| 1989 | A Logic for Nondeterministic Functional Programs (Extended Abstract). Ana Gil-Luezas |
| 1989 | About Connections Between Syntactical and Computational Complexity. Jean-Luc Coquidé, Max Dauchet, Sophie Tison |
| 1989 | About a Family of Binary Morphisms which Stationary Words are Sturmian. Patrice Séébold |
| 1989 | An Extended Framework for Default Reasoning. M. A. Nait Abdallah |
| 1989 | Analysis of Compact 0-Complete Trees: A New Access Method to Large Databases. Ratko Orlandic, John L. Pfaltz |
| 1989 | Approximation Algorithms for Channel Assignment in Cellular Radio Networks. Hans Ulrich Simon |
| 1989 | Completeness in Approximation Classes. Pierluigi Crescenzi, Alessandro Panconesi |
| 1989 | Complexity Classes with Complete Problems Between P and NP-C. Carme Àlvarez, Josep Díaz, Jacobo Torán |
| 1989 | Complexity of Formula Classes in First Order Logic with Functions. Erich Grädel |
| 1989 | Constructivity, Computability, and Computational Complexity in Analysis. Klaus Weihrauch |
| 1989 | Context-Free NCE Graph Grammars. Joost Engelfriet |
| 1989 | Decision Problems and Coxeter Groups. Bernd Graw |
| 1989 | Descriptive and Computational Complexity. Neil Immerman |
| 1989 | Dynamic Data Structures with Finite Population: A Combinatorial Analysis. Jean Françon, B. Randrianarimanana, René Schott |
| 1989 | Extensional Properties of Sets of Time Bounded Complexity (Extended Abstract). Wolfgang Maass, Theodore A. Slaman |
| 1989 | Fundamentals of Computation Theory, International Conference FCT'89, Szeged, Hungary, August 21-25, 1989, Proceedings János Csirik, János Demetrovics, Ferenc Gécseg |
| 1989 | Generalized Boolean Hierarchies and Boolean Hierarchies Over RP (Conference Abstract). Alberto Bertoni, Danilo Bruschi, Deborah Joseph, Meera Sitharam, Paul Young |
| 1989 | Inducibility of the Composition of Frontier-to-Root Tree Transformations. Tibor Kovács |
| 1989 | Interpretations of Synchronous Flowchart Schemes. Miklós Bartha |
| 1989 | Iterated Deterministic Top-Down Look-Ahead. Zoltán Fülöp, Sándor Vágvölgyi |
| 1989 | Kolmogorov Complexity and Hausdorff Dimension. Ludwig Staiger |
| 1989 | Learning Under Uniform Distribution. Alberto Marchetti-Spaccamela, Marco Protasi |
| 1989 | Logic Programming of Some Mathematical Paradoxes. M. A. Nait Abdallah |
| 1989 | Monte-Carlo Inference and Its Relations to Reliable Frequency Identification. Efim B. Kinber, Thomas Zeugmann |
| 1989 | New Simulations between CRCW PRAMs. Bogdan S. Chlebus, Krzysztof Diks, Torben Hagerup, Tomasz Radzik |
| 1989 | Normal and Sinkless Petri Nets. Rodney R. Howell, Louis E. Rosier, Hsu-Chun Yen |
| 1989 | On Oblivious Branching Programs of Linear Length (Extended Abstract). Matthias Krause, Stephan Waack |
| 1989 | On Product Hierarchies of Automata. Pál Dömösi, Zoltán Ésik, Balázs Imreh |
| 1989 | On Restricted Boolean Circuits. György Turán |
| 1989 | On Word Equations and Makanin's Algorithm. Habib Abdulrab, Jean-Pierre Pécuchet |
| 1989 | On the Communication Complexity of Planarity. Pavol Duris, Pavel Pudlák |
| 1989 | On the Finite Degree of Ambiguity of Finite Tree Automata. Helmut Seidl |
| 1989 | Parallel General Prefix Computations with Geometric, Algebraic and Other Applications. Frederick N. Springsteel, Ivan Stojmenovic |
| 1989 | Rank of Rational Finitely Generated W-Languages. Igor Litovsky |
| 1989 | Recent Developments in the Design of Asynchronous Circuits. Janusz A. Brzozowski, Jo C. Ebergen |
| 1989 | Representation of Recursively Enumerable Languages Using Alternating Finite Tree Recognizers. Kai Salomaa |
| 1989 | Semilinear Real-Time Systolic Trellis Automata. Ivan Korec |
| 1989 | Separating Completely Complexity Classes Related to Polynomial Size Omega-Decision Trees. Carsten Damm, Christoph Meinel |
| 1989 | Some Time-Space Bounds for One-Tape Deterministic Turing Machines. Maciej Liskiewicz, Krzysztof Lorys |
| 1989 | The Borel Hierarchy is Infinite in the Class of Regular Sets of Trees. Jerzy Skurczynski |
| 1989 | The Complexity of Connectivity Problems on Context-Free Graph Languages (Extended Abstract). Egon Wanke |
| 1989 | The Computational Complexity of Cellular Automata. Klaus Sutner |
| 1989 | The Distributed Bit Complexity of the Ring: From the Anonymous to the Non-anonymous Case. Hans L. Bodlaender, Shlomo Moran, Manfred K. Warmuth |
| 1989 | The Effect of Null-Chains on the Complexity of Contact Schemes. Stasys Jukna |
| 1989 | The Equational Logic of Iterative Processes. Stephen L. Bloom |
| 1989 | The Jump Number Problem for Biconvex Graphs and Rectangle Covers of Rectangular Regions. Andreas Brandstädt |
| 1989 | Tree Language Problems in Pattern Recognition Theory (Extended Abstract). Magnus Steinby |
| 1989 | Using Generating Functions to Compute Concurrency. Dominique Geniet, Loÿs Thimonier |