Automata, Languages and Programming: 17th International Colloquium Warwick University, England, July 16–20, 1990 Proceedings

Stefan Näher, Kurt Mehlhorn (auth.), Michael S. Paterson (eds.)3540528261, 9783540528265

This volume contains the proceedings of ICALP 90, the International Colloquium on Automata, Languages and Programming sponsored by the European Association for Theoretical Computer Science (EATCS). This annual conference series covers all important areas of theoretical computer science, such as computability, automata, formal languages, analysis of algorithms, computational complexity, data types and data structures, theory of data bases and knowledge bases, semantics of programming languages, program specification, transformation and verification, foundations of logic programming, theory of logical design and layout, parallel and distributed computation, theory of concurrency, symbolic and algebraic computation, term rewriting systems, computational geometry, cryptography, and theory of robotics. This volume contains five invited papers and 52 papers selected from 250 submitted.

---

Table of contents :
LEDA: A library of efficient data types and algorithms….Pages 1-5
A new universal class of hash functions and dynamic hashing in real time….Pages 6-19
A complete and decidable proof system for call-by-value equalities….Pages 20-31
Static correctness of hierarchical procedures….Pages 32-45
Generic terms having no polymorphic types….Pages 46-59
A complete system of B-rational identities….Pages 60-73
On non-counting regular classes….Pages 74-87
Two-way automata with multiplicity….Pages 88-102
ω-Continuous semirings, algebraic systems and pushdown automata….Pages 103-110
Nondeterministic computations in sublogarithmic space and space constructibility….Pages 111-124
Normalizing and accelerating RAM computations and the problem of reasonable space measures….Pages 125-138
A formal study of learning via queries….Pages 139-152
Language learning by a “team”….Pages 153-166
Functions as processes….Pages 167-180
A domain-theoretic model for a higher-order process calculus….Pages 181-194
Concurrency, automata and domains….Pages 195-208
A theory of communicating processes with value-passing….Pages 209-219
Analytic variations on the common subexpression problem….Pages 220-234
Can a maximum flow be computed in o ( nm ) time?….Pages 235-248
On the distributional complexity of disjointness….Pages 249-253
Computing boolean functions on anonymous networks….Pages 254-267
On the composition of zero-knowledge proof systems….Pages 268-282
Additional queries to random and pseudorandom oracles….Pages 283-293
Communication among relations….Pages 294-307
Stability and sequentiality in dataflow networks….Pages 308-321
Automata for modeling real-time systems….Pages 322-335
Markov decision processes and regular events….Pages 336-349
Term rewriting systems from Church-Rosser to Knuth-Bendix and beyond….Pages 350-369
Nonoblivious normalization algorithms for nonlinear rewrite systems….Pages 370-385
Algebraic properties of idempotent substitutions….Pages 386-399
Determining the separation of preprocessed polyhedra — A unified approach….Pages 400-413
Randomized incremental construction of delaunay and Voronoi diagrams….Pages 414-431
Merging free trees in parallel for efficient voronoi diagram construction….Pages 432-445
Local optimization and the Traveling Salesman Problem….Pages 446-461
Polynomial-time approximation algorithms for the ising model….Pages 462-475
On parallelizing graph-partitioning heuristics….Pages 476-489
Iterated substitutions and locally catenative systems: a decidability result in the binary case….Pages 490-500
Decomposition of partial commutations….Pages 501-511
Boolean closure and unambiguity of rational sets….Pages 512-525
Compositionality through an operational semantics of contexts….Pages 526-539
Structural and behavioural equivalences of networks….Pages 540-552
Proving partial order liveness properties….Pages 553-571
A proof system for the parallel object-oriented language POOL….Pages 572-585
A new approach to maximum matching in general graphs….Pages 586-597
On-line graph algorithms with SPQR-trees….Pages 598-611
On the bit-complexity of discrete solutions of PDEs: Compact multigrid….Pages 612-625
An efficient algorithm for branching bisimulation and stuttering equivalence….Pages 626-638
Partial evaluation, self-application and types….Pages 639-659
Provable computable functions on abstract data types….Pages 660-673
Equational formulas in order-sorted algebras….Pages 674-688
An input-size/output-size trade-off in the time-complexity of rectilinear hidden surface removal….Pages 689-702
Approximation of convex polygons….Pages 703-716
On the rectilinear art gallery problem….Pages 717-728
On parallel hashing and integer sorting….Pages 729-743
The parallel simplicity of compaction and chaining….Pages 744-751
The importance of the left merge operator in process algebras….Pages 752-764
Operational and algebraic semantics for facile: A symmetric integration of concurrent and functional programming….Pages 765-780