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

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