Automata, Languages and Programming: 20th International Colloquium, ICALP 93 Lund, Sweden, July 5–9, 1993 Proceedings

Program result checking: A new approach to making programs more reliable....Pages 1-14
Dynamic interpolation search in o (log log n ) time....Pages 15-27
Searching among intervals and compact routing tables....Pages 28-39
The approximation of maximum subgraph problems....Pages 40-51
Polynomially bounded minimization problems which are hard to approximate....Pages 52-63
Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover....Pages 64-75
The complexity of approximating PSPACE-complete problems for hierarchical specifications....Pages 76-87
Problems on pairs of trees and the four colour problem of planar graphs....Pages 88-101
Constructing competitive tours from local information....Pages 102-113
Treewidth and pathwidth of permutation graphs....Pages 114-125
A theory of even functionals and their algorithmic applications....Pages 126-136
Exact asymptotics of divide-and-conquer recurrences....Pages 137-149
Optimal bounds for the change-making problem....Pages 150-161
The complexity of N -body simulation....Pages 162-176
A simple method for resolving degeneracies in Delaunay triangulations....Pages 177-188
Fault-tolerance and complexity (Extended abstract)....Pages 189-202
Reversal-space trade-offs for simultaneous resource-bounded nondeterministic Turing machines....Pages 203-214
On the computational power of discrete Hopfield nets....Pages 215-226
On randomized versus deterministic computation....Pages 227-240
Lower bounds for one-way probabilistic communication complexity....Pages 241-252
Maintaining discrete probability distributions optimally....Pages 253-264
Secure and efficient off-line digital money (extended abstract)....Pages 265-276
Computational depth and reducibility....Pages 277-288
Learnability: Admissible, co-finite, and hypersimple languages....Pages 289-300
Inclusion is undecidable for pattern languages....Pages 301-312
New decidability results concerning two-way counter machines and applications....Pages 313-324
Cobham's Theorem seen through Büchi's Theorem....Pages 325-334
Logical definability on infinite traces....Pages 335-346
Algebras for classifying regular tree languages and an application to frontier testability....Pages 347-358
Finite automata as characterizations of minor closed tree families (extended abstract)....Pages 359-370
On distributed algorithms in a broadcast domain....Pages 371-387
Sparse networks supporting efficient reliable broadcasting....Pages 388-397
Strongly adaptive token distribution....Pages 398-409
Fast parallel computation of characteristic polynomials by Leverrier's power sum method adapted to fields of finite characteristic....Pages 410-417
Fast parallel constraint satisfaction....Pages 418-429
The product of rational languages....Pages 430-444
On regular compatibility of semi-commutations....Pages 445-456
Algebraic aspects of B-regular series....Pages 457-468
Products of finite state machines with full coverage....Pages 469-477
An effective version of Stallings' theorem in the case of context-free groups....Pages 478-495
On the power of periodic iteration of morphisms....Pages 496-506
If a DOL language is k-power free then it is circular....Pages 507-518
Deciding true concurrency equivalences on finite safe nets (preliminary report)....Pages 519-531
Timed testing of concurrent systems....Pages 532-543
The fork calculus....Pages 544-557
Extended transition systems for parametric bisimulation....Pages 558-569
Temporal logic and categories of Petri nets....Pages 570-581
Decidability of a partial order based temporal logic....Pages 582-592
Local model checking for context-free processes....Pages 593-605
Computing on structures....Pages 606-620
A partial solution for D -unification based on a reduction to AC 1 -unification....Pages 621-632
Efficient analysis of concurrent constraint logic programs....Pages 633-644
A confluent reduction for the extensional typed λ-calculus with pairs, sums, recursion and terminal object....Pages 645-656
Modularity of termination and confluence in combinations of rewrite systems with λ ω ....Pages 657-668
From domains to automata with concurrency....Pages 669-681
What is a universal higher-order programming language?....Pages 682-695