| 1985 | About Rational Sets of Factors of a Bi-Infinite Word. | Danile Beauquier, Maurice Nivat |
| 1985 | Infinite Streams and Finite Observations in the Semantics of Uniform Concurrency. | J. W. de Bakker, John-Jules Ch. Meyer, Ernst-Rdiger Olderog |
| 1985 | Towards a Uniform Topological Treatment of Streams and Functions on Streams. | J. W. de Bakker, Joost N. Kok |
| 1984 | Sampling Algorithms for Differential Batch Retrieval Problems (Extended Abstract). | Dan E. Willard |
| 1984 | Encoding Graphs by Derivations and Implications for the Theory of Graph Grammars. | Emo Welzl |
| 1984 | Computational Complexity of an Optical Disk Interface (Extended Abstract). | Jeffrey Scott Vitter |
| 1984 | The Simple Roots of Real-Time Computation Hierarchies (Preliminary Version). | Paul M. B. Vitnyi |
| 1984 | AVL-Trees for Localized Search. | Athanasios K. Tsakalidis |
| 1984 | The Propositional Mu-Calculus is Elementary. | Robert S. Streett, E. Allen Emerson |
| 1984 | Node Weighted Matching. | Thomas H. Spencer, Ernst W. Mayr |
| 1984 | Robust Algorithms: A Different Approach to Oracles. | Uwe Schning |
| 1984 | Factorization of Univariate Integer Polynomials by Diophantine Aproximation and an Improved Basis Reduction Algorithm. | Arnold Schnhage |
| 1984 | The VLSI Revolution in Theoretical Circles. | Arnold L. Rosenberg |
| 1984 | A Hardware Implementation of the CSP Primitives and its Verification. | Dorit Ron, Flavia Rosemberg, Amir Pnueli |
| 1984 | Cancellation, Pumping and Permutation in Formal Languages. | Antonio Restivo, Christophe Reutenauer |
| 1984 | Partial Order Semantics versus Interleaving Semantics for CSP-like Languages and its Impact on Fairness. | Wolfgang Reisig |
| 1984 | Probabilistic Bidding Gives Optimal Distributed Resource Allocation. | John H. Reif, Paul G. Spirakis |
| 1984 | Automates Boustrophendon, Semi-Groupe de Birget et Monoide Inversiv Libre (Abstract/ Rsum). | Jean-Pierre Pcuchet |
| 1984 | Complexit des Facteurs des Mots Infinis Engendrs par Morphimes Itrs. | Jean-Jacques Pansiot |
| 1984 | A Linear Time Algorithm to Solve the Single Function Coarsest Partition Problem. | Robert Paige, Robert Endre Tarjan |
| 1984 | Area-Time Optimal VLSI Integer Multiplier with Minimum Computation Time. | Kurt Mehlhorn, Franco P. Preparata |
| 1984 | Languages and Inverse Semigroups. | Stuart W. Margolis, Jean-Eric Pin |
| 1984 | Measures of Presortedness and Optimal Sorting Algorithms (Extended Abstract). | Heikki Mannila |
| 1984 | Performance Analysis of Shamir's Attack on the Basic Merkle-Hellman Knapsack Cryptosystem. | J. C. Lagarias |
| 1984 | Recursion Depth Analysis for Specail Tree Traversal Algorithms. | Peter Kirschenhofer, Helmut Prodinger |