14. ICALP 1987: Karlsruhe, Germany

Inductive Inference, Logic and Functional Programming

• Leonard Pitt, Carl H. Smith:
  Probability and Plurality for Aggregations of Learning Machines. 1-10
  
• M. A. Nait Abdallah:
  Logic Programming with Ions. 11-20
  
• Peter Dybjer:
  Inverse Image Analysis. 21-30
  

Rewrite Systems

• Steffen Hölldobler:
  A Unification Algorithms for Confluent Theories. 31-41
  
• Volker Diekert:
  On the Knuth-Bendix Completion for Concurrent Processes. 42-53
  
• Jieh Hsiang, Michaël Rusinowitch:
  On Word Problems in Equational Theories. 54-71
  

Semantics, Concurrency

• R. K. Shyamasundar, K. T. Narayana, Toniann Pitassi:
  Semantics for Nondeterministic Asynchronous Broadcast Networks. 72-83
  
• Jos C. M. Baeten, Rob J. van Glabbeek:
  Another Look at Abstraction in Process Algebra (Extended Abstract). 84-94
  
• Rob Gerth, Andy Boucher:
  A Timed Failures Model for Extended Communicating Processes. 95-114
  
• Susanne Graf, Joseph Sifakis:
  Readiness Semantics for Regular Processes with Silent Actions. 115-125
  
• Kim Guldstrand Larsen, Robin Milner:
  Verifying a Protocol Using Relativized Bisimulation. 126-135
  

Formal Languages and Automata

• Juhani Karhumäki:
  On Recent Trends in Formal Language Theory. 136-162
  
• David A. Mix Barrington, Denis Thérien:
  Non-Uniform Automata Over Groups. 163-173
  
• Danièle Beauquier:
  Minimal Automaton of a Rational Cover. 174-189
  
• Christian Choffrut, Christine Duboc:
  A Star-Height Problem in Free Monoids with Partial Communications. 190-201
  
• J. Howard Johnson:
  Single-Valued Finite Transduction. 202-211
  
• Werner Kuich:
  The Kleene and the Parikh Theorem in Complete Semirings. 212-225
  
• Yves Métivier:
  An Algorithm for Computing Asynchronous Automata in the Case of Acyclic Non-Commutation Graphs. 226-236
  
• Jean-Eric Pin:
  On the Language Accepted by Finite Reversible Automata. 237-249
  
• IJsbrand Jan Aalbersberg, Hendrik Jan Hoogeboom:
  Decision Problems for Regular Trace Languages. 250-259
  
• Michal Chytil, Jirí Demner:
  Panic Mode without Panic. 260-268
  

Temporal Logic, Concurrent Systems

• Thilo Hafer, Wolfgang Thomas:
  Computation Tree Logic CTL* and Path Quantifiers in the Monadic Theory of the Binary Tree. 269-279
  
• Bernhard Josko:
  Modelchecking of CTL Formulae under Liveness Assumptions. 280-289
  
• Kamal Lodaya, P. S. Thiagarajan:
  A Modal Logic for a Subclass of Event Structures. 290-303
  

Parallel and Distributed Computing

• Torben Hagerup, Marek Chrobak, Krzysztof Diks:
  Parallel 5-Colouring of Planar Graphs. 304-313
  
• Gad M. Landau, Baruch Schieber, Uzi Vishkin:
  Parallel Construction of a Suffix Tree (Extended Abstract). 314-325
  
• Ming Li, Yaacov Yesha:
  The Probabilistic and Deterministic Parallel Complexity of Symmetric Functions. 326-335
  
• R. Ramesh, Rakesh M. Verma, Krishnaprasad Thirunarayan, I. V. Ramakrishnan:
  Term Matching on Parallel Computers. 336-346
  
• Jan van Leeuwen, Nicola Santoro, Jorge Urrutia, Shmuel Zaks:
  Guessing Games and Distributed Computations in Synchronous Networks. 347-356
  

Algorithms and Complexity

• Jacob T. Schwartz, Micha Sharir:
  On the Bivariate Function Minimization Problem And Its Applications to Motion Planning. 357-363
  
• Herbert Edelsbrunner, Günter Rote, Emo Welzl:
  Testing the Necklace Condition for Shortest Tours and Optimal Factors in the Plane. 364-375
  
• Christos Levcopoulos, Andrzej Lingas, Jörg-Rüdiger Sack:
  Nearly Optimal Heuristics for Binary Search Trees with Geometric Generalizations (Extended Abstract). 376-385
  
• Azaria Paz, Claus-Peter Schnorr:
  Approximating Integer Lattices by Lattices with Cyclic Factor Groups. 386-393
  
• Jin-yi Cai, Gabriele E. Meyer:
  On the Complexity of Graph Critical Uncolorability. 394-403
  
• Giorgio Gambosi, Jaroslav Nesetril, Maurizio Talamo:
  Posets, Boolean Representations and Quick Path Searching. 404-424
  
• Satoru Miyano:
  The Lexicographically First Maximal Subgraph Problems: P-Completeness and NC Algorithms. 425-434
  
• Norbert Th. Müller:
  Uniform Computational Complexity of Taylor Series. 435-444
  
• Alberto Marchetti-Spaccamela, Carlo Vercellis:
  Efficient On-Line Algorithms for the Knapsack Problem (Extended Abstract). 445-456
  
• Martin Dietzfelbinger:
  Lower Bounds for Sorting of Sums. 457-466
  
• Alok Aggarwal, Jeffrey Scott Vitter:
  The I/O Complexity of Sorting and Related Problems (Extended Abstract). 467-478
  
• Kurt Mehlhorn, Stefan Näher, Helmut Alt:
  A Lower Bound for the Complexity of the Union-Split-Find Problem. 479-488
  
• Athanasios K. Tsakalidis:
  The Nearest Common Ancestor in a Dynamic Tree. 489-498
  

Petri Nets, Algebraic Specification

• Alain Finkel:
  A Generalization of the Procedure of Karp and Miller to Well Structured Transition Systems. 499-508
  
• Rodney R. Howell, Louis E. Rosier:
  Completeness Rules for Reachability, Containment, and Equivalence, with Respect to Conflict-Free Vector Replacement Systems. 509-520
  
• Hans-Jörg Kreowski:
  Partial Algebras Flow From Algebraic Specifications. 521-530
  

Complexity

• Klaus-Jörn Lange, Birgit Jenner, Bernd Kirsig:
  The Logarithmic Alternation Hierarchiy Collapses: A Sigma^C_2 = A Pi^C_2. 531-541
  
• Martin Beaudry:
  Testing Membership in Commutative Transformation Semigroups. 542-549
  
• Oscar H. Ibarra, Tao Jiang:
  On the Computing Power of One-Way Cellular Arrays. 550-562
  

Invited Lecture

• Leslie G. Valiant:
  Recent Developments in the Theory of Learning (Abstract). 563