| 1989 | A First Order Logic for Partial Functions (Extended Abstract). Francisca Lucio-Carrasco, Antonio Gavilanes-Franco |
| 1989 | A Generalization of Automatic Sequences. Jeffrey O. Shallit |
| 1989 | A Proof System for Type Theory and CCS. Olov Schelén, Nils-Olof Forsgren |
| 1989 | AMORE: A System for Computing Automata, MOnoids, and Regular Expressions. V. Kell, Albert Maier, Andreas Potthoff, Wolfgang Thomas, U. Wermuth |
| 1989 | AXE: The Syntax Driven Diagram Editor for Visual Languages used in the Software Engineering Environments AxIS. Maria Morandi Cecchi, F. Nachria, O. Viele |
| 1989 | Algebraic Specifications for Domain THeory. Friederike Nickl |
| 1989 | An O(n log n) Algorithm for Computing a Link Center in a Simple Polygon. Hristo N. Djidjev, Andrzej Lingas, Jörg-Rüdiger Sack |
| 1989 | Area Efficient Methods to Increase the Reliability of Combinatorial Circuits. Rüdiger Reischuk, Bernd Schmeltz |
| 1989 | Average Number of Messages for Distributed Leader Finding in Rings of Processors. Christian Lavault |
| 1989 | Chain Properties of Rule Closures. Miki Hermann |
| 1989 | Classes of Picture Languages that Cannot be Distinguished in the Chain Code Concept and Deletion of Redundant Retreats. Friedhelm Hinz |
| 1989 | Complete Problems and Strong Polynomial Reducibilities. K. Ganesan, Steven Homer |
| 1989 | Computing Minimum Spanning Forests on 1- and 2-Dimensional Processor Arrays. Friedhelm Meyer auf der Heide |
| 1989 | Concatenable Segment Trees (Extended Abstract). Marc J. van Kreveld, Mark H. Overmars |
| 1989 | Decidability of Waek Fairness in Petri Nets. Petr Jancar |
| 1989 | Deciding Bisimulation Equivalences for a Class of Non-Finite-State Programs. Bengt Jonsson, Joachim Parrow |
| 1989 | Deciding Equivalence of Finite Tree Automata. Helmut Seidl |
| 1989 | Distributed Computing on TRansitive Networks: The Thorus. Paul Beame, Hans L. Bodlaender |
| 1989 | Dynamic Planar Point Location with Optimal Query Time. Franco P. Preparata, Roberto Tamassia |
| 1989 | Examining the Satisfiability of Formulas of Propositional Dynamic Logic. Tomasz Janowski |
| 1989 | Fault Masking Probabilities with Single and Multiple Signature Analysis. Jürgen Doenhardt |
| 1989 | Graph^Ed: An Interactive Garpg Editor. Michael Himsolt |
| 1989 | If Deterministic and Nondeterministic Space Complexities are Equal for Andrzej Szepietowski |
| 1989 | Implementation of a Transition Sematics for Parallel Programs with Shared Variables. Thomas Wolff |
| 1989 | It is Undecidable Whether the Knuth-Bendix Completion Procedure Generates a Crossed Pair. Paliath Narendran, Jonathan Stillman |
| 1989 | Linear Numeration Systems, Theta-Developments and Finite Automata. Christiane Frougny |
| 1989 | Measure of Parallelism of Distributed Computations. Bernadette Charron-Bost |
| 1989 | Membership in Plynomial Ideals over Q Is Exponential Space Complete. Ernst W. Mayr |
| 1989 | New Results on the Generalized Star-Height Problem. Jean-Eric Pin, Howard Straubing, Denis Thérien |
| 1989 | Observational Implementations. Rolf Hennicker |
| 1989 | On Genuinely Time Bounded Compuations. Friedhelm Meyer auf der Heide |
| 1989 | On the Boundary of a Union of Rays. Panagiotis Alevizos, Jean-Daniel Boissonnat, Franco P. Preparata |
| 1989 | On the Complexity of Approximating the Independent Set Problem. Piotr Berman, Georg Schnitger |
| 1989 | On the Equivalence Problem for Deterministic Multitape Automata and Transducers. Karel Culík II, Juhani Karhumäki |
| 1989 | On the Power of Parity Polynomial Time. Jin-Yi Cai, Lane A. Hemachandra |
| 1989 | Parallel Computation of Discrete Voronoi Diagrams (Extended Abstract). Otfried Schwarzkopf |
| 1989 | Polynomial Graph-Colorings. Wolfgang Gutjahr, Emo Welzl, Gerhard J. Woeginger |
| 1989 | Properties of Infinite Words: Recent Result. Jean Berstel |
| 1989 | Reversals and Alternation. Gerhard Buntrock, Albrecht Hoene |
| 1989 | Rounds versus Time for the Two Person Pebble Game (Extended Abstract). Bala Kalyanasundaram, Georg Schnitger |
| 1989 | SAMPLE: A Language Dependent Prototyping Environment. Michael Jäger |
| 1989 | STACS 89, 6th Annual Symposium on Theoretical Aspects of Computer Science, Paderborn, FRG, February 16-18, 1989, Proceedings Burkhard Monien, Robert Cori |
| 1989 | Shorest Edge-Disjoint Paths in Graphs. Andreas Schwill |
| 1989 | Some Complexity Theoretic Aspects of AC Rewriting. Rakesh M. Verma, I. V. Ramakrishnan |
| 1989 | Successive Approximation in Parallel Graph Algorithms. Donald S. Fussell, Ramakrishna Thurimella |
| 1989 | TIME vs BITS. Mark H. Overmars, Nicola Santoro |
| 1989 | Testing Membership: Beyond Permutation Groups (Extended Abstract). Martin Beaudry, Pierre McKenzie, Denis Thérien |
| 1989 | The Query Topology in Logic Programming. Aïda Batarekh, V. S. Subrahmanian |
| 1989 | Time is Not a Healer. Nicola Santoro, Peter Widmayer |
| 1989 | Time-Optimal Simulations of Networks by Universal Parallel Computers. Friedhelm Meyer auf der Heide, Rolf Wanka |
| 1989 | Unified Algebras and Action Semantics. Peter D. Mosses |
| 1989 | Word Problems over TRaces Which are Solvable in Linear Time. Volker Diekert |