Full Description
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.
Contents
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.
