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

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