Automata, Languages and Programming: 2nd Colloquium, University of Saarbrücken, July 29 - August 2, 1974. Proceedings (Lecture Notes in Computer Science, 14) (English, French and German Edition)

The generative power of two-level grammars....Pages 9-16 A generalisation of Parikh's theorem in formal language theory....Pages 17-26 Checking stacks and context-free programmed grammars accept p-complete languages....Pages 27-33 Recursion and parameter mechanisms: An axiomatic approach....Pages 34-65 Dynamic programming schemata....Pages 66-80 Semantic characterization of flow diagrams and their decomposability....Pages 81-96 On the most recent property of ALGOL-like programs....Pages 97-111 Langages sans etiquettes et transformations de programmes....Pages 112-128 Relations between semantics and complexity of recursive programs-....Pages 129-140 On the relation between direct and continuation semantics....Pages 141-156 Graph representation and computation rules for typeless recursive languages....Pages 157-169 Application of Church-Rosser properties to increase the parallelism and efficiency of algorithms....Pages 170-184 Combinatorial problems, combinator equations and normal forms....Pages 185-199 Algorithmes d'Equivalence et de reduction a des expressions minimales dans une classe d'equations recursives simples....Pages 200-213 Automatic generation of multiple exit parsing subroutines....Pages 214-231 Production prefix parsing....Pages 232-241 On eliminating unit productions from LR(k) parsers....Pages 242-254 Deterministic techniques for efficient non-deterministic parsers....Pages 255-269 File organization, an application of graph theory....Pages 270-279 Characterizations of time-bounded computations by limited primitive recursion....Pages 280-293 On maximal merging of information in Boolean computations....Pages 294-300 On simple Goedel numberings and translations....Pages 301-316 The ‘almost all’ theory of subrecursive degrees is decidable....Pages 317-325 The computational complexity of program schemata....Pages 326-334 Un resultat en theorie des groupes de permutations et son application au calcul effectif du groupe d'automorphismes d'un automate fini....Pages 335-341 Sur l'Application du theoreme de suschkewitsch a l'etude des codes rationnels complets....Pages 342-350 Composition of automata....Pages 351-363 Context-free grammar forms....Pages 364-382 Une suite decroissante de cônes rationnels....Pages 383-397 Komplexitätsmaße for Ausdrocke....Pages 398-412 Efficient procedures for using matrix algorithms....Pages 413-427 Further schemes for combining matrix algorithms....Pages 428-436 On the structure of complexity classes....Pages 437-445 On sets having only hard subsets....Pages 446-457 Turing machines with associative memory access....Pages 458-472 Trade-off between the use of nonterminals, codings and homomorphisms in defining languages for some classes of rewriting systems....Pages 473-480 Operators reducing generalized OL-systems....Pages 481-494 Parallel rewriting systems on terms....Pages 495-510 Transductions of context-free languages into sets of sentential forms....Pages 511-522 Parallelism in rewriting systems....Pages 523-533 Mehrdeutigkeiten kontextfreier Grammatiken....Pages 534-546 Monadic program schemes under restricted classes of free interpretations....Pages 547-561 Generalized program schemas....Pages 562-576 A decidability result for sequential grammars....Pages 577-583 Effectivity problems of algorithmic logic....Pages 584-600 Simple and structural redundancy in non-deterministic computation....Pages 601-611 Sur une propriete syntactique des relations rationnelles....Pages 612-619 The Second Colloquium On Automata, Languages And Programming Is The Successor Of A Similar Colloquium Organized By Iria In Paris, July 3-7, 1972. The Present Colloquium Which Takes Place At The Unl- Versity Of Saarbrucken From July 29th To August 2nd, 1974, Is Spon Sored By The Gesellschaft Fur. Informatik And Organized In Cooperation Wlth The Special Interest Group On Automata And Computability Theory (sigact) And With The European Association For Theoretical Computer Science (eatcs). As Its Predecessor The Present Colloquium Is Devoted To The Theo Retical Bases Of Computer Science. This Volume Contains The Text Of The Different Lectures Of The Colloquium Whlch Have Been Selected By The Program Committee Out Of About 130 Submitted Papers. About One Third Of The Papers Of This Volume Is Concerned With Formal Language Theory, One Other Third With The Theory Of Computation And The Rest With Complexity Theory, Automata Theory, Programming Languages, Etc.