Automata, Languages and Programming: 23rd International Colloquium, ICALP ’96 Paderborn, Germany, July 8–12, 1996 Proceedings

Harald Ganzinger (auth.), Friedhelm Meyer, Burkhard Monien (eds.)3540614400, 9783540614401

This volume constitutes the refereed proceedings of the 23rd International Colloquium on Automata, Languages and Programming (ICALP ’96), held at Paderborn, Germany, in July 1996. ICALP is an annual conference sponsored by the European Association on Theoretical Computer Science (EATCS).
The proceedings contain 52 refereed papers selected from 172 submissions and 4 invited papers. The papers cover the whole range of theoretical computer science; they are organized in sections on: Process Theory; Fairness, Domination, and the u-Calculus; Logic and Algebra; Languages and Processes; Algebraic Complexity; Graph Algorithms; Automata; Complexity Theory; Combinatorics on Words; Algorithms; Lower Bounds; Data Structures…

---

Table of contents :
Saturation-based theorem proving (abstract)….Pages 1-3
Bandwidth efficient parallel computation….Pages 4-23
Variable-length maximal codes….Pages 24-47
Lower bounds for prepositional proofs and independence results in bounded arithmetic….Pages 48-62
Algebraic characterizations of decorated trace equivalences over tree-like structures….Pages 63-74
Fast asynchronous systems in dense time….Pages 75-86
A hierarchy theorem for the μ-calculus….Pages 87-97
An effective tableau system for the linear time μ-calculus….Pages 98-109
Characterizing fairness implementability for multiparty interaction….Pages 110-121
Termination of context-sensitive rewriting by rewriting….Pages 122-133
A complete gentzen-style axiomatization for set constraints….Pages 134-145
Fatal errors in conditional expressions….Pages 146-157
Different types of arrow between logical frameworks….Pages 158-169
Effective models of polymorphism, subtyping and recursion (extended abstract)….Pages 170-181
Regularity for a large class of context-free processes is decidable….Pages 182-193
On infinite transition graphs having a decidable monadic theory….Pages 194-205
Semi-groups acting on context-free graphs….Pages 206-218
Hard sets method and semilinear reservoir method with applications….Pages 219-231
Random polynomials and polynomial factorization….Pages 232-243
Optimal gröbner base algorithms for binomial ideals….Pages 244-255
Minimum fill-in on circle and circular-arc graphs….Pages 256-267
Practical approximation schemes for maximum induced-subgraph problems on K 3,3 -free or K 5 -free graphs….Pages 268-279
Searching a fixed graph….Pages 280-289
Improved sampling with applications to dynamic graph algorithms….Pages 290-299
The expressive power of existential first order sentences of büchi’s sequential calculus….Pages 300-311
Fixpoints for rabin tree automata make complementation easy….Pages 312-323
New upper bounds to the limitedness of distance automata….Pages 324-335
Recognizing regular expressions by means of dataflow networks….Pages 336-347
On the power of randomized branching programs….Pages 348-356
Hitting sets derandomize BPP….Pages 357-368
On type-2 probabilistic quantifiers….Pages 369-380
Speeding-up single-tape nondeterministic computations by single alternation, with separation results….Pages 381-392
On ω-generators and codes….Pages 393-402
On standard Sturmian morphisms….Pages 403-415
Constructions and bounds for visual cryptography….Pages 416-428
On capital investment….Pages 429-441
Lower bounds for static dictionaries on RAMs with bit operations but no multiplication….Pages 442-453
Lower bounds for row minima searching….Pages 454-465
On the complexity of relational problems for finite state processes….Pages 466-477
Deciding finiteness of Petri nets up to bisimulation….Pages 478-489
Mobile processes with a distributed environment….Pages 490-501
The meaning of negative premises in transition system specifications II….Pages 502-513
Average case analyses of list update algorithms, with applications to data compression….Pages 514-525
Self-organizing data structures with dependent accesses….Pages 526-537
Lopsided trees: Analyses, algorithms, and applications….Pages 538-549
Optimal logarithmic time randomized suffix tree construction….Pages 550-561
Improved parallel approximation of a class of integer programming problems….Pages 562-573
Efficient collective communication in optical networks….Pages 574-585
Shared-memory simulations on a faulty-memory DMM….Pages 586-597
Fast deterministic backtrack search….Pages 598-609
Agent rendezvous: A dynamic symmetry-breaking problem….Pages 610-621
Efficient asynchronous consensus with the value-oblivious adversary scheduler….Pages 622-633
A formal framework for evaluating heuristic programs….Pages 634-645
Improved scheduling algorithms for minsum criteria….Pages 646-657
On the complexity of string folding….Pages 658-669
A polynomial-time algorithm for near-perfect phylogeny….Pages 670-680