15. ICALP 1988: Tampere, Finland

• Alok Aggarwal, Ashok K. Chandra:
  Communication Complexity of PRAMs (Preliminary Version). 1-17
  
• Luc Albert, François Fages:
  Average Case Complexity Analysis of the Rete Multi-Pattern Match Algorithm. 18-37
  
• Stefan Arnborg, Jens Lagergren, Detlef Seese:
  Problems Easy for Tree-Decomposable Graphs (Extended Abstract). 38-51
  
• Ralph-Johan Back, Reino Kurki-Suonio:
  Serializability in Distributed Systems with Handshaking. 52-66
  
• Chandrajit L. Bajaj, Myung-Soo Kim:
  Algorithms for Planar Geometric Models. 67-81
  
• Gyora M. Benedek, Alon Itai:
  Nonuniform Learnability. 82-92
  
• Jean Berstel, Christophe Reutenauer:
  Zeta Functions of Recognizable Languages. 93-104
  
• Hans L. Bodlaender:
  Dynamic Programming on Graphs with Bounded Treewidth. 105-118
  
• Jik H. Chang, Oscar H. Ibarra, Michael A. Palis:
  Efficient Simulations of Simple Models of Parallel Computation by Time-Bounded ATM's and Space-Bounded TM's. 119-132
  
• Richard Cole, Jeffrey S. Salowe, William L. Steiger, Endre Szemerédi:
  Optimal Slope Selection. 133-146
  
• Robert Cori, Yves Métivier:
  Approximation of a TRace, Asynchronous Automata and the Ordering of Events in a Distributed System. 147-161
  
• Karel Culik II:
  New Techniques for Proving the Decidability of Equivalence Problems. 162-175
  
• Volker Diekert:
  Transitive Orientations, Möbius Functions, and Complete Semi-Thue Systems for Free Partially Commutative Monoids. 176-187
  
• Martin Dietzfelbinger, Wolfgang Maass:
  The Complexity of Matrix Transposition on One-Tape Off-Line Turing Machines with Output Tape. 188-200
  
• Herbert Edelsbrunner:
  Geometric Structures in Computational Geometry. 201-213
  
• Herbert Edelsbrunner, Leonidas J. Guibas, János Pach, Richard Pollack, Raimund Seidel, Micha Sharir:
  Arrangements of Curves in the Plane - Topology, Combinatorics, and Algorithms. 214-229
  
• David Eppstein:
  Reset Sequences for Finite Automata with Application to Design of Parts Orienters. 230-238
  
• Philippe Flajolet, Danièle Gardy, Loÿs Thimonier:
  Random Allocations and Probabilistic Languages. 239-253
  
• Jozef Gruska:
  Systolic Architectures, Systems and Computations. 254-270
  
• Juris Hartmanis:
  New Developments in Structural Complexity Theory. 271-286
  
• Claude Kirchner, Hélène Kirchner, José Meseguer:
  Operational Semantics of OBJ-3 (Extended Abstract). 287-301
  
• Peter Kirschenhofer, Helmut Prodinger, Wojciech Szpankowski:
  Do We Really Need to Balance Patricia Trees? (Extended Abstract). 302-316
  
• Joost N. Kok, Jan J. M. M. Rutten:
  Contractions in Comparing Concurrent Semantics. 317-332
  
• Clyde P. Kruskal, Larry Rudolph, Marc Snir:
  A Complexity Theory of Efficient Parallel Algorithms (Extended Abstract). 333-346
  
• Ludek Kucera, Alberto Marchetti-Spaccamela, Marco Protasi:
  On the Learnability of DNF Formulae. 347-361
  
• Clemens Lautemann:
  Efficient Algorithms on Context-Free Graph Grammars. 362-378
  
• Thomas Lengauer, Egon Wanke:
  Efficient Analysis of Graph Properties on Context-free Graph Languages (Extended Abstract). 379-393
  
• Andrzej Lingas, Maciej M. Syslo:
  A Polynomial-Time Algorithm for Subgraph Isomorphism of Two-Connected Series-Parallel Graphs. 394-409
  
• Kurt Mehlhorn, Chee-Keng Yap:
  Constructive Hopf's Theorem: Or How to Untangle Closed Planar Curves. 410-423
  
• Valtteri Niemi:
  Maximal Dense Intervals of Grammar Forms. 424-438
  
• Prakash Panangaden, Eugene W. Stark:
  Computations, Residuals, and the POwer of Indeterminancy. 439-454
  
• Sanguthevar Rajasekaran, John H. Reif:
  Nested Annealing: A Provable Improvement to Simulated Annealing. 455-472
  
• R. Ramesh, I. V. Ramakrishnan:
  Nonlinear Pattern Matching in Trees. 473-488
  
• Ren-ji Tao:
  Invertibility of Linear Finite Automata Over a Ring. 489-501
  
• Hans Rohnert:
  Moving Discs Between Polygons. 502-515
  
• Steven Rudich, Leonard Berman:
  Optimal Circuits and Transitive Automorphism Groups. 516-524
  
• Jürgen Schäfer:
  A Kleene-Presburgerian Approach to Linear Production Systems. 525-534
  
• Klaus Simon:
  On Minimum Flow and Transitive Reduction. 535-546
  
• Jean-Claude Spehner:
  La Reconnaissance des Facteurs d'un Language Fini dans un Texte en Temps Lineaire (Resume). 547-560
  
• Howard Straubing, Denis Thérien, Wolfgang Thomas:
  regular Languages Defined with Generalized Quantifiers. 561-575
  
• Roberto Tamassia:
  A Dynamic Data Structure for Planar Graph Embedding (Extended Abstract). 576-590
  
• Shouwen Tang, Ronald V. Book:
  Separating Polynomial-Time Turing and Truth-Table Reductions by Tally Sets. 591-599
  
• Gerard Tel:
  Assertional Verification of a Timer Based Protocol. 600-614
  
• Satish Thatte:
  Type Inference with Partial Types. 615-629
  
• P. S. Thiagarajan:
  Some Behavioural Aspects of Net Theory. 630-653
  
• Paavo Turakainen:
  The Equivalence of DGSM Replications on Q-Rational Languages is Decidable. 654-666
  
• Vijay V. Vazirani, Mihalis Yannakakis:
  Pfaffian Orientations, 0/1 Permanents, and Even Cycles in Directed Graphs. 667-681
  
• Klaus W. Wagner:
  On Restricting the Access to an NP-Oracle. 682-696
  
• Osamu Watanabe:
  On <=^P_{1-tt}-Sparseness and Nondeterministic Complexity Classes (Extended Abstract). 697-709
• W. P. Weijland:
  Semantics for Logic Programs without Occur Check. 710-726
  
• Jia-Huai You:
  Outer Narrowing for Equational Theories Based on Constructors. 727-741