| 1989 | A Generalization of Automatic Sequences. | Jeffrey O. Shallit |
| 1989 | Deciding Equivalence of Finite Tree Automata. | Helmut Seidl |
| 1989 | Shorest Edge-Disjoint Paths in Graphs. | Andreas Schwill |
| 1989 | Parallel Computation of Discrete Voronoi Diagrams (Extended Abstract). | Otfried Schwarzkopf |
| 1989 | A Proof System for Type Theory and CCS. | Olov Scheln, Nils-Olof Forsgren |
| 1989 | Time is Not a Healer. | Nicola Santoro, Peter Widmayer |
| 1989 | Area Efficient Methods to Increase the Reliability of Combinatorial Circuits. | Rdiger Reischuk, Bernd Schmeltz |
| 1989 | Dynamic Planar Point Location with Optimal Query Time. | Franco P. Preparata, Roberto Tamassia |
| 1989 | New Results on the Generalized Star-Height Problem. | Jean-Eric Pin, Howard Straubing, Denis Thrien |
| 1989 | TIME vs BITS. | Mark H. Overmars, Nicola Santoro |
| 1989 | Algebraic Specifications for Domain THeory. | Friederike Nickl |
| 1989 | It is Undecidable Whether the Knuth-Bendix Completion Procedure Generates a Crossed Pair. | Paliath Narendran, Jonathan Stillman |
| 1989 | Unified Algebras and Action Semantics. | Peter D. Mosses |
| 1989 | Membership in Plynomial Ideals over Q Is Exponential Space Complete. | Ernst W. Mayr |
| 1989 | A First Order Logic for Partial Functions (Extended Abstract). | Francisca Lucio-Carrasco, Antonio Gavilanes-Franco |
| 1989 | Average Number of Messages for Distributed Leader Finding in Rings of Processors. | Christian Lavault |
| 1989 | Concatenable Segment Trees (Extended Abstract). | Marc J. van Kreveld, Mark H. Overmars |
| 1989 | AMORE: A System for Computing Automata, MOnoids, and Regular Expressions. | V. Kell, Albert Maier, Andreas Potthoff, Wolfgang Thomas, U. Wermuth |
| 1989 | Rounds versus Time for the Two Person Pebble Game (Extended Abstract). | Bala Kalyanasundaram, Georg Schnitger |
| 1989 | Deciding Bisimulation Equivalences for a Class of Non-Finite-State Programs. | Bengt Jonsson, Joachim Parrow |
| 1989 | Examining the Satisfiability of Formulas of Propositional Dynamic Logic. | Tomasz Janowski |
| 1989 | Decidability of Waek Fairness in Petri Nets. | Petr Jancar |
| 1989 | SAMPLE: A Language Dependent Prototyping Environment. | Michael Jger |
| 1989 | Classes of Picture Languages that Cannot be Distinguished in the Chain Code Concept and Deletion of Redundant Retreats. | Friedhelm Hinz |
| 1989 | Graph^Ed: An Interactive Garpg Editor. | Michael Himsolt |