Automata, Languages and Programming

Proceedings 1990 of ICALP, the established conference series on Automata, Languages and Programming. The selected contributions cover all important areas of theoretical computer science.

Inhalt
LEDA: A library of efficient data types and algorithms.- A new universal class of hash functions and dynamic hashing in real time.- A complete and decidable proof system for call-by-value equalities.- Static correctness of hierarchical procedures.- Generic terms having no polymorphic types.- A complete system of B-rational identities.- On non-counting regular classes.- Two-way automata with multiplicity.- ?-Continuous semirings, algebraic systems and pushdown automata.- Nondeterministic computations in sublogarithmic space and space constructibility.- Normalizing and accelerating RAM computations and the problem of reasonable space measures.- A formal study of learning via queries.- Language learning by a team.- Functions as processes.- A domain-theoretic model for a higher-order process calculus.- Concurrency, automata and domains.- A theory of communicating processes with value-passing.- Analytic variations on the common subexpression problem.- Can a maximum flow be computed in o(nm) time?.- On the distributional complexity of disjointness.- Computing boolean functions on anonymous networks.- On the composition of zero-knowledge proof systems.- Additional queries to random and pseudorandom oracles.- Communication among relations.- Stability and sequentiality in dataflow networks.- Automata for modeling real-time systems.- Markov decision processes and regular events.- Term rewriting systems from Church-Rosser to Knuth-Bendix and beyond.- Nonoblivious normalization algorithms for nonlinear rewrite systems.- Algebraic properties of idempotent substitutions.- Determining the separation of preprocessed polyhedra A unified approach.- Randomized incremental construction of delaunay and Voronoi diagrams.- Merging free trees in parallel for efficient voronoidiagram construction.- Local optimization and the Traveling Salesman Problem.- Polynomial-time approximation algorithms for the ising model.- On parallelizing graph-partitioning heuristics.- Iterated substitutions and locally catenative systems: a decidability result in the binary case.- Decomposition of partial commutations.- Boolean closure and unambiguity of rational sets.- Compositionality through an operational semantics of contexts.- Structural and behavioural equivalences of networks.- Proving partial order liveness properties.- A proof system for the parallel object-oriented language POOL.- A new approach to maximum matching in general graphs.- On-line graph algorithms with SPQR-trees.- On the bit-complexity of discrete solutions of PDEs: Compact multigrid.- An efficient algorithm for branching bisimulation and stuttering equivalence.- Partial evaluation, self-application and types.- Provable computable functions on abstract data types.- Equational formulas in order-sorted algebras.- An input-size/output-size trade-off in the time-complexity of rectilinear hidden surface removal.- Approximation of convex polygons.- On the rectilinear art gallery problem.- On parallel hashing and integer sorting.- The parallel simplicity of compaction and chaining.- The importance of the left merge operator in process algebras.- Operational and algebraic semantics for facile: A symmetric integration of concurrent and functional programming.