18. ICALP 1991: Madrid, Spain

Javier Leach Albert, Burkhard Monien, Mario Rodríguez-Artalejo (Eds.): Automata, Languages and Programming, 18th International Colloquium, ICALP91, Madrid, Spain, July 8-12, 1991, Proceedings. Lecture Notes in Computer Science 510 Springer 1991, ISBN 3-540-54233-7

Logic Programming

Antonio Bucciarelli, Thomas Ehrhard:
Extensional Embedding of a Strongly Stable Model of PCF. 35-46
Christine Ernoult, Alan Mycroft:
Uniform Ideals and Strictness Analysis. 47-59
Val Tannen, Ramesh Subrahmanyam:
Logical and Computational Aspects of Programming with Sets/Bags/Lists. 60-75

Ahmed Bouajjani, Jean-Claude Fernandez, Susanne Graf, Carlos Rodriguez, Joseph Sifakis:
Safety for Branching Time Semantics. 76-92
Limor Fix, Nissim Francez, Orna Grumberg:
Program Composition and Modular Verification. 93-114
Rajeev Alur, Costas Courcoubetis, David L. Dill:
Model-Checking for Probabilistic Real-Time Systems (Extended Abstract). 115-126
Rance Cleaveland, Bernhard Steffen:
Computing Behavioural Relations, Logically. 127-138

Yosi Ben-Asher, David Peleg, R. Ramaswami, Assaf Schuster:
The POwer of Reconfiguration. 139-150
Jean-Denis Fouks:
General Resolution of Tseitin Formulas is Hard. 151-162
Sampath Kannan, Andrew Chi-Chih Yao:
Program Checkers for Probability Generation. 163-173
Janis Kaneps, Rusins Freivalds:
Running Time to Recognize Nonregular Languages by 2-Way Probabilistic Automata. 174-185

Rafael Casas, Josep Díaz, Conrado Martinez:
Static on Random Trees. 186-203
Kim Guldstrand Larsen:
The Expressive Power of Implicit Specifications. 204-216
Wang Yi:
CCS + Time = An Interleaving Model for Real Time Systems. 217-228

Volker Diekert, Edward Ochmanski, Klaus Reinhardt:
On Confluent Semi-Commutations - Decidability and Complexity Results. 229-241
Gérard Duchamp, Daniel Krob:
Lazard's Factorizations of Free Partially Commutative Monoids. 242-253
Paul Gastin, Antoine Petit, Wieslaw Zielonka:
A Kleene Theorem for Infinite Trace Languages. 254-266

Nachum Dershowitz:
Cononical Sets of Horn Clauses. 267-278
Klaus Madlener, Paliath Narendran, Friedrich Otto:
A Specialized Completion Procedure for Monadic String-Rewriting Systems Presenting Groups. 279-290
Pierre-Louis Curien, Roberto Di Cosmo:
A Concluent Reduction for the Lambda-Calculus with Surjective Pairing and Terminal Object. 291-302
Tim Fernando:
Provably Recursive Programs and Program Extraction. 303-313

Thomas Lengauer, Dirk Theune:
Efficient Algorithms for Path Problems with Gernal Cost Citeria. 314-326
Hristo Djidjev, Grammati E. Pantziou, Christos D. Zaroliagis:
Computing Shortest Paths and Distances in Planar Graphs. 327-338
Zvi Galil, Giuseppe F. Italiano:
Maintaining Biconnected Components of Dynamic Planar Graphs. 339-350
Martin Loebl:
Efficient Maximal Cubic Graph Cuts (Extended Abstract). 351-362

Uzi Vishkin:
Strutural Parallel Algorithmics. 363-380
Desh Ranjan, Suresh Chari, Pankaj Rohatgi:
Improving Known Solutions is Hard. 381-392
Lane A. Hemachandra, Albrecht Hoene:
Collapsing Degrees via Strong Computation (Extended Abstract). 393-404

Torben Hagerup:
Fast Parallel Generation of Random Permutations. 405-416
Hermann Jung, Maria J. Serna, Paul G. Spirakis:
A Parallel Algorithm for Two Processors Precedence Constraint Scheduling. 417-428
Martin Fürer:
An Efficient NC Algorithm for Finding Hamiltonian Cycles in Dense Directed Graphs. 429-440

Wolfgang Thomas:
On Logics, Tilings, and Automata. 441-454
Jean-Pierre Jouannaud, Mitsuhiro Okada:
Satisfiability of Systems of Ordinal Notations with the Subterm Property is Decidable. 455-468
Hubert Comon:
Complete Axiomatizations of Some Quotient Term Algebras. 469-480

Roland N. Bol, Jan Friso Groote:
The Meaning of Negative Premises in Transition System Specifications. 481-494
Walter Vogler:
Deciding History Preserving Bisimilarity. 495-505
Luca Aceto, Matthew Hennessy:
Adding Action Refinement to a Finite Process Algebra. 506-519

Dario Bini, Luca Gemignani, Victor Y. Pan:
Improved Parallel Computations with Matrices and Polynomials. 520-531
Jens Lagergren, Stefan Arnborg:
Finding Minimal Forbidden Minors Using a Finite Congruence. 532-543
Hans L. Bodlaender, Ton Kloks:
Better Algorithms for the Pathwidth and Treewidth of Graphs. 544-555
Felipe Cucker, A. Torrecillas:
Two P-Complete Problems in the Theory of the Reals. 556-565

Juha Honkala, Arto Salomaa:
L Morphisms: Bounded Delay and Regularity of Ambiguity. 566-574
Véronique Bruyère, Clelia de Felice:
Degree and Decomposability of Variable-Length Codes. 575-587
Thomas Wilke:
An Eilenberg Theorem for Infinity-Languages. 588-599
Karel Culik II, Simant Dube:
Balancing Order and Chaos in Image Generation (Extended Abstract). 600-614

Yuri Gurevich:
Average Case Complexity. 615-628
Tao Jiang, Bala Ravikumar:
Minimal NFA Problems Are Hard. 629-640
Kosaburo Hashiguchi:
Algorithms for Determining the Smallest Number of Nonterminals (States) Sufficient for Generating (Accepting) a Regular Language. 641-648

Binay K. Bhattacharya, Godfried T. Toussaint:
Computing Shortest Transversals. 649-660
Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas J. Guibas, John Hershberger, Micha Sharir, Jack Snoeyink:
Ray Shooting in Polygons Using Geodesic Triangulations. 661-646
Marshall W. Bern, David Eppstein, F. Frances Yao:
The Expected Extremes in a Delaunay Triangulation. 674-685

Bernard Chazelle:
Computational Geometry for the Gourmet: Old Fare and New Dishes. 686-696
Pavol Duris, Zvi Galil:
On the Power of Multiple Reads in a Chip. 697-706
Hans Dietmar Gröger, György Turán:
On Linear Decision Trees Computing Boolean Functions. 707-718

Zvi Galil, Oded Margalit:
An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem. 719-727
Samir Khuller, Stephen G. Mitchell, Vijay V. Vazirani:
On-Line Algorithms for Weighted Bipartite Matching and Stable Marriages. 728-738
Moni Naor:
String Matching with Preprocessing of Text and Pattern. 739-750
R. Ravi, Ajit Agrawal, Philip N. Klein:
Ordering Problems Approximated: Single-Processor Scheduling and Interval Graph Completion. 751-762