Automata, Languages and Programming: 21st International Colloquium, ICALP 94 Jerusalem, Israel, July 11–14, 1994 Proceedings

Pavel Pudlák (auth.), Serge Abiteboul, Eli Shamir (eds.)3540582010, 9783540582014

This volume constitutes the proceedings of the 21st International Colloquium on Automata, Languages and Programming (ICALP 94), held at Jerusalem in July 1994. ICALP is an annual conference sponsored by the European Association on Theoretical Computer Science (EATCS). The proceedings contains 48 refereed papers selected from 154 submissions and 4 invited papers. The papers cover the whole range of theoretical computer science; they are organized in sections on theory of computation, automata and computation models, expressive power, automata and concurrency, pattern matching, data structures, computational complexity, logic and verification, formal languages, term rewriting, algorithms and communications, graph algorithms, randomized complexity, various algorithms.

---

Table of contents :
Unexpected upper bounds on the complexity of some communication games….Pages 1-10
Valuations and unambiguity of languages, with applications to fractal geometry….Pages 11-22
On the computational power of probabilistic and faulty neural networks….Pages 23-34
Deciding properties of integral relational automata….Pages 35-46
On the cost of recomputing: tight bounds on pebbling with faults….Pages 47-58
On some relations between dynamical systems and transition systems….Pages 59-72
Complexity results for multi-pebble automata and their logics….Pages 73-82
An analysis of the Core-ML language: Expressive power and type reconstruction….Pages 83-105
Expressiveness of efficient semi-deterministic choice constructs….Pages 106-117
Tailoring recursion for complexity….Pages 118-129
Determinizing asynchronous automata….Pages 130-141
On the complementation of Büchi asynchronous cellular automata….Pages 142-153
Distribution and locality of concurrent systems….Pages 154-165
Liveness in timed and untimed systems….Pages 166-177
Average-case analysis of pattern-matching in trees under the BST probability model….Pages 178-190
On the approximation of shortest common supersequences and longest common subsequences….Pages 191-202
Optimal parallel algorithms for Prefix Matching….Pages 203-214
Optimal two-dimensional compressed matching….Pages 215-226
Maintaining spanning trees of small diameter….Pages 227-238
Simple fast parallel hashing….Pages 239-250
The Optimal Alphabetic Tree problem revisited….Pages 251-262
On the cutting edge of relativization: The resource bounded injury method….Pages 263-273
PSPACE-completeness of certain algorithmic problems on the subgroups of free groups….Pages 274-285
Higher-order processes and their models….Pages 286-303
Efficient local correctness checking for single and alternating boolean equation systems….Pages 304-315
Undecidable verification problems for programs with unreliable channels….Pages 316-327
Reasoning about programs by exploiting the environment….Pages 328-339
A model of intuitionistic affine logic from stable domain theory….Pages 340-351
Bistructures, bidomains and linear logic….Pages 352-363
Equivalences for fair Kripke structures….Pages 364-375
Generalizing finiteness conditions of labelled transition systems….Pages 376-387
A kleene theorem for recognizable languages over concurrency monoids….Pages 388-399
Least solutions of equations over N ….Pages 400-411
Fast uniform analysis of Coupled-Context-Free languages….Pages 412-423
Polynomial closure of group languages and open sets of the Hall topology….Pages 424-435
Pumping, cleaning and symbolic constraints solving….Pages 436-449
Dynamically-typed computations for order-sorted equational presentations….Pages 450-461
Combining first order algebraic rewriting systems, recursion and extensional lambda calculi….Pages 462-472
On the theory of interconnection networks for parallel computers….Pages 473-486
Multiway cuts in directed and node weighted graphs….Pages 487-498
A fast randomized LOGSPACE algorithm for graph connectivity….Pages 499-507
Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing….Pages 508-519
The size of an intertwine….Pages 520-531
Finding even cycles even faster….Pages 532-543
Polynomial time analysis of toroidal periodic graphs….Pages 544-555
A tight lower bound for primitivity in k -structures….Pages 556-567
Randomness in distribution protocols….Pages 568-579
Lower space bounds for randomized computation….Pages 580-592
The average case complexity of the parallel prefix problem….Pages 593-604
Prefix codes: Equiprobable words, unequal letter costs….Pages 605-617
A super-logarithmic lower bound for hypercubic sorting networks….Pages 618-629
Efficient strategies for robot navigation in unknown environment….Pages 630-641