| 1990 | Two-Way Automata with Multiplicity. | Marcella Anselmo |
| 1990 | Automata For Modeling Real-Time Systems. | Rajeev Alur, David L. Dill |
| 1990 | Approximation of Convex Polygons. | Helmut Alt, Johannes Blmer, Hubert Wagener |
| 1989 | DI-Domains as Information Systems (Extended Abstract). | Guo-Qiang Zhang |
| 1989 | A Note on Model Checking the Modal nu-Calculus. | Glynn Winskel |
| 1989 | Horn Programs and Semicomputable Relations on Abstract Structures. | John V. Tucker, Jeffery I. Zucker |
| 1989 | A Combinatorial Technique for Separating Counting Complexity Classes. | Jacobo Torn |
| 1989 | Polymorphic Rewriting Conserves Algebraic Strong Normalization and Confluence. | Val Tannen, Jean H. Gallier |
| 1989 | Characteristic Formulae. | Bernhard Steffen |
| 1989 | Syntactic Control of Inference, Part 2. | John C. Reynolds |
| 1989 | Memory Versus Randomization in On-line Algorithms (Extended Abstract). | Prabhakar Raghavan, Marc Snir |
| 1989 | The Complexity of Controlled Selection. | Kirk Pruhs, Udi Manber |
| 1989 | On the Synthesis of an Asynchronous Reactive Module. | Amir Pnueli, Roni Rosner |
| 1989 | Partial Commutations. | Dominique Perrin |
| 1989 | Modular System Design Applying Graph Grammars Techniques. | Francesco Parisi-Presicce |
| 1989 | Shortest Paths Without a Map. | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1989 | Two Versus One Index Register and Modifiable Versus Non-modifiable Programs. | Kurt Mehlhorn, Wolfgang J. Paul |
| 1989 | Automata Theory Meets Circuit Complexity. | Pierre McKenzie, Denis Thrien |
| 1989 | Programming, Transforming, and Providing with Function Abstractions and Memories. | Ian A. Mason, Carolyn L. Talcott |
| 1989 | Lower Bounds for Computations with the Floor Operation. | Yishay Mansour, Baruch Schieber, Prasoon Tiwari |
| 1989 | Completing the Temporal Picture. | Zohar Manna, Amir Pnueli |
| 1989 | Dynamic Algorithms in D. E. Knuth's Model: A Probabilistic Analysis. | Guy Louchard, B. Randrianarimanana, Ren Schott |
| 1989 | A New Approach to Formal Language Theory by Kolmogorov Complexity (Preliminary Version). | Ming Li, Paul M. B. Vitnyi |
| 1989 | How to Share Concurrent Asynchronous Wait-Free Varaibles (Preliminary Version). | Ming Li, Paul M. B. Vitnyi |
| 1989 | General Methods for the Analysis of the Maximum Size of Dynamic Data Structures (Extended Abstract). | Claire Kenyon-Mathieu, Jeffrey Scott Vitter |