Automata, Languages and Programming: 22nd International Colloquium, ICALP 95 Szeged, Hungary, July 10–14, 1995 Proceedings

A. Ehrenfeucht, T. Harju, G. Rozenberg (auth.), Zoltán Fülöp, Ferenc Gécseg (eds.)3540600841, 9783540600848

This volume constitutes the proceedings of the 22nd Interna- tional Colloquium on Automata, Languages, and Programming, held under the sponsorship of EATCS in Szeged, Hungary in July 1995.
The volume presents four invited papers and 53 full revised research papers selected from a total of 111 submissions. ICALP traditionally covers the whole area of theoretical computer science; among the topics addressed in the volume are concurrency, automata, formal languages, algorithms, communication protocols, computational complexity, computability, foundations of programming, learning and coding, and semantics.

---

Table of contents :
Theory of 2-structures….Pages 1-14
A domain for concurrent termination a generalization of Mazurkiewicz traces….Pages 15-26
Nonfinite axiomatizability of the equational theory of shuffle….Pages 27-38
The algebraic equivalent of AFL theory….Pages 39-50
Finite state transformations of images….Pages 51-62
Post correspondence problem: Words possible as primitive solutions….Pages 63-74
Computing the closure of sets of words under partial commutations….Pages 75-86
Intervalizing k -colored graphs….Pages 87-98
NC algorithms for finding a maximal set of paths with application to compressing strings….Pages 99-110
On the construction of classes of suffix trees for square matrices: Algorithms and applications….Pages 111-122
How to use the minimal separators of a graph for its chordal triangulation….Pages 123-134
Fast gossiping by short messages….Pages 135-146
Break Finite Automata Public Key Cryptosystem….Pages 147-158
Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time….Pages 159-170
On the number of random bits in totally private computation….Pages 171-182
Lower time bounds for randomized computation….Pages 183-195
New collapse consequences of NP having small circuits….Pages 196-207
The complexity of searching succinctly represented graphs….Pages 208-219
Optimal shooting: Characterizations and applications….Pages 220-231
Placing resources in a tree: Dynamic and static algorithms….Pages 232-243
Shortest path queries in digraphs of small treewidth….Pages 244-255
A dynamic programming algorithm for constructing optimal prefix-free codes for unequal letter costs….Pages 256-267
Parallel algorithms with optimal speedup for bounded treewidth….Pages 268-279
Approximating minimum cuts under insertions….Pages 280-291
Linear time algorithms for dominating pairs in asteroidal triple-free graphs….Pages 292-302
On-line resource management with applications to routing and scheduling….Pages 303-314
Alternation in simple devices….Pages 315-323
Hybrid automata with finite bisimulations….Pages 324-335
Generalized Sturmian languages….Pages 336-347
Polynomial closure and unambiguous product….Pages 348-359
Lower bounds on algebraic random access machines….Pages 360-371
Improved deterministic PRAM simulation on the mesh….Pages 372-383
On optimal polynomial time approximations: P-levelability vs. δ-levelability….Pages 384-392
Weakly useful sequences….Pages 393-404
Graph Connectivity, Monadic NP and built-in relations of moderate degree….Pages 405-416
The expressive power of clocks….Pages 417-428
Grammar systems: A grammatical approach to distribution and cooperation….Pages 429-443
Compactness of systems of equations in semigroups….Pages 444-454
Sensing versus nonsensing automata….Pages 455-463
New upper bounds for generalized intersection searching problems….Pages 464-474
OKFDDs versus OBDDs and OFDDs….Pages 475-486
Bicriteria network design problems….Pages 487-498
On determining optimal strategies in pursuit games in the plane….Pages 499-510
Extension orderings….Pages 511-522
The pushdown method to optimize chain logic programs….Pages 523-534
Automatic synthesis of real time systems….Pages 535-546
Self-correcting for function fields of finite transcendental degree….Pages 547-557
Measure, category and learning theory….Pages 558-569
A characterization of the existence of energies for neural networks….Pages 570-580
Variable-length codes for error correction….Pages 581-592
Graphbots: Mobility in discrete spaces….Pages 593-604
Solving recursive net equations….Pages 605-623
Implicit definability and infinitary logic in finite model theory….Pages 624-635
The limit of split n -language equivalence….Pages 636-647
Divergence and fair testing….Pages 648-659
Causality for mobile processes….Pages 660-671
Internal mobility and agent-passing calculi….Pages 672-683