Ebook: Automata, Languages and Programming: Fifth Colloquium, Udine, Italy, July 17–21, 1978

---

Content:
Front Matter....Pages -
Simple EOL forms under uniform interpretation generating CF languages....Pages 1-14
Codes : Unequal probabilities, unequal letter costs....Pages 15-25
Sur l'inversion des morphismes d'arbres....Pages 26-35
Grammars with dynamic control sets....Pages 36-51
Ambiguite forte....Pages 52-62
Relationship between density and deterministic complexity of MP-complete languages....Pages 63-71
Stable models of typed ?-calculi....Pages 72-89
Path measures of turing machine computations....Pages 90-104
Une famille remarquable de codes indecomposables....Pages 105-112
Comparisons and reset machines....Pages 113-124
Size — Depth tradeoff in boolean formulas....Pages 125-141
(Semi)-separability of finite sets of terms in Scott's D?-models of the ?-calculus....Pages 142-164
Mutual exclusion of N processors using an O(N)-valued message variable....Pages 165-176
On the power of self-application and higher type recursion....Pages 177-191
Time and space bounds for selection problems....Pages 192-204
Stepwise specification and implementation of abstract data types....Pages 205-226
The complexity of equivalence and containment for free single variable program schemes....Pages 227-240
On improving the worst case running time of the Boyer-Moore string matching algorithm....Pages 241-250
Semantics and correctness of nondeterministic flowchart programs with recursive procedures....Pages 251-267
Arithmetical completeness in logics of programs....Pages 268-288
Covering a graph by circuits....Pages 289-299
A pspace complete problem related to a pebble game....Pages 300-321
Some effective results about linear recursive sequences....Pages 322-329
On the parsing and covering of simple chain grammars....Pages 330-344
Sur un cas particulier de la conjecture de Cerny....Pages 345-352
States can sometimes do more than stack symbols in PDA's....Pages 353-362
Some decision results for recognizable sets in arbitrary monoids....Pages 363-371
Sur les series rationnelles en variables non commutatives....Pages 372-381
On constructing efficient evaluators for attribute grammars....Pages 382-397
Une extension de la theorie des types en ?-calcul....Pages 398-410
Parallel and nondeterministic time complexity classes....Pages 411-424
Multiterminal network flow and connectivity in unsymmetrical networks....Pages 425-439
Admissible coherent c.p.o.'s....Pages 440-456
Integration of the phase-difference relations in asynchronous sequential networks....Pages 457-463
Self-modifying nets, a natural extension of Petri nets....Pages 464-476
Head recurrent terms in combinatory logic : A generalization of the notion of head normal form....Pages 477-493
Characterization problems in the theory of inductive inference....Pages 494-508

---

Content:
Front Matter....Pages -
Simple EOL forms under uniform interpretation generating CF languages....Pages 1-14
Codes : Unequal probabilities, unequal letter costs....Pages 15-25
Sur l'inversion des morphismes d'arbres....Pages 26-35
Grammars with dynamic control sets....Pages 36-51
Ambiguite forte....Pages 52-62
Relationship between density and deterministic complexity of MP-complete languages....Pages 63-71
Stable models of typed ?-calculi....Pages 72-89
Path measures of turing machine computations....Pages 90-104
Une famille remarquable de codes indecomposables....Pages 105-112
Comparisons and reset machines....Pages 113-124
Size — Depth tradeoff in boolean formulas....Pages 125-141
(Semi)-separability of finite sets of terms in Scott's D?-models of the ?-calculus....Pages 142-164
Mutual exclusion of N processors using an O(N)-valued message variable....Pages 165-176
On the power of self-application and higher type recursion....Pages 177-191
Time and space bounds for selection problems....Pages 192-204
Stepwise specification and implementation of abstract data types....Pages 205-226
The complexity of equivalence and containment for free single variable program schemes....Pages 227-240
On improving the worst case running time of the Boyer-Moore string matching algorithm....Pages 241-250
Semantics and correctness of nondeterministic flowchart programs with recursive procedures....Pages 251-267
Arithmetical completeness in logics of programs....Pages 268-288
Covering a graph by circuits....Pages 289-299
A pspace complete problem related to a pebble game....Pages 300-321
Some effective results about linear recursive sequences....Pages 322-329
On the parsing and covering of simple chain grammars....Pages 330-344
Sur un cas particulier de la conjecture de Cerny....Pages 345-352
States can sometimes do more than stack symbols in PDA's....Pages 353-362
Some decision results for recognizable sets in arbitrary monoids....Pages 363-371
Sur les series rationnelles en variables non commutatives....Pages 372-381
On constructing efficient evaluators for attribute grammars....Pages 382-397
Une extension de la theorie des types en ?-calcul....Pages 398-410
Parallel and nondeterministic time complexity classes....Pages 411-424
Multiterminal network flow and connectivity in unsymmetrical networks....Pages 425-439
Admissible coherent c.p.o.'s....Pages 440-456
Integration of the phase-difference relations in asynchronous sequential networks....Pages 457-463
Self-modifying nets, a natural extension of Petri nets....Pages 464-476
Head recurrent terms in combinatory logic : A generalization of the notion of head normal form....Pages 477-493
Characterization problems in the theory of inductive inference....Pages 494-508
....