| 1989 | A Combinatorial Technique for Separating Counting Complexity Classes. Jacobo Torán |
| 1989 | A New Approach to Formal Language Theory by Kolmogorov Complexity (Preliminary Version). Ming Li, Paul M. B. Vitányi |
| 1989 | A Note on Model Checking the Modal nu-Calculus. Glynn Winskel |
| 1989 | A Pointer-Free Data Structure for Merging Heaps and Min-Max Heaps. Giorgio Gambosi, Enrico Nardelli, Maurizio Talamo |
| 1989 | A Singly-Expenential Stratification Scheme for Real Semi-Algebraic Varieties and Its Applications. Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir |
| 1989 | About Primitive Recursive Algorithms. Loïc Colson |
| 1989 | An Improved Algorithm for Approximate String Matching. Zvi Galil, Kunsoo Park |
| 1989 | An Optimal Probabilistic Algorithm For Synchronous Byzantine Agreement. Paul Feldman, Silvio Micali |
| 1989 | Asymptotically Optimal Distributed Consensus (Extended Abstract). Piotr Berman, Juan A. Garay |
| 1989 | Automata Theory Meets Circuit Complexity. Pierre McKenzie, Denis Thérien |
| 1989 | Automata with Storage on Infinite Words. Joost Engelfriet, Hendrik Jan Hoogeboom |
| 1989 | Automata, Languages and Programming, 16th International Colloquium, ICALP89, Stresa, Italy, July 11-15, 1989, Proceedings Giorgio Ausiello, Mariangiola Dezani-Ciancaglini, Simona Ronchi Della Rocca |
| 1989 | Causal Trees. Philippe Darondeau, Pierpaolo Degano |
| 1989 | Characteristic Formulae. Bernhard Steffen |
| 1989 | Completing the Temporal Picture. Zohar Manna, Amir Pnueli |
| 1989 | Completion of Finite Codes with Finite Deciphering Delay. Véronique Bruyère |
| 1989 | DI-Domains as Information Systems (Extended Abstract). Guo-Qiang Zhang |
| 1989 | Dominoes and the Regularity of DNS Splicing Languages. Karel Culík II, Tero Harju |
| 1989 | Dynamic Algorithms in D. E. Knuth's Model: A Probabilistic Analysis. Guy Louchard, B. Randrianarimanana, René Schott |
| 1989 | Efficient Text Searching of Regular Expressions (Extended Abstract). Ricardo A. Baeza-Yates, Gaston H. Gonnet |
| 1989 | Everything in NP can be Argued in Perfect Zero-Knowledge in a Bounded Number of Rounds. Gilles Brassard, Claude Crépeau, Moti Yung |
| 1989 | Factors of Words. Danièle Beauquier, Jean-Eric Pin |
| 1989 | Finding Triconnected Components by Local Replacements. Donald S. Fussell, Vijaya Ramachandran, Ramakrishna Thurimella |
| 1989 | General Methods for the Analysis of the Maximum Size of Dynamic Data Structures (Extended Abstract). Claire Kenyon-Mathieu, Jeffrey Scott Vitter |
| 1989 | Horn Programs and Semicomputable Relations on Abstract Structures. John V. Tucker, Jeffery I. Zucker |
| 1989 | How to Share Concurrent Asynchronous Wait-Free Varaibles (Preliminary Version). Ming Li, Paul M. B. Vitányi |
| 1989 | Infinite Normal Forms (Preliminary Version). Nachum Dershowitz, Stéphane Kaplan, David A. Plaisted |
| 1989 | Limitations of the Upward Separation Technique (Preliminary Version). Eric Allender |
| 1989 | Lower Bounds for Computations with the Floor Operation. Yishay Mansour, Baruch Schieber, Prasoon Tiwari |
| 1989 | Lower Bounds for the Low Hierarchy (Extended Abstract). Eric Allender, Lane A. Hemachandra |
| 1989 | Memory Versus Randomization in On-line Algorithms (Extended Abstract). Prabhakar Raghavan, Marc Snir |
| 1989 | Modular System Design Applying Graph Grammars Techniques. Francesco Parisi-Presicce |
| 1989 | On Dice and Coins: Models of Computation for Random Generation. David Feldman, Russell Impagliazzo, Moni Naor, Noam Nisan, Steven Rudich, Adi Shamir |
| 1989 | On Recent Trends in Algebraic Specification. Hartmut Ehrig, Peter Pepper, Fernando Orejas |
| 1989 | On the Synthesis of an Asynchronous Reactive Module. Amir Pnueli, Roni Rosner |
| 1989 | Parallel Algorithmic Techniques for Combinatorial Computation. David Eppstein, Zvi Galil |
| 1989 | Parallel Retrieval of Scattered Information. Torben Hagerup, Manfred Nowak |
| 1989 | Partial Commutations. Dominique Perrin |
| 1989 | Polymorphic Rewriting Conserves Algebraic Strong Normalization and Confluence. Val Tannen, Jean H. Gallier |
| 1989 | Programming, Transforming, and Providing with Function Abstractions and Memories. Ian A. Mason, Carolyn L. Talcott |
| 1989 | Realizable and Unrealizable Specifications of Reactive Systems. Martín Abadi, Leslie Lamport, Pierre Wolper |
| 1989 | Relational Semantics for Recursive Types and Bounded Quantification. Felice Cardone |
| 1989 | Shortest Paths Without a Map. Christos H. Papadimitriou, Mihalis Yannakakis |
| 1989 | Structural Operational Semantics and Bisimulation as a Congruence (Extended Abstract). Jan Friso Groote, Frits W. Vaandrager |
| 1989 | Subduing Self-Application. Corrado Böhm |
| 1989 | Syntactic Control of Inference, Part 2. John C. Reynolds |
| 1989 | Tensor Rank is NP-Complete. Johan Håstad |
| 1989 | The Complexity of Controlled Selection. Kirk Pruhs, Udi Manber |
| 1989 | The Complexity of Nonlinear Separable Optimization. Dorit S. Hochbaum, J. George Shanthikumar |
| 1989 | The Definability of Equational Graphs in Monadic Second-Order Logic. Bruno Courcelle |
| 1989 | Time Lower Bounds For CREW-PRAM Computation Of Monotone Functions. Gianfranco Bilardi, Abha Moitra |
| 1989 | Two Versus One Index Register and Modifiable Versus Non-modifiable Programs. Kurt Mehlhorn, Wolfgang J. Paul |