Automata, Languages and Programming: 14th International Colloquium Karlsruhe, Federal Republic of Germany, July 13–17, 1987 Proceedings

Leonard Pitt, Carl H. Smith (auth.), Thomas Ottmann (eds.)3540180885, 9783540180883

This volume contains the proceedings of the 14th International Colloquium on Automata Languages and Programming, organized by the European Association for Theoretical Computer Science (EATCS) and held in Karlsruhe, July 13-17, 1987. The papers report on original research in theoretical computer science and cover topics such as algorithms and data structures, automata and formal languages, computability and complexity theory, semantics of programming languages, program specification, transformation and verification, theory of data bases, logic programming, theory of logical design and layout, parallel and distributed computation, theory of concurrency, symbolic and algebraic computation, term rewriting systems, cryptography, and theory of robotics. The authors are young scientists and leading experts in these areas.

---

Table of contents :
Probability and plurality for aggregations of learning machines….Pages 1-10
Logic programming with ions….Pages 11-20
Inverse image analysis….Pages 21-30
A unification algorithm for confluent theories….Pages 31-41
On the Knuth-Bendix completion for concurrent processes….Pages 42-53
On word problems in equational theories….Pages 54-71
Semantics for nondeterministic asynchronous broadcast networks….Pages 72-83
Another look at abstraction in process algebra….Pages 84-94
A timed failures model for extended communicating processes….Pages 95-114
Readiness semantics for regular processes with silent actions….Pages 115-125
Verifying a protocol using relativized bisimulation….Pages 126-135
On recent trends in formal language theory….Pages 136-162
Non-uniform automata over groups….Pages 163-173
Minimal automaton of a rational cover….Pages 174-189
A star-height problem in free monoids with partial commutations….Pages 190-201
Single-valued finite transduction….Pages 202-211
The kleene and the Parikh Theorem in complete semirings….Pages 212-225
An algorithm for computing asynchronous automata in the case of acyclic non-commutation graphs….Pages 226-236
On the languages accepted by finite reversible automata….Pages 237-249
Decision problems for regular trace languages….Pages 250-259
Panic mode without panic….Pages 260-268
Computation tree logic CTL* and path quantifiers in the monadic theory of the binary tree….Pages 269-279
Modelchecking of CTL formulae under liveness assumptions….Pages 280-289
A modal logic for a subclass of event structures….Pages 290-303
Parallel 5-colouring of planar graphs….Pages 304-313
Parallel construction of a suffix tree….Pages 314-325
The probabilistic and deterministic parallel complexity of symmetric functions….Pages 326-335
Term matching on parallel computers….Pages 336-346
Guessing games and distributed computations in synchronous networks….Pages 347-356
On the bivariate function minimization problem and its applications to motion planning….Pages 357-363
Testing the necklace condition for Shortest Tours and optimal factors in the plane….Pages 364-375
Nearly optimal heuristics for binary search trees with geometric generalizations….Pages 376-385
Approximating integer lattices by lattices with cyclic factor groups….Pages 386-393
On the complexity of graph critical uncolorability….Pages 394-403
Posets, boolean representations and quick path searching….Pages 404-424
The lexicographically first maximal subgraph problems: P-completeness and NC algorithms….Pages 425-434
Uniform computational complexity of Taylor series….Pages 435-444
Efficient on-line algorithms for the knapsack problem….Pages 445-456
Lower bounds for sorting of sums….Pages 457-466
The I/O complexity of sorting and related problems….Pages 467-478
A lower bound for the complexity of the Union-Split-Find problem….Pages 479-488
The nearest common ancestor in a dynamic tree….Pages 489-498
A generalization of the procedure of karp and miller to well structured transition systems….Pages 499-508
Completeness results for reachability, containment, and equivalence, with respect to conflict-free vector replacement systems….Pages 509-520
Partial algebras flow from algebraic specifications….Pages 521-530
The logarithmic alternation hierarchy collapses: $$ASigma _2^mathcal{L} = APi _2^mathcal{L}$$ ….Pages 531-541
Testing membership in commutative transformation semigroups….Pages 542-549
On the computing power of one-way cellular arrays….Pages 550-562
Recent developments in the theory of learning….Pages 563-563