| 1989 | Chain Properties of Rule Closures. | Miki Hermann |
| 1989 | Observational Implementations. | Rolf Hennicker |
| 1989 | Time-Optimal Simulations of Networks by Universal Parallel Computers. | Friedhelm Meyer auf der Heide, Rolf Wanka |
| 1989 | Computing Minimum Spanning Forests on 1- and 2-Dimensional Processor Arrays. | Friedhelm Meyer auf der Heide |
| 1989 | On Genuinely Time Bounded Compuations. | Friedhelm Meyer auf der Heide |
| 1989 | Polynomial Graph-Colorings. | Wolfgang Gutjahr, Emo Welzl, Gerhard J. Woeginger |
| 1989 | Complete Problems and Strong Polynomial Reducibilities. | K. Ganesan, Steven Homer |
| 1989 | Successive Approximation in Parallel Graph Algorithms. | Donald S. Fussell, Ramakrishna Thurimella |
| 1989 | Linear Numeration Systems, Theta-Developments and Finite Automata. | Christiane Frougny |
| 1989 | Fault Masking Probabilities with Single and Multiple Signature Analysis. | Jrgen Doenhardt |
| 1989 | An O(n log n) Algorithm for Computing a Link Center in a Simple Polygon. | Hristo N. Djidjev, Andrzej Lingas, Jrg-Rdiger Sack |
| 1989 | Word Problems over TRaces Which are Solvable in Linear Time. | Volker Diekert |
| 1989 | On the Equivalence Problem for Deterministic Multitape Automata and Transducers. | Karel Culk II, Juhani Karhumki |
| 1989 | Measure of Parallelism of Distributed Computations. | Bernadette Charron-Bost |
| 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 | On the Power of Parity Polynomial Time. | Jin-yi Cai, Lane A. Hemachandra |
| 1989 | Reversals and Alternation. | Gerhard Buntrock, Albrecht Hoene |
| 1989 | Properties of Infinite Words: Recent Result. | Jean Berstel |
| 1989 | On the Complexity of Approximating the Independent Set Problem. | Piotr Berman, Georg Schnitger |
| 1989 | Testing Membership: Beyond Permutation Groups (Extended Abstract). | Martin Beaudry, Pierre McKenzie, Denis Thrien |
| 1989 | Distributed Computing on TRansitive Networks: The Thorus. | Paul Beame, Hans L. Bodlaender |
| 1989 | The Query Topology in Logic Programming. | Ada Batarekh, V. S. Subrahmanian |
| 1989 | On the Boundary of a Union of Rays. | Panagiotis Alevizos, Jean-Daniel Boissonnat, Franco P. Preparata |
| 1988 | PLEXUS: A System for Implementing Hierarchical Graph Algorithms. | Egon Wanke |
| 1988 | An Automatic Speed-up of Random Access Machines with Powerful Arithmetic Instructions. | Ingolf Wald |