16. ICALP 1989: Stresa, Italy

• Martín Abadi, Leslie Lamport, Pierre Wolper:
  Realizable and Unrealizable Specifications of Reactive Systems. 1-17
  
• Eric Allender:
  Limitations of the Upward Separation Technique (Preliminary Version). 18-30
  
• Eric Allender, Lane A. Hemachandra:
  Lower Bounds for the Low Hierarchy (Extended Abstract). 31-45
  
• Ricardo A. Baeza-Yates, Gaston H. Gonnet:
  Efficient Text Searching of Regular Expressions (Extended Abstract). 46-62
  
• Danièle Beauquier, Jean-Eric Pin:
  Factors of Words. 63-79
  
• Piotr Berman, Juan A. Garay:
  Asymptotically Optimal Distributed Consensus (Extended Abstract). 80-94
  
• Gianfranco Bilardi, Abha Moitra:
  Time Lower Bounds For CREW-PRAM Computation Of Monotone Functions. 95-107
  
• Corrado Böhm:
  Subduing Self-Application. 108-122
  
• Gilles Brassard, Claude Crépeau, Moti Yung:
  Everything in NP can be Argued in Perfect Zero-Knowledge in a Bounded Number of Rounds. 123-136
  
• Val Tannen, Jean H. Gallier:
  Polymorphic Rewriting Conserves Algebraic Strong Normalization and Confluence. 137-150
  
• Véronique Bruyère:
  Completion of Finite Codes with Finite Deciphering Delay. 151-163
  
• Felice Cardone:
  Relational Semantics for Recursive Types and Bounded Quantification. 164-178
  
• Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir:
  A Singly-Expenential Stratification Scheme for Real Semi-Algebraic Varieties and Its Applications. 179-193
  
• Loïc Colson:
  About Primitive Recursive Algorithms. 194-206
  
• Bruno Courcelle:
  The Definability of Equational Graphs in Monadic Second-Order Logic. 207-221
  
• Karel Culik II, Tero Harju:
  Dominoes and the Regularity of DNS Splicing Languages. 222-233
  
• Philippe Darondeau, Pierpaolo Degano:
  Causal Trees. 234-248
  
• Nachum Dershowitz, Stéphane Kaplan, David A. Plaisted:
  Infinite Normal Forms (Preliminary Version). 249-262
  
• Hartmut Ehrig, Peter Pepper, Fernando Orejas:
  On Recent Trends in Algebraic Specification. 263-288
  
• Joost Engelfriet, Hendrik Jan Hoogeboom:
  Automata with Storage on Infinite Words. 289-303
  
• David Eppstein, Zvi Galil:
  Parallel Algorithmic Techniques for Combinatorial Computation. 304-318
  
• David Feldman, Russell Impagliazzo, Moni Naor, Noam Nisan, Steven Rudich, Adi Shamir:
  On Dice and Coins: Models of Computation for Random Generation. 319-340
  
• Paul Feldman, Silvio Micali:
  An Optimal Probabilistic Algorithm For Synchronous Byzantine Agreement. 341-378
  
• Donald S. Fussell, Vijaya Ramachandran, Ramakrishna Thurimella:
  Finding Triconnected Components by Local Replacements. 379-393
  
• Zvi Galil, Kunsoo Park:
  An Improved Algorithm for Approximate String Matching. 394-404
  
• Giorgio Gambosi, Enrico Nardelli, Maurizio Talamo:
  A Pointer-Free Data Structure for Merging Heaps and Min-Max Heaps. 405-422
  
• Jan Friso Groote, Frits W. Vaandrager:
  Structural Operational Semantics and Bisimulation as a Congruence (Extended Abstract). 423-438
  
• Torben Hagerup, Manfred Nowak:
  Parallel Retrieval of Scattered Information. 439-450
  
• Johan Håstad:
  Tensor Rank is NP-Complete. 451-460
  
• Dorit S. Hochbaum, J. George Shanthikumar:
  The Complexity of Nonlinear Separable Optimization. 461-472
  
• Claire Kenyon-Mathieu, Jeffrey Scott Vitter:
  General Methods for the Analysis of the Maximum Size of Dynamic Data Structures (Extended Abstract). 473-487
  
• Ming Li, Paul M. B. Vitányi:
  How to Share Concurrent Asynchronous Wait-Free Varaibles (Preliminary Version). 488-505
  
• Ming Li, Paul M. B. Vitányi:
  A New Approach to Formal Language Theory by Kolmogorov Complexity (Preliminary Version). 506-520
  
• Guy Louchard, B. Randrianarimanana, René Schott:
  Dynamic Algorithms in D. E. Knuth's Model: A Probabilistic Analysis. 521-533
  
• Zohar Manna, Amir Pnueli:
  Completing the Temporal Picture. 534-558
  
• Yishay Mansour, Baruch Schieber, Prasoon Tiwari:
  Lower Bounds for Computations with the Floor Operation. 559-573
  
• Ian A. Mason, Carolyn L. Talcott:
  Programming, Transforming, and Providing with Function Abstractions and Memories. 574-588
  
• Pierre McKenzie, Denis Thérien:
  Automata Theory Meets Circuit Complexity. 589-602
  
• Kurt Mehlhorn, Wolfgang J. Paul:
  Two Versus One Index Register and Modifiable Versus Non-modifiable Programs. 603-609
  
• Christos H. Papadimitriou, Mihalis Yannakakis:
  Shortest Paths Without a Map. 610-620
  
• Francesco Parisi-Presicce:
  Modular System Design Applying Graph Grammars Techniques. 621-636
  
• Dominique Perrin:
  Partial Commutations. 637-651
  
• Amir Pnueli, Roni Rosner:
  On the Synthesis of an Asynchronous Reactive Module. 652-671
  
• Kirk Pruhs, Udi Manber:
  The Complexity of Controlled Selection. 672-686
  
• Prabhakar Raghavan, Marc Snir:
  Memory Versus Randomization in On-line Algorithms (Extended Abstract). 687-703
  
• John C. Reynolds:
  Syntactic Control of Inference, Part 2. 704-722
  
• Bernhard Steffen:
  Characteristic Formulae. 723-732
  
• Jacobo Torán:
  A Combinatorial Technique for Separating Counting Complexity Classes. 733-744
  
• J. V. Tucker, Jeffery I. Zucker:
  Horn Programs and Semicomputable Relations on Abstract Structures. 745-760
  
• Glynn Winskel:
  A Note on Model Checking the Modal nu-Calculus. 761-772
  
• Guo-Qiang Zhang:
  DI-Domains as Information Systems (Extended Abstract). 773-788