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

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: $$A\Sigma _2^\mathcal{L} = A\Pi _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