Automata, Languages and Programming: 2nd Colloquium, University of Saarbrücken, July 29 - August 2, 1974. Proceedings - Softcover

Softcover

ISBN 10: 3662215462 ISBN 13: 9783662215463

Publisher: Springer, 2014

Synopsis

The generative power of two-level grammars.- A generalisation of Parikh's theorem in formal language theory.- Checking stacks and context-free programmed grammars accept p-complete languages.- Recursion and parameter mechanisms: An axiomatic approach.- Dynamic programming schemata.- Semantic characterization of flow diagrams and their decomposability.- On the most recent property of ALGOL-like programs.- Langages sans etiquettes et transformations de programmes.- Relations between semantics and complexity of recursive programs-.- On the relation between direct and continuation semantics.- Graph representation and computation rules for typeless recursive languages.- Application of Church-Rosser properties to increase the parallelism and efficiency of algorithms.- Combinatorial problems, combinator equations and normal forms.- Algorithmes d'Equivalence et de reduction a des expressions minimales dans une classe d'equations recursives simples.- Automatic generation of multiple exit parsing subroutines.- Production prefix parsing.- On eliminating unit productions from LR(k) parsers.- Deterministic techniques for efficient non-deterministic parsers.- File organization, an application of graph theory.- Characterizations of time-bounded computations by limited primitive recursion.- On maximal merging of information in Boolean computations.- On simple Goedel numberings and translations.- The 'almost all' theory of subrecursive degrees is decidable.- The computational complexity of program schemata.- Un resultat en theorie des groupes de permutations et son application au calcul effectif du groupe d'automorphismes d'un automate fini.- Sur l'Application du theoreme de suschkewitsch a l'etude des codes rationnels complets.- Composition of automata.- Context-free grammar forms.- Une suite decroissante de cônes rationnels.- Komplexitätsmaße for Ausdrocke.- Efficient procedures for using matrix algorithms.- Further schemes for combining matrix algorithms.- On the structure of complexity classes.- On sets having only hard subsets.- Turing machines with associative memory access.- Trade-off between the use of nonterminals, codings and homomorphisms in defining languages for some classes of rewriting systems.- Operators reducing generalized OL-systems.- Parallel rewriting systems on terms.- Transductions of context-free languages into sets of sentential forms.- Parallelism in rewriting systems.- Mehrdeutigkeiten kontextfreier Grammatiken.- Monadic program schemes under restricted classes of free interpretations.- Generalized program schemas.- A decidability result for sequential grammars.- Effectivity problems of algorithmic logic.- Simple and structural redundancy in non-deterministic computation.- Sur une propriete syntactique des relations rationnelles.

Edition details

• Publisher: Springer
• Publication date: 2014
• Language: English
• ISBN 10: 3662215462
• ISBN 13: 9783662215463
• Binding: Paperback