Automata, Languages and Programming: 25th International Colloquium, ICALP’98 Aalborg, Denmark, July 13–17, 1998 Proceedings

Yonit Kesten, Amir Pnueli, Li-on Raviv (auth.), Kim G. Larsen, Sven Skyum, Glynn Winskel (eds.)3540647813, 9783540647812

This book constitutes the refereed proceedings of the 25th International Colloquium on Automata, Languages and Programming, ICALP’98, held in Aalborg, Denmark, in July 1998.
The 70 revised full papers presented together with eight invited contributions were carefully selected from a total of 182 submissions. The book is divided in topical sections on complexitiy, verification, data structures, concurrency, computational geometry, automata and temporal logic, algorithms, infinite state systems, semantics, approximation, thorem proving, formal languages, pi-calculus, automata and BSP, rewriting, networking and routing, zero-knowledge, quantum computing, etc..

---

Table of contents :
Algorithmic verification of linear temporal logic specifications….Pages 1-16
On existentially first-order definable languages and their relation to NP….Pages 17-28
An algebraic approach to communication complexity….Pages 29-40
Deciding global partial-order properties….Pages 41-52
Simple linear-time algorithms for minimal fixed points….Pages 53-66
Hardness results for dynamic problems by extensions of Fredman and Saks’ chronogram method….Pages 67-78
Simpler and faster dictionaries on the AC 0 RAM….Pages 79-90
Partial-congruence factorization of bisimilarity induced by open maps….Pages 91-102
Reset nets between decidability and undecidability….Pages 103-115
Geometric algorithms for robotic manipulation….Pages 116-117
Compact encodings of planar graphs via canonical orderings and multiple parentheses….Pages 118-129
Reducing simple polygons to triangles – A proof for an improved conjecture -….Pages 130-139
Difficult configurations — on the complexity of LTrL ….Pages 140-151
On the expressiveness of real and integer arithmetic automata….Pages 152-163
Distributed matroid basis completion via elimination upcast and distributed correction of minimum-weight spanning trees….Pages 164-175
Independent sets with domination constraints….Pages 176-187
Robust asynchronous protocols are finite-state….Pages 188-199
Deciding bisimulation-like equivalences with finite-state processes….Pages 200-211
Do probabilistic algorithms outperform deterministic ones?….Pages 212-214
A degree-decreasing Lemma for (MOD q, MOD p) circuits….Pages 215-222
Improved pseudorandom generators for combinatorial rectangles….Pages 223-234
Translation validation for synchronous languages….Pages 235-246
An efficient and unified approach to the decidability of equivalence of propositional programs….Pages 247-258
On branching programs with bounded uncertainty….Pages 259-270
CONS-free programs with tree input….Pages 271-282
Concatenable graph processes: Relating processes and derivation traces….Pages 283-295
Axioms for contextual net processes….Pages 296-308
Existential types: Logical relations and operational equivalence….Pages 309-326
Optimal sampling strategies in quicksort….Pages 327-338
A genuinely polynomial-time algorithm for sampling two-rowed contingency tables….Pages 339-350
A modular approach to denotational semantics….Pages 351-362
Generalised flowcharts and games….Pages 363-374
Efficient minimization of numerical summation errors….Pages 375-386
Efficient approximation algorithms for the subset-sums equality problem….Pages 387-396
Structural recursive definitions in type theory….Pages 397-408
A good class of tree automata. Application to inductive theorem proving….Pages 409-420
Locally periodic infinite words and a chaotic behaviour….Pages 421-430
Bridges for concatenation hierarchies….Pages 431-442
Complete proof systems for observation congruences in finite-control π-calculus….Pages 443-454
Concurrent constraints in the fusion calculus….Pages 455-469
On computing the entropy of cellular automata….Pages 470-481
On the determinization of weighted finite automata….Pages 482-493
Bulk-synchronous parallel multiplication of boolean matrices….Pages 494-506
A complex example of a simplifying rewrite system….Pages 507-517
On a duality between Kruskal and Dershowitz theorems….Pages 518-529
A total AC-compatible reduction ordering on higher-order terms….Pages 530-542
Model checking game properties of multi-agent systems….Pages 543-543
Limited wavelength conversion in all-optical tree networks….Pages 544-555
Computing mimicking networks….Pages 556-567
Metric semantics for true concurrent real time….Pages 568-579
The regular real-time languages….Pages 580-591
Static and dynamic low-congested interval routing schemes….Pages 592-603
Low-bandwidth routing and electrical power networks….Pages 604-615
Constraint automata and the complexity of recursive subtype entailment….Pages 616-627
Reasoning about the past with two-way automata….Pages 628-641
A neuroidal architecture for cognitive computation….Pages 642-669
Deterministic polylog approximation for minimum communication spanning trees….Pages 670-681
A polynomial time approximation scheme for euclidean minimum cost k -connectivity….Pages 682-694
Global/local subtyping and capability inference for a distributed π-calculus….Pages 695-706
Checking strong/Weak bisimulation equivalences and observation congruence for the π-calculus….Pages 707-718
Inversion of circulant matrices over Z m ….Pages 719-730
Application of Lempel-Ziv encodings to the solution of word equations….Pages 731-742
Explicit substitutitions for constructive necessity….Pages 743-754
The relevance of proof-irrelevance….Pages 755-768
New horizons in quantum information processing….Pages 769-771
Sequential iteration of interactive arguments and an efficient zero-knowledge argument for NP….Pages 772-783
Image density is complete for non-interactive-SZK….Pages 784-795
Randomness spaces….Pages 796-807
Totality, definability and boolean circuits….Pages 808-819
Quantum counting….Pages 820-831
On the complexity of deriving score functions from examples for problems in molecular biology….Pages 832-843
A hierarchy of equivalences for asynchronous calculi….Pages 844-855
On asynchrony in name-passing calculi….Pages 856-867
Protection in programming-language translations….Pages 868-883
Efficient simulations by queue machines….Pages 884-895
Power of cooperation and multihead finite systems….Pages 896-907
A simple solution to type specialization….Pages 908-917
Multi-stage programming: axiomatization and type safety….Pages 918-929