| 1984 | A Lower Bound on Complexity of Branching Programs (Extended Abstract). Pavel Pudlák |
| 1984 | A Note on Unique Decipherability. Christoph M. Hoffmann |
| 1984 | A Topological View of Some Problems in Complexity Theory. Michael Sipser |
| 1984 | A Truely Morphic Characterization of Recursively Enumerable Sets. Franz-Josef Brandenburg |
| 1984 | A Uniform Independence of Invariant Sentences. Max I. Kanovic |
| 1984 | Algorithms for String Editing which Permit Arbitrarily Complex Editing Constraints. B. John Oommen |
| 1984 | An Exponential Lower Bound for One-Time-Only Branching Programs. Stanislav Zák |
| 1984 | An Investigation of Controls for Concurrent Systems by Abstract Control Languages. Hans-Dieter Burkhard |
| 1984 | Another Look at Parameterization Using Algebras with Subsorts. Axel Poigné |
| 1984 | Combinatorial Games with Exponential Space Complete Decision Problems. J. M. Robson |
| 1984 | Complexity of Quantifier Elimination in the Theory of Algebraically Closed Fields. Alexander L. Chistov, Dima Grigoriev |
| 1984 | Computability of Probabilistic Parameters for Some Classes of Formal Languages. Joffroy Beauquier, Loÿs Thimonier |
| 1984 | Decidability of Monadic Theories. Alexei L. Semenov |
| 1984 | Decidability of the Equivalence Problem for Synchronous Deterministic Pushdown Automata. A. Sh. Nepomnjashchaja |
| 1984 | Factoring Multivariate Polynomials over Algebraic Number Fields. Arjen K. Lenstra |
| 1984 | Fast Recognition of Pushdown Automaton and Context-Free Languages. Wojciech Rytter |
| 1984 | Finding a Maximum Flow in /S, T/-Planar Network in Linear Expected Time. Ludek Kucera |
| 1984 | Free Constructions in Algebraic Institutions. Andrzej Tarlecki |
| 1984 | From Dynamic Algebras to Test Algebras. Jan Reiterman, Vera Trnková |
| 1984 | Gödel Numberings, Principal Morphisms, Combinatory Algebras: A Category-theoretic Characterization of Functional Completeness. Giuseppe Longo, Eugenio Moggi |
| 1984 | Hierarchy of Reversal and Zerotesting Bounded Multicounter Machines. Juraj Hromkovic |
| 1984 | Limits, Higher Type Computability and Type-Free Languages. Giuseppe Longo |
| 1984 | Lower Bounds for Polygon Simplicity Testing and Other Problems. Jerzy W. Jaromczyk |
| 1984 | Many-Sorted Temporal Logic for Multi-Processes Systems. Patrice Enjalbert, Max Michel |
| 1984 | Mathematical Foundations of Computer Science 1984, Praha, Czechoslovakia, September 3-7, 1984, Proceedings Michal Chytil, Václav Koubek |
| 1984 | Models and Operators for Nondeterministic Processes. Rocco De Nicola |
| 1984 | Monotone Edge Sequences in Line Arrangements and Applications (Extended Abstract). Herbert Edelsbrunner, Emo Welzl |
| 1984 | Multiprocessor Systems and Their Concurrency. Peter H. Starke |
| 1984 | New Lower Bound for Polyhedral Membership Problem with an Application to Linear Programming. Jaroslav Morávek, Pavel Pudlák |
| 1984 | Nondeterminism Is Essential for Two-Way Counter Machines. Marek Chrobak |
| 1984 | Nondeterministic Logspace Reductions. Klaus-Jörn Lange |
| 1984 | On Generalized Words of Thue-Morse. Anton Cerný |
| 1984 | On Searching of Special Cases of Mazes and Finite Embedded Graphs. Armin Hemmerling, Klaus Kriegel |
| 1984 | On the Complexity of Inductive Inference (Preliminary Report). Robert P. Daley, Carl H. Smith |
| 1984 | On the Complexity of Slice Functions. Ingo Wegener |
| 1984 | On the Ehrenfeucht Conjecture on Test Sets and Its Dual Version. Jürgen Albert |
| 1984 | On the Equivalence of Compositions of Morphisms and Inverse Morphisms on Regular Languages. Juhani Karhumäki, H. C. M. Kleijn |
| 1984 | On the Herbrand Kleene Universe for Nondeterministic Computations. Manfred Broy |
| 1984 | On the Power of Alternation in Finite Automata. Juraj Hromkovic |
| 1984 | Outline of an Algebraic Language Theory. Günter Hotz |
| 1984 | Process Logics: Two Decidability Results. Zdzislaw Habasinski |
| 1984 | Propositional Dynamic Logic with Strong Loop Predicate. Ryszard Danecki |
| 1984 | Recent Results on Automata and Infinite Words. Dominique Perrin |
| 1984 | Remarks on Comparing Expressive Power of Logics of Programs. Jerzy Tiuryn, Pawel Urzyczyn |
| 1984 | Representations lf Integers and Language Theory. Aldo de Luca, Antonio Restivo |
| 1984 | Separating, Strongly Separating, and Collapsing Relativized Complexity Classes. José L. Balcázar |
| 1984 | Solving Visibility Problems by Using Skeleton Structures. Thomas Ottmann, Peter Widmayer |
| 1984 | Some Connections between Representability of Complexity Classes and the Power of Formal Systems of Reasoning. Wojciech Kowalczyk |
| 1984 | Sparse Oracles, Lowness, and Highness. José L. Balcázar, Ronald V. Book, Uwe Schöning |
| 1984 | Systolic Automata - Power, Characterizations, Nonhomogeneity. Jozef Gruska |
| 1984 | The Complexity of Problems Concerning Graphs with Regularities (Extended Abstract). Klaus Wagner |
| 1984 | The Equivalence Problem and Correctness Formulas for a Simple Class of Programs (Extended Abstract). Oscar H. Ibarra, Louis E. Rosier |
| 1984 | The Power of the Future Perfect in Program Logics. Matthew Hennessy, Colin Stirling |
| 1984 | The Structure of Polynomial Complexity Cores (Extended Abstract). Pekka Orponen, Uwe Schöning |
| 1984 | Thue Systems and the Church-Rosser Property. Matthias Jantzen |
| 1984 | Traces, Histories, Graphs: Instances of a Process Monoid. Antoni W. Mazurkiewicz |
| 1984 | VLSI Algorithms and Architectures. Franco P. Preparata |
| 1984 | Weak and Strong Fairness in CCS. Gerardo Costa, Colin Stirling |