| 1984 | New Lower Bound for Polyhedral Membership Problem with an Application to Linear Programming. | Jaroslav Morvek, Pavel Pudlk |
| 1984 | Traces, Histories, Graphs: Instances of a Process Monoid. | Antoni W. Mazurkiewicz |
| 1984 | Representations lf Integers and Language Theory. | Aldo de Luca, Antonio Restivo |
| 1984 | Gdel Numberings, Principal Morphisms, Combinatory Algebras: A Category-theoretic Characterization of Functional Completeness. | Giuseppe Longo, Eugenio Moggi |
| 1984 | Limits, Higher Type Computability and Type-Free Languages. | Giuseppe Longo |
| 1984 | Factoring Multivariate Polynomials over Algebraic Number Fields. | Arjen K. Lenstra |
| 1984 | Nondeterministic Logspace Reductions. | Klaus-Jrn Lange |
| 1984 | Finding a Maximum Flow in /S, T/-Planar Network in Linear Expected Time. | Ludek Kucera |
| 1984 | Some Connections between Representability of Complexity Classes and the Power of Formal Systems of Reasoning. | Wojciech Kowalczyk |
| 1984 | On the Equivalence of Compositions of Morphisms and Inverse Morphisms on Regular Languages. | Juhani Karhumki, H. C. M. Kleijn |
| 1984 | A Uniform Independence of Invariant Sentences. | Max I. Kanovic |
| 1984 | Lower Bounds for Polygon Simplicity Testing and Other Problems. | Jerzy W. Jaromczyk |
| 1984 | Thue Systems and the Church-Rosser Property. | Matthias Jantzen |
| 1984 | The Equivalence Problem and Correctness Formulas for a Simple Class of Programs (Extended Abstract). | Oscar H. Ibarra, Louis E. Rosier |
| 1984 | On the Power of Alternation in Finite Automata. | Juraj Hromkovic |
| 1984 | Hierarchy of Reversal and Zerotesting Bounded Multicounter Machines. | Juraj Hromkovic |
| 1984 | Outline of an Algebraic Language Theory. | Gnter Hotz |
| 1984 | A Note on Unique Decipherability. | Christoph M. Hoffmann |
| 1984 | The Power of the Future Perfect in Program Logics. | Matthew Hennessy, Colin Stirling |
| 1984 | On Searching of Special Cases of Mazes and Finite Embedded Graphs. | Armin Hemmerling, Klaus Kriegel |
| 1984 | Process Logics: Two Decidability Results. | Zdzislaw Habasinski |
| 1984 | Systolic Automata - Power, Characterizations, Nonhomogeneity. | Jozef Gruska |
| 1984 | Many-Sorted Temporal Logic for Multi-Processes Systems. | Patrice Enjalbert, Max Michel |
| 1984 | Monotone Edge Sequences in Line Arrangements and Applications (Extended Abstract). | Herbert Edelsbrunner, Emo Welzl |
| 1984 | Propositional Dynamic Logic with Strong Loop Predicate. | Ryszard Danecki |