| 1989 | Parallel General Prefix Computations with Geometric, Algebraic and Other Applications. | Frederick N. Springsteel, Ivan Stojmenovic |
| 1989 | The Borel Hierarchy is Infinite in the Class of Regular Sets of Trees. | Jerzy Skurczynski |
| 1989 | Approximation Algorithms for Channel Assignment in Cellular Radio Networks. | Hans Ulrich Simon |
| 1989 | On the Finite Degree of Ambiguity of Finite Tree Automata. | Helmut Seidl |
| 1989 | About a Family of Binary Morphisms which Stationary Words are Sturmian. | Patrice Sbold |
| 1989 | Representation of Recursively Enumerable Languages Using Alternating Finite Tree Recognizers. | Kai Salomaa |
| 1989 | The Effect of Null-Chains on the Complexity of Contact Schemes. | Stasys Jukna |
| 1989 | Analysis of Compact 0-Complete Trees: A New Access Method to Large Databases. | Ratko Orlandic, John L. Pfaltz |
| 1989 | Learning Under Uniform Distribution. | Alberto Marchetti-Spaccamela, Marco Protasi |
| 1989 | Extensional Properties of Sets of Time Bounded Complexity (Extended Abstract). | Wolfgang Maass, Theodore A. Slaman |
| 1989 | Rank of Rational Finitely Generated W-Languages. | Igor Litovsky |
| 1989 | Some Time-Space Bounds for One-Tape Deterministic Turing Machines. | Maciej Liskiewicz, Krzysztof Lorys |
| 1989 | On Oblivious Branching Programs of Linear Length (Extended Abstract). | Matthias Krause, Stephan Waack |
| 1989 | Inducibility of the Composition of Frontier-to-Root Tree Transformations. | Tibor Kovcs |
| 1989 | Semilinear Real-Time Systolic Trellis Automata. | Ivan Korec |
| 1989 | Monte-Carlo Inference and Its Relations to Reliable Frequency Identification. | Efim B. Kinber, Thomas Zeugmann |
| 1989 | Descriptive and Computational Complexity. | Neil Immerman |
| 1989 | Normal and Sinkless Petri Nets. | Rodney R. Howell, Louis E. Rosier, Hsu-Chun Yen |
| 1989 | Decision Problems and Coxeter Groups. | Bernd Graw |
| 1989 | Complexity of Formula Classes in First Order Logic with Functions. | Erich Grdel |
| 1989 | A Logic for Nondeterministic Functional Programs (Extended Abstract). | Ana Gil-Luezas |
| 1989 | Using Generating Functions to Compute Concurrency. | Dominique Geniet, Los Thimonier |
| 1989 | Iterated Deterministic Top-Down Look-Ahead. | Zoltn Flp, Sndor Vgvlgyi |
| 1989 | Dynamic Data Structures with Finite Population: A Combinatorial Analysis. | Jean Franon, B. Randrianarimanana, Ren Schott |
| 1989 | Context-Free NCE Graph Grammars. | Joost Engelfriet |