| 1989 | Pushdown Automata on Infinite Trees and Omega-Kleene closure of Context-Free Tree Sets. | Ahmed Saoudi |
| 1989 | Knuth-Morris-Pratt Algorithm: An Analysis. | Mireille Rgnier |
| 1989 | Characterization of Recognizable Trace Languages by Distributed Automata (Extended Abstract). | Antoine Petit |
| 1989 | An Extended Herbrand Theorem for First-Order Theories with Equality Interpreted in Partial Algebras. | Uwe Petermann |
| 1989 | Logically Defined Subsets of N | Pierre Pladeau |
| 1989 | Area Complexity of Merging. | Vladimir Palko, Ondrej Skora, Imrich Vrto |
| 1989 | Correctness of Concurrent Processes. | Ernst-Rdiger Olderog |
| 1989 | Generalizing Singly-Linked List Reorganizing Heuristics for Doubly-Linked Lists. | David T. H. Ng, B. John Oommen |
| 1989 | Pomset Semantics for True Concurrency with Synchronization and Recursion (Extended Abstract). | John-Jules Ch. Meyer, Erik P. de Vink |
| 1989 | Switching Graphs and Their Complexity. | Christoph Meinel |
| 1989 | LEDA: A Library of Efficient Data Types and Algorithms. | Kurt Mehlhorn, Stefan Nher |
| 1989 | Concurrency, Modularity, and Synchronization. | Antoni W. Mazurkiewicz |
| 1989 | On the Nature of TELLUS (a Typed Equational Logic Look over Uniform Specification). | Vincenzo Manca, Antonino Salibra, Giuseppe Scollo |
| 1989 | Complexity of Decision Problems Under Incomplete Information. | Wojciech Kowalczyk |
| 1989 | An Iterative Metric Fully Abstract Semantics for Nondeterministic Dataflow (Extended Abstract). | Joost N. Kok |
| 1989 | Integer Relations Among Algebraic Numbers. | Bettina Just |
| 1989 | Memory and Algebra. | C. Jousselin, J.-P. Moskowitz |
| 1989 | Testing Approximate Symmetry in the Plane is NP-hard. | Sebastian Iwanowski |
| 1989 | Pinwheel Scheduling With Tow Distinct Numbers. | Robert Holte, Louis E. Rosier, Igor Tulchinsky, Donald A. Varvel |
| 1989 | Generalized Definite Tree Languages. | Uschi Heuter |
| 1989 | Polynomial-Time Functions Generate SAT: On P-Splinters. | Lane A. Hemachandra, Albrecht Hoene, Dirk Siefkes |
| 1989 | Space Bounded Computations: Review And New Separation Results. | Juris Hartmanis, Desh Ranjan |
| 1989 | A Thesis for Bounded Concurrency. | David Harel |
| 1989 | System Simulation and the Sensitivity of Self-Stabilization. | Mohamed G. Gouda, Rodney R. Howell, Louis E. Rosier |
| 1989 | Equivalence Notions for Concurrent Systems and Refinement of Actions (Extended Abstract). | Rob J. van Glabbeek, Ursula Goltz |