Automata, Languages and Programming: 24th International Colloquium, ICALP ’97 Bologna, Italy, July 7–11, 1997 Proceedings

Robin Milner (auth.), Pierpaolo Degano, Roberto Gorrieri, Alberto Marchetti-Spaccamela (eds.)3540631658, 9783540631651

This book constitutes the refereed proceedings of the 24th International Colloquium on Automata, Languages and Programming, ICALP ’97, held in Bologna, Italy, in July 1997. ICALP ’97 celebrated the 25th anniversary of the European Association for Theoretical Computer Science (EATCS), which has sponsored the ICALP meetings since 1972.
The volume presents 73 revised full papers selected from a total of 197 submissions. Also included are six invited contributions. ICALP is one of the few flagship conferences in the area. The book addresses all current topics in theoretical computer science.

---

Table of contents :
Graphical calculi for interaction….Pages 1-1
NP-completeness: A retrospective….Pages 2-6
The LEDA platform for combinatorial and geometric computing….Pages 7-16
The Wadge-Wagner hierarchy of ω-rational sets….Pages 17-35
From chaotic iteration to constraint propagation….Pages 36-55
DNA 2 DNA computations: A potential “killer app”?….Pages 56-64
Tilings and quasiperiodicity….Pages 65-75
Enumerative sequences of leaves in rational trees….Pages 76-86
A completion algorithm for codes with bounded synchronization delay….Pages 87-97
The expressibility of languages and relations by word equations….Pages 98-109
Finite loops recognize exactly the regular open languages….Pages 110-120
An abstract data type for real numbers….Pages 121-131
Recursive computational depth….Pages 132-142
Some bounds on the computational power of piecewise constant derivative systems (extended abstract)….Pages 143-153
Monadic simultaneous rigid E -unification and related problems….Pages 154-165
Computability on the probability measures on the Borel sets of the unit interval….Pages 166-176
Worst-case hardness suffices for derandomization: A new method for hardness-randomness trade-offs….Pages 177-187
Results on resource-bounded measure….Pages 188-194
Randomization and nondeterminism are comparable for ordered read-once branching programs….Pages 195-202
Checking properties of polynomials….Pages 203-213
Exact analysis of Dodgson elections: Lewis Carroll’s 1876 voting system is complete for parallel access to NP….Pages 214-224
Game theoretic analysis of call-by-value computation….Pages 225-236
On modular properties of higher order extensional lambda calculi….Pages 237-247
On explicit substitutions and names (extended abstract)….Pages 248-258
On the dynamics of sharing graphs….Pages 259-269
Minimizing diameters of dynamic trees….Pages 270-280
Improving spanning trees by upgrading nodes….Pages 281-291
Dynamic algorithms for graphs of bounded treewidth….Pages 292-302
The name discipline of uniform receptiveness (extended abstract)….Pages 303-313
On confluence in the π -calculus….Pages 314-324
A proof theoretical approach to communication….Pages 325-335
Solving trace equations using lexicographical normal forms….Pages 336-346
Star-free picture expressions are strictly weaker than first-order logic….Pages 347-357
An algebra-based method to associate rewards with EMPA terms….Pages 358-368
A semantics preserving actor translation….Pages 369-378
Periodic and non-periodic min-max equations….Pages 379-389
Efficient parallel graph algorithms for coarse grained multicomputers and BSP….Pages 390-400
Upper bound on the communication complexity of private information retrieval….Pages 401-407
Computation paths logic: An expressive, yet elementary, process logic….Pages 408-418
Model checking the full modal mu-calculus for infinite sequential processes….Pages 419-429
Symbolic model checking for probabilistic processes….Pages 430-440
On the concentration of the height of binary search trees….Pages 441-448
An improved master theorem for divide-and-conquer recurrences….Pages 449-459
Bisimulation for probabilistic transition systems: A coalgebraic approach….Pages 460-470
Distributed processes and location failures….Pages 471-481
Basic observables for processes….Pages 482-492
Constrained bipartite edge coloring with applications to wavelength routing….Pages 493-504
Colouring paths in directed symmetric trees with applications to WDM routing….Pages 505-515
On-line routing in all-optical networks….Pages 516-526
A complete characterization of the path layout construction problem for ATM networks with given hop count and load….Pages 527-537
Efficiency of asynchronous systems and read arcs in petri nets….Pages 538-548
Bisimulation equivalence is decidable for one-counter processes….Pages 549-559
Symbolic reachability analysis of FIFO-channel systems with nonregular sets of configurations….Pages 560-570
Axiomatizations for the perpetual loop in process algebra….Pages 571-581
Discrete-time control for rectangular hybrid automata….Pages 582-593
Maintaining minimum spanning trees in dynamic graphs….Pages 594-604
Efficient splitting and merging algorithms for order decomposable problems….Pages 605-615
Efficient array partitioning….Pages 616-626
Constructive linear time algorithms for branchwidth….Pages 627-637
The word matching problem is undecidable for finite special string-rewriting systems that are confluent….Pages 638-648
The geometry of orthogonal reduction spaces….Pages 649-659
The theory of vaccines….Pages 660-670
The equivalence problem for deterministic pushdown automata is decidable….Pages 671-681
On recognizable and rational formal power series in partially commuting variables….Pages 682-692
On a conjecture of J. Shallit….Pages 693-704
On characterizations of escrow encryption schemes….Pages 705-715
Randomness-efficient non-interactive zero knowledge….Pages 716-726
Approximation results for the optimum cost chromatic partition problem….Pages 727-737
The minimum color sum of bipartite graphs….Pages 738-748
A primal-dual approach to approximation of node-deletion problems for matroidal properties….Pages 749-759
Independent sets in asteroidal triple-free graphs….Pages 760-770
Refining and compressing abstract domains….Pages 771-781
Labelled reductions, runtime errors, and operational subsumption….Pages 782-793
A complete and efficiently computable topological classification of D-dimensional linear cellular automata over Z m ….Pages 794-804
Recognizability equals definability for partial k -paths….Pages 805-815
Molecular computing, bounded nondeterminism, and efficient recursion….Pages 816-826
Constructing big trees from short sequences….Pages 827-837
Termination of constraint logic programs….Pages 838-848
The expressive power of unique total stable model semantics….Pages 849-859