| 1989 | Proving Correctness of Constructor Implementations. | Jordi Farrs-Casals |
| 1989 | Logical Characterizations of Nonmonotonic TMSs. | Charles Elkan |
| 1989 | Optimal Parallel Algorithms For The Recognition And Colouring Outerplanar Graphs (Extended Abstract). | Krzysztof Diks, Torben Hagerup, Wojciech Rytter |
| 1989 | On the Power of Synchronization in Parallel Computations. | Jrgen Dassow, Juraj Hromkovic, Juhani Karhumki, Branislav Rovan, Anna Slobodov |
| 1989 | Monadic Second-Order Logic and Context-Free Graph-Grammars. | Bruno Courcelle |
| 1989 | Parallel Complexity of Lexicographically First Order Problems for Tree-Structured Graphs (Extended Abstract). | Bogdan S. Chlebus, Krzysztof Diks, Wojciech Rytter, Tomasz Szymacha |
| 1989 | Concurrent Nondeterministic Processes: Adequacy of Structure and Behaviour. | Ludmila Cherkasova, Vadim E. Kotov |
| 1989 | Ehrenfeucht Test Set Theorem and Hilbert Basis Theorem: A Constructive Glimpse. | Cristian Calude, Dragos Vaida |
| 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 | Oracle Branching Programs and Logspace versus P. | David A. Mix Barrington, Pierre McKenzie |
| 1989 | Algebraic Closed Theories. | ric Badouel |
| 1989 | Proof-Theoretic Characterisations of Logic Programs. | James H. Andrews |
| 1989 | On the Strength of Temporal Proofs. | Hajnal Andrka, Istvn Nmeti, Ildik Sain |
| 1989 | From Specification Languages to Specification Knowledge Bases: The PTO Approach. | Valery N. Agafonov |
| 1989 | On Comparing Probabilistic and Deterministic Automata Complexity of Languages. | Farid M. Ablayev |
| 1988 | Reusable Specification Components. | Martin Wirsing, Rolf Hennicker, Ruth Breu |
| 1988 | A Decomposition Theorem for Finite-Valued Tranducers and an Application to the Equivalence Problem. | Andreas Weber |
| 1988 | Failures Semantics and Deadlocking of Modular Petri Nets. | Walter Vogler |
| 1988 | Bisections of Free Monoids and a New Unavoidable Regularity. | Stefano Varricchio |
| 1988 | Classes of CNF-Formulas with Backtracking Trees of Exponential or Linear Average Order for Exact-Satisfiability. | Ewald Speckenmeyer |
| 1988 | On the Power of Communication in Alternating Machines. | Anna Slobodov |
| 1988 | Recognizable Sets with Multiplicities in the Tropical Semiring. | Imre Simon |
| 1988 | Robust Orale Machines. | Uwe Schning |
| 1988 | Random Boolean Formulas Representing any Boolean Function with Asymptotically Equal Probability (Extended Abstract). | Petr Savick |
| 1988 | An Almost Linear Robinson Unification ALgorithm. | Peter Ruzicka, Igor Prvara |