| 1989 | A Coloring Algorithm for Interval Graphs. Maciej Slusarek |
| 1989 | A Thesis for Bounded Concurrency. David Harel |
| 1989 | Algebraic Closed Theories. Éric Badouel |
| 1989 | An Extended Herbrand Theorem for First-Order Theories with Equality Interpreted in Partial Algebras. Uwe Petermann |
| 1989 | An Imperative Type Hierarchy with Partial Products. Erik Meineche Schmidt, Michael I. Schwartzbach |
| 1989 | An Iterative Metric Fully Abstract Semantics for Nondeterministic Dataflow (Extended Abstract). Joost N. Kok |
| 1989 | Area Complexity of Merging. Vladimir Palko, Ondrej Sýkora, Imrich Vrto |
| 1989 | Characterization of Recognizable Trace Languages by Distributed Automata (Extended Abstract). Antoine Petit |
| 1989 | Complexity of Decision Problems Under Incomplete Information. Wojciech Kowalczyk |
| 1989 | Concurrency, Modularity, and Synchronization. Antoni W. Mazurkiewicz |
| 1989 | Concurrent Nondeterministic Processes: Adequacy of Structure and Behaviour. Ludmila Cherkasova, Vadim E. Kotov |
| 1989 | Constructive Aspects of the Omega-Rule: Application to Proof Systems in Computer Science and Algorithmic Logic. Serge Yoccoz |
| 1989 | Control Flow versus Logic: A Denotational and a Declarative Model for Guarded Horn Clauses. Frank S. de Boer, Joost N. Kok, Catuscia Palamidessi, Jan J. M. M. Rutten |
| 1989 | Correctness of Concurrent Processes. Ernst-Rüdiger Olderog |
| 1989 | Ehrenfeucht Test Set Theorem and Hilbert Basis Theorem: A Constructive Glimpse. Cristian Calude, Dragos Vaida |
| 1989 | Equivalence Notions for Concurrent Systems and Refinement of Actions (Extended Abstract). Rob J. van Glabbeek, Ursula Goltz |
| 1989 | Finite Constants: Characterizations of a New Decidable Set of Constants. Bernhard Steffen, Jens Knoop |
| 1989 | From Specification Languages to Specification Knowledge Bases: The PTO Approach. Valery N. Agafonov |
| 1989 | Generalized Definite Tree Languages. Uschi Heuter |
| 1989 | Generalizing Singly-Linked List Reorganizing Heuristics for Doubly-Linked Lists. David T. H. Ng, B. John Oommen |
| 1989 | How to Define Functionals of Free Structures in Typed Lambda Calculus. Marek Zaionc |
| 1989 | Integer Relations Among Algebraic Numbers. Bettina Just |
| 1989 | Knuth-Morris-Pratt Algorithm: An Analysis. Mireille Régnier |
| 1989 | LEDA: A Library of Efficient Data Types and Algorithms. Kurt Mehlhorn, Stefan Näher |
| 1989 | Logical Characterizations of Nonmonotonic TMSs. Charles Elkan |
| 1989 | Logically Defined Subsets of N Pierre Péladeau |
| 1989 | Mathematical Foundations of Computer Science 1989, MFCS'89, Porabka-Kozubnik, Poland, August 28 - September 1, 1989, Proceedings Antoni Kreczmar, Grazyna Mirkowska |
| 1989 | Memory and Algebra. C. Jousselin, J.-P. Moskowitz |
| 1989 | Monadic Second-Order Logic and Context-Free Graph-Grammars. Bruno Courcelle |
| 1989 | On Comparing Probabilistic and Deterministic Automata Complexity of Languages. Farid M. Ablayev |
| 1989 | On Varieties of Languages Closed Under Products with Counter. Pascal Weil |
| 1989 | On the Computational Efficiency of Symmetric Neural Networks. Juraj Wiedermann |
| 1989 | On the Length of Values in a Finite Transducer. Andreas Weber |
| 1989 | On the Nature of TELLUS (a Typed Equational Logic Look over Uniform Specification). Vincenzo Manca, Antonino Salibra, Giuseppe Scollo |
| 1989 | On the Power of Synchronization in Parallel Computations. Jürgen Dassow, Juraj Hromkovic, Juhani Karhumäki, Branislav Rovan, Anna Slobodová |
| 1989 | On the Strength of Temporal Proofs. Hajnal Andréka, István Németi, Ildikó Sain |
| 1989 | One More Method For Proving Lower Bounds on the Formula Complexity of Boolean Functions. Vladimir Stetsenko |
| 1989 | Optimal Data Flow Analysis via Observational Equivalence. Bernhard Steffen |
| 1989 | Optimal Parallel Algorithms For The Recognition And Colouring Outerplanar Graphs (Extended Abstract). Krzysztof Diks, Torben Hagerup, Wojciech Rytter |
| 1989 | Oracle Branching Programs and Logspace versus P. David A. Mix Barrington, Pierre McKenzie |
| 1989 | Parallel Complexity of Lexicographically First Order Problems for Tree-Structured Graphs (Extended Abstract). Bogdan S. Chlebus, Krzysztof Diks, Wojciech Rytter, Tomasz Szymacha |
| 1989 | Pinwheel Scheduling With Tow Distinct Numbers. Robert Holte, Louis E. Rosier, Igor Tulchinsky, Donald A. Varvel |
| 1989 | Polynomial-Time Functions Generate SAT: On P-Splinters. Lane A. Hemachandra, Albrecht Hoene, Dirk Siefkes |
| 1989 | Pomset Semantics for True Concurrency with Synchronization and Recursion (Extended Abstract). John-Jules Ch. Meyer, Erik P. de Vink |
| 1989 | Proof-Theoretic Characterisations of Logic Programs. James H. Andrews |
| 1989 | Proving Correctness of Constructor Implementations. Jordi Farrés-Casals |
| 1989 | Pushdown Automata on Infinite Trees and Omega-Kleene closure of Context-Free Tree Sets. Ahmed Saoudi |
| 1989 | Space Bounded Computations: Review And New Separation Results. Juris Hartmanis, Desh Ranjan |
| 1989 | Switching Graphs and Their Complexity. Christoph Meinel |
| 1989 | System Simulation and the Sensitivity of Self-Stabilization. Mohamed G. Gouda, Rodney R. Howell, Louis E. Rosier |
| 1989 | Testing Approximate Symmetry in the Plane is NP-hard. Sebastian Iwanowski |
| 1989 | The Hoare-Like Verification System for a Language with an Exception Handling Mechanism. Danuta Szczepanska |
| 1989 | Understanding Nets. Boris A. Trakhtenbrot |