Automata, Languages and Programming: 12th Colloquium Nafplion, Greece, July 15–19, 1985

Vertex packing algorithms....Pages 1-14
Linear and branching structures in the semantics and logics of reactive systems....Pages 15-32
About rational sets of factors of a bi-infinite word....Pages 33-42
A fair protocol for signing contracts....Pages 43-52
The influence of key length on the area-time complexity of sorting....Pages 53-62
Repeated synchronous snapshots and their implementation in CSP....Pages 63-70
On total regulators generated by derivation relations....Pages 71-79
Optimal solutions for a class of point retrieval problems....Pages 80-89
Fractional cascading: A data structuring technique with geometric applications....Pages 90-100
Hierarchies of one-way multihead automata languages....Pages 101-110
Partitioning point sets in 4 dimensions....Pages 111-119
A completeness theorem for recursively defined types....Pages 120-129
Categorical combinatory logic....Pages 130-139
Towards a uniform topological treatment of streams and functions on streams....Pages 140-148
Infinite streams and finite observations in the semantics of uniform concurrency....Pages 149-157
Imposed-functional dependencies inducing horizontal decompositions....Pages 158-170
Characterization of high level tree transducers....Pages 171-178
Ambiguity and transcendence....Pages 179-188
A fast algorithm for polygon containment by translation....Pages 189-198
Deterministic and Las Vegas primality testing algorithms....Pages 199-209
Efficient algorithms for graphic matroid intersection and parity....Pages 210-220
Operational semantics for order-sorted algebra....Pages 221-231
A universal domain technique for profinite posets....Pages 232-243
A simple proof of the Skolem-Mahler-Lech theorem....Pages 244-249
On complete problems for NP ∩ CoNP ....Pages 250-259
An algebraic theory of fair asynchronous communicating processes....Pages 260-269
Hoare's logic for nondeterministic regular programs: A nonstandard completeness theorem....Pages 270-280
Powerdomains as algebraic lattices preliminary report....Pages 281-289
Random generation of combinatiorial structures from a uniform distribution....Pages 290-299
Do rational equivalence relations have regular cross-sections?....Pages 300-309
On probabilistic time and space....Pages 310-317
The nearest neighbor problem on bounded domains....Pages 318-327
Routing through a generalized switchbox....Pages 328-337
On k-repetition free words generated by length uniform morphisms over a binary alphabet....Pages 338-347
Every commutative quasirational language is regular....Pages 348-355
A probabilistic distributed algorithm for set intersection and its analysis....Pages 356-362
Distributed algorithms in synchronous broadcasting networks....Pages 363-372
A context dependent equivalence between processes....Pages 373-382
Lower bounds by kolmogorov-complexity....Pages 383-393
A bidirectional shortest-path algorithm with good average-case behavior (preliminary version)....Pages 394-403
Applications of an infinite squarefree CO-CFL....Pages 404-412
Special relations in automated deduction....Pages 413-423
Dynamic interpolation search....Pages 424-434
Polynomial levelability and maximal complexity cores....Pages 435-444
Finite group topology and p-adic topology for free monoids....Pages 445-455
On the use of relational expressions in the design of efficient algorithms....Pages 456-464
The complementation problem for Büchi automata with applications to temporal logic....Pages 465-474
A complete compositional modal proof system for a subset of CCS....Pages 475-486
On matrix multiplication using array processors....Pages 487-496
Optimal parallel pattern matching in strings....Pages 497-508
Compositionality and concurrent networks: Soundness and completeness of a proofsystem....Pages 509-519