Automata, Languages and Programming: 13th International Colloquium, Rennes, France, July 1519, 1986. Proceedings (Lecture Notes,Used

Characterizations of PUNC and precomputation. Comparison of algorithms controlling concurrent access to a A combinatorial approach. A new duality result concerning Voronoi diagrams. Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial. On exponential lowness. A tradeoff between search and update time for the implicit dictionary problem. Intersections of some families of languages. Correspondence between ternary simulation and binary race analysis in gate networks. Counting with rational functions. Finite biprefix sets of paths in a Graph. Parallel RAMs with owned global memory and deterministic contextfree language recognition. A Strong restriction of the inductive completion procedure. On discerning words by automata. Complexity classes without On complete languages for UP. Containment, separation, complete sets, and immunity of complexity classes. On nontermination of KnuthBendix algorithm. Tradeoffs for language recognition on parallel computing models. Rational equivalence relations. Some further results on digital search trees. Knowledge, belief and time. A termination detector for static and dynamic distributed systems with asynchronous nonfirstinfirstout communication. Decompositions of nondeterministic reductions. Hierarchical planarity testing algorithms. Synthesis and equivalence of concurrent systems. The set union problem with backtracking. Torsion matrix semigroups and recognizable transductions. On recognizable subsets of free partially commutative monoids. Min Cut is NPcomplete for edge weighted trees. Alternating automata, the weak monadic theory of the tree, and its complexity. Subpolynomial complexity classes of real functions and real numbers. Etude syntaxique des parties reconnaissables de mots infinis. Refusal testing. A timed model for communicating sequential processes. A uniform reduction theorem extending a result of J. Grollmann and A. Selman. On the complexity of deciding fair termination of probabilistic concurrent finitestate programs. A new approach to detection of locally indicative stability. A more efficient algorithm for lattice basis reduction. Lower bounds by recursion theoretic arguments. An improved algorithm for transitive closure on acyclic digraphs. Un algorithme determinant les melanges de deux mots. A very fast, practical algorithm for finding a negative cycle in a digraph. A compositional reformulation of OwickiGries's partial correctness logic for a concurrent while language. Semigroups and languages of dotdepth 2. A parallel vertex insertion algorithm for minimum spanning trees. More complicated questions about maxima and minima, and some closures of NP. Lower bounds for dynamic range query problems that permit subtraction (extended abstract). Eunification algorithms for a class of confluent term rewriting systems. On fixedpoint clones.