Automata, Languages and Programming: 13th International Colloquium Rennes, France, July 15–19, 1986 Proceedings

Characterizations of PUNC and precomputation....Pages 1-10
Comparison of algorithms controlling concurrent access to a database: A combinatorial approach....Pages 11-20
A new duality result concerning Voronoi diagrams....Pages 21-30
Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial....Pages 31-39
On exponential lowness....Pages 40-49
A tradeoff between search and update time for the implicit dictionary problem....Pages 50-59
Intersections of some families of languages....Pages 60-68
Correspondence between ternary simulation and binary race analysis in gate networks....Pages 69-78
Counting with rational functions....Pages 79-88
Finite biprefix sets of paths in a Graph....Pages 89-94
Parallel RAMs with owned global memory and deterministic context-free language recognition....Pages 95-104
A Strong restriction of the inductive completion procedure....Pages 105-115
On discerning words by automata....Pages 116-122
Complexity classes without machines: On complete languages for UP....Pages 123-135
Containment, separation, complete sets, and immunity of complexity classes....Pages 136-145
On nontermination of Knuth-Bendix algorithm....Pages 146-156
Tradeoffs for language recognition on parallel computing models....Pages 157-166
Rational equivalence relations....Pages 167-176
Some further results on digital search trees....Pages 177-185
Knowledge, belief and time....Pages 186-195
A termination detector for static and dynamic distributed systems with asynchronous non-first-in-first-out communication....Pages 196-205
Decompositions of nondeterministic reductions....Pages 206-214
Hierarchical planarity testing algorithms....Pages 215-225
Synthesis and equivalence of concurrent systems....Pages 226-235
The set union problem with backtracking....Pages 236-243
Torsion matrix semigroups and recognizable transductions....Pages 244-253
On recognizable subsets of free partially commutative monoids....Pages 254-264
Min Cut is NP-complete for edge weighted trees....Pages 265-274
Alternating automata, the weak monadic theory of the tree, and its complexity....Pages 275-283
Subpolynomial complexity classes of real functions and real numbers....Pages 284-293
Etude syntaxique des parties reconnaissables de mots infinis....Pages 294-303
Refusal testing....Pages 304-313
A timed model for communicating sequential processes....Pages 314-323
A uniform reduction theorem extending a result of J. Grollmann and A. Selman....Pages 324-333
On the complexity of deciding fair termination of probabilistic concurrent finite-state programs....Pages 334-343
A new approach to detection of locally indicative stability....Pages 344-358
A more efficient algorithm for lattice basis reduction....Pages 359-369
Lower bounds by recursion theoretic arguments....Pages 370-375
An improved algorithm for transitive closure on acyclic digraphs....Pages 376-386
Un algorithme determinant les melanges de deux mots....Pages 387-396
A very fast, practical algorithm for finding a negative cycle in a digraph....Pages 397-406
A compositional reformulation of Owicki-Gries's partial correctness logic for a concurrent while language....Pages 407-415
Semigroups and languages of dot-depth 2....Pages 416-423
A parallel vertex insertion algorithm for minimum spanning trees....Pages 424-433
More complicated questions about maxima and minima, and some closures of NP....Pages 434-443
Lower bounds for dynamic range query problems that permit subtraction (extended abstract)....Pages 444-453
E-unification algorithms for a class of confluent term rewriting systems....Pages 454-463
On fixed-point clones....Pages 464-473