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

Manuel Blum (auth.), Andrzej Lingas, Rolf Karlsson, Svante Carlsson (eds.)3540569391, 9783540569398

The International Colloquium on Automata, Languages and Programming (ICALP) is an annual conference series sponsored by the European Association for Theoretical Computer Science (EATCS). It is intended to cover all important areas of theoretical computer science, such as: computability, automata,formal languages, term rewriting, analysis of algorithms, computational geometry, computational complexity, symbolic and algebraic computation, cryptography, data types and data structures, theory of data bases and knowledge bases, semantics of programming languages, program specification, transformation and verification, foundations of logicprogramming, theory of logical design and layout, parallel and distributed computation, theory of concurrency, and theory of robotics. This volume contains the proceedings of ICALP 93, held at LundUniversity, Sweden, in July 1993. It includes five invited papers and 51 contributed papers selected from 151 submissions.

---

Table of contents :
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