Automata, Languages and Programming: 18th International Colloquium Madrid, Spain, July 8–12, 1991 Proceedings

Maurizio Gabbrielli, Giorgio Levi (auth.), Javier Leach Albert, Burkhard Monien, Mario Rodríguez Artalejo (eds.)3540542337, 9783540542339

This volume contains the proceedings of ICALP ’91, the 18th annual summer conference sponsored by the European Association for Theoretical Computer Science (EATCS). ICALP stands for International Colloquium on Automata, Languages, and Programming, and this conference series covers all important areas of theoretical computer science, such as: computability, automata, formal languages, data types and structures, theory of databases and knowledge bases, semantics of programming languages, program specification, transformation and verification, foundations of logic and functional 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.

---

Table of contents :
On the semantics of logic programs….Pages 1-19
Logic programming with recurrence domains….Pages 20-34
Extensional embedding of a strongly stable model of PCF….Pages 35-46
Uniform ideals and strictness analysis….Pages 47-59
Logical and computational aspects of programming with sets/bags/lists….Pages 60-75
Safety for branching time semantics….Pages 76-92
Program composition and modular verification….Pages 93-114
Model-checking for probabilistic real-time systems….Pages 115-126
Computing behavioural relations, logically….Pages 127-138
The power of reconfiguration….Pages 139-150
General resolution of tseitin formulas is hard….Pages 151-162
Program checkers for probability generation….Pages 163-173
Running time to recognize nonregular languages by 2-way probabilistic automata….Pages 174-185
Statistics on random trees….Pages 186-203
The expressive power of implicit specifications….Pages 204-216
CCS + time = an interleaving model for real time systems….Pages 217-228
On confluent semi-commutations — Decidability and complexity results….Pages 229-241
Lazard’s factorizations of free partially commutative monoids….Pages 242-253
A Kleene theorem for infinite trace languages….Pages 254-266
Canonical sets of horn clauses….Pages 267-278
A specialized completion procedure for monadic string-rewriting systems presenting groups….Pages 279-290
A confluent reduction for the λ-calculus with surjective pairing and terminal object….Pages 291-302
Provably recursive programs and program extraction….Pages 303-313
Efficient algorithms for path problems with general cost criteria….Pages 314-326
Computing shortest paths and distances in planar graphs….Pages 327-338
Maintaining biconnected components of dynamic planar graphs….Pages 339-350
Efficient maximal cubic graph cuts….Pages 351-362
Structural parallel algorithmics….Pages 363-380
Improving known solutions is hard….Pages 381-392
Collapsing degrees via strong computation….Pages 393-404
Fast parallel generation of random permutations….Pages 405-416
A parallel algorithm for two processors precedence constraint scheduling….Pages 417-428
An efficient NC algorithm for finding Hamiltonian cycles in dense directed graphs….Pages 429-440
On logics, tilings, and automata….Pages 441-454
Satisfiability of systems of ordinal notations with the subterm property is decidable….Pages 455-468
Complete axiomatizations of some quotient term algebras….Pages 469-480
The meaning of negative premises in transition system specifications….Pages 481-494
Deciding history preserving bisimilarity….Pages 495-505
Adding action refinement to a finite process algebra….Pages 506-519
Improved parallel computations with matrices and polynomials….Pages 520-531
Finding minimal forbidden minors using a finite congruence….Pages 532-543
Better algorithms for the pathwidth and treewidth of graphs….Pages 544-555
Two P-complete problems in the theory of the reals….Pages 556-565
L morphisms: Bounded delay and regularity of ambiguity….Pages 566-574
Degree and decomposability of variable-length codes….Pages 575-587
An EILENBERG theorem for ∞-languages….Pages 588-599
Balancing order and chaos in image generation….Pages 600-614
Average case complexity….Pages 615-628
Minimal NFA problems are hard….Pages 629-640
Algorithms for determining the smallest number of nonterminals (states) sufficient for generating (accepting) a regular language….Pages 641-648
Computing shortest transversals….Pages 649-660
Ray shooting in polygons using geodesic triangulations….Pages 661-673
The expected extremes in a delaunay triangulation….Pages 674-685
Computational geometry for the gourmet old fare and new dishes….Pages 686-696
On the power of multiple reads in a chip….Pages 697-706
On linear decision trees computing Boolean functions….Pages 707-718
An almost linear-time algorithm for the dense subset-sum problem….Pages 719-727
On-line algorithms for weighted bipartite matching and stable marriages….Pages 728-738
String matching with preprocessing of text and pattern….Pages 739-750
Ordering problems approximated: single-processor scheduling and interval graph completion….Pages 751-762