| 1989 | Efficient Text Searching of Regular Expressions (Extended Abstract). | Ricardo A. Baeza-Yates, Gaston H. Gonnet |
| 1989 | Lower Bounds for the Low Hierarchy (Extended Abstract). | Eric Allender, Lane A. Hemachandra |
| 1989 | Limitations of the Upward Separation Technique (Preliminary Version). | Eric Allender |
| 1989 | Realizable and Unrealizable Specifications of Reactive Systems. | Martn Abadi, Leslie Lamport, Pierre Wolper |
| 1988 | Outer Narrowing for Equational Theories Based on Constructors. | Jia-Huai You |
| 1988 | Semantics for Logic Programs without Occur Check. | W. P. Weijland |
| 1988 | On ≤ | Osamu Watanabe |
| 1988 | On Restricting the Access to an NP-Oracle. | Klaus W. Wagner |
| 1988 | Pfaffian Orientations, 0/1 Permanents, and Even Cycles in Directed Graphs. | Vijay V. Vazirani, Mihalis Yannakakis |
| 1988 | The Equivalence of DGSM Replications on Q-Rational Languages is Decidable. | Paavo Turakainen |
| 1988 | Some Behavioural Aspects of Net Theory. | P. S. Thiagarajan |
| 1988 | Type Inference with Partial Types. | Satish Thatte |
| 1988 | Assertional Verification of a Timer Based Protocol. | Gerard Tel |
| 1988 | Invertibility of Linear Finite Automata Over a Ring. | Ren-ji Tao |
| 1988 | Separating Polynomial-Time Turing and Truth-Table Reductions by Tally Sets. | Shouwen Tang, Ronald V. Book |
| 1988 | A Dynamic Data Structure for Planar Graph Embedding (Extended Abstract). | Roberto Tamassia |
| 1988 | regular Languages Defined with Generalized Quantifiers. | Howard Straubing, Denis Thrien, Wolfgang Thomas |
| 1988 | La Reconnaissance des Facteurs d'un Language Fini dans un Texte en Temps Lineaire (Resume). | Jean-Claude Spehner |
| 1988 | On Minimum Flow and Transitive Reduction. | Klaus Simon |
| 1988 | A Kleene-Presburgerian Approach to Linear Production Systems. | Jrgen Schfer |
| 1988 | Optimal Circuits and Transitive Automorphism Groups. | Steven Rudich, Leonard Berman |
| 1988 | Moving Discs Between Polygons. | Hans Rohnert |
| 1988 | Nonlinear Pattern Matching in Trees. | R. Ramesh, I. V. Ramakrishnan |
| 1988 | Nested Annealing: A Provable Improvement to Simulated Annealing. | Sanguthevar Rajasekaran, John H. Reif |
| 1988 | Computations, Residuals, and the POwer of Indeterminancy. | Prakash Panangaden, Eugene W. Stark |