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

Jürgen Albert, Hermann Maurer, Grzegorz Rozenberg (auth.), Giorgio Ausiello, Corrado Böhm (eds.)9783540088608, 3540088601

This volume contains the proceedings of ICALP 89, held at Stresa, Italy, July 11-15, 1989. ICALP 89 is the 16th International Colloquium on Automata, Languages and Programming in a series of meetings sponsored by the European Association for Theoretical Computer Science (EATCS). It is a broadly based conference covering all aspects of theoretical computer science including topics such as computability, automata theory, formal language theory, analysis of algorithms, computational complexity, mathematical aspects of programming language definition, logic and semantics of programming languages, foundations of logic programming, theorem proving, software specification, computational geometry, data types and data structures, theory of data bases and knowledge based systems, cryptography, VLSI structures, parallel and distributed computing, models of concurrency and robotics.

---

Table of contents :
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