| 1998 | A (Non-elementary) Modular Decision Procedure for LTrL. Paul Gastin, Raphaël Meyer, Antoine Petit |
| 1998 | A Computational Interpretation of the lambda-µ-Calculus. Gavin M. Bierman |
| 1998 | A Finite Hierarchy of the Recursively Enumerable Real Numbers. Klaus Weihrauch, Xizhong Zheng |
| 1998 | A Parallelization of Dijkstra's Shortest Path Algorithm. Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, Peter Sanders |
| 1998 | A Second Step Towards Circuit Complexity-Theoretic Analogs of Rice's Theorem. Lane A. Hemaspaandra, Jörg Rothe |
| 1998 | A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with At Most (1/6) log log Kazuyuki Amano, Akira Maruoka |
| 1998 | About Synchronization Languages. Isabelle Ryl, Yves Roos, Mireille Clerbout |
| 1998 | Additive Cellular Automata over Z Jacques Mazoyer, Ivan Rapaport |
| 1998 | Approximating Maximum Independent Sets in Uniform Hypergraphs. Thomas Hofmeister, Hanno Lefmann |
| 1998 | Average-Case Intractability vs. Worst-Case Intractability. Johannes Köbler, Rainer Schuler |
| 1998 | Blockwise Variable Orderings for Shared BDDs. Harry Preuß, Anand Srivastav |
| 1998 | Characterization of Sensitive Linear Cellular Automata with Respect to the Counting Distance. Giovanni Manzini |
| 1998 | Combinatorial Hardness Proofs for Polynomial Evaluation. Mikel Aldaz, Joos Heintz, Guillermo Matera, José Luis Montaña, Luis Miguel Pardo |
| 1998 | Communication Complexity and Lower Bounds on Multilective Computations. Juraj Hromkovic |
| 1998 | Comparison Between the Complexity of a Function and the Complexity of Its Graph. Bruno Durand, Sylvain Porrot |
| 1998 | Complete Abstract Interpretations Made Constructive. Roberto Giacobazzi, Francesco Ranzato, Francesca Scozzari |
| 1998 | Computationally-Sound Checkers. Silvio Micali |
| 1998 | Computing epsilon-Free NFA from Regular Expressions in O(n log²(n)) Time. Christian Hagenah, Anca Muscholl |
| 1998 | D0L-Systems and Surface Automorphisms. Luis-Miguel Lopez, Philippe Narbel |
| 1998 | Deadlocking States in Context-Free Process Algebra. Jirí Srba |
| 1998 | Defining the Java Virtual Machine as Platform for Provably Correct Java Compilation. Egon Börger, Wolfram Schulte |
| 1998 | Degree-Preserving Forests. Hajo Broersma, Andreas Huck, Ton Kloks, Otto R. Koppius, Dieter Kratsch, Haiko Müller, Hilde Tuinstra |
| 1998 | Embedding of Hypercubes into Grids. Sergei L. Bezrukov, Joe D. Chavez, L. H. Harper, Markus Röttger, Ulf-Peter Schroeder |
| 1998 | Encoding the Hydra Battle as a Rewrite System. Hélène Touzet |
| 1998 | Equations in Transfinite Strings. Christian Choffrut, Sándor Horváth |
| 1998 | Expressive Completeness of Temporal Logic of Action. Alexander Moshe Rabinovich |
| 1998 | Facial Circuits of Planar Graphs and Context-Free Languages. Bruno Courcelle, Denis Lapoire |
| 1998 | Flow Logic for Imperative Objects. Flemming Nielson, Hanne Riis Nielson |
| 1998 | From Algorithms to Working Programs: On the Use of Program Checking in LEDA. Kurt Mehlhorn, Stefan Näher |
| 1998 | Gaußian Elimination and a Characterization of Algebraic Power Series. Werner Kuich |
| 1998 | Hypergraph Traversal Revisited: Cost Measures and Dynamic Algorithms. Giorgio Ausiello, Giuseppe F. Italiano, Umberto Nanni |
| 1998 | IFS and Control Languages. Henning Fernau, Ludwig Staiger |
| 1998 | Improved Time and Space Hierarchies of One-Tape Off-Line TMs. Kazuo Iwama, Chuzo Iwamoto |
| 1998 | Iterated Length-Preserving Rational Transductions. Michel Latteux, David Simplot, Alain Terlutte |
| 1998 | Lazy Functional Algorithms for Exact Real Functionals. Alex K. Simpson |
| 1998 | Locality of Order-Invariant First-Order Formulas. Martin Grohe, Thomas Schwentick |
| 1998 | Locally Explicit Construction of Rödl's Asymptotically Good Packings. Nikolai N. Kuzjurin |
| 1998 | Mathematical Foundations of Computer Science 1998, 23rd International Symposium, MFCS'98, Brno, Czech Republic, August 24-28, 1998, Proceedings Lubos Brim, Jozef Gruska, Jirí Zlatuska |
| 1998 | Minimal Forbidden Words and Factor Automata. Maxime Crochemore, Filippo Mignosi, Antonio Restivo |
| 1998 | Minimum Propositional Proof Length is NP-Hard to Linearly Approximate. Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi |
| 1998 | Model Checking Real-Time Properties of Symmetric Systems. E. Allen Emerson, Richard J. Trefler |
| 1998 | Modularization and Abstraction: The Keys to Practical Formal Verification. Yonit Kesten, Amir Pnueli |
| 1998 | Nonstochastic Languages as Projections of 2-Tape Quasideterministic Languages. Richard F. Bonner, Rusins Freivalds, Janis Lapins, Antra Lukjanska |
| 1998 | On Boolean vs. Modular Arithmetic for Circuits and Communication Protocols. Carsten Damm |
| 1998 | On Counting AC Andris Ambainis, David A. Mix Barrington, Huong LeThanh |
| 1998 | On Defect Effect of Bi-Infinite Words. Juhani Karhumäki, Ján Manuch, Wojciech Plandowski |
| 1998 | On One-Pass Term Rewriting. Zoltán Fülöp, Eija Jurvanen, Magnus Steinby, Sándor Vágvölgyi |
| 1998 | On Repetition-Free Binary Words of Minimal Density. Roman M. Kolpakov, Gregory Kucherov, Yuriy V. Tarannikov |
| 1998 | On Some Recognizable Picture-Languages. Klaus Reinhardt |
| 1998 | On the Complexity of Wavelength Converters. Vincenzo Auletta, Ioannis Caragiannis, Christos Kaklamanis, Pino Persiano |
| 1998 | On the Composition Problem for OBDDs with Multiple Variable Orders. Anna Slobodová |
| 1998 | On the Role of Time and Space in Neural Computation. Wolfgang Maass |
| 1998 | On the Word, Subsumption, and Complement Problem for Recurrent Term Schematizations. Miki Hermann, Gernot Salzer |
| 1998 | One Guess One-Way Cellular Arrays. Thomas Buchholz, Andreas Klein, Martin Kutrib |
| 1998 | One Quantifier Will Do in Existential Monadic Second-Order Logic over Pictures. Oliver Matz |
| 1998 | Optimizing OBDDs Is Still Intractable for Monotone Functions. Kazuo Iwama, Mitsushi Nouzoe, Shuzo Yajima |
| 1998 | Polymorphic Subtyping Without Distributivity. Jacek Chrzaszcz |
| 1998 | Positive Turing and Truth-Table Completeness for NEXP Are Incomparable. Levke Bentzien |
| 1998 | Predicative Polymorphic Subtyping. Marcin Benke |
| 1998 | Probabilistic Concurrent Constraint Programming: Towards a Fully Abstract Model. Alessandra Di Pierro, Herbert Wiklicky |
| 1998 | Proof Theory of Fuzzy Logics: Urquhart's C and Related Logics. Matthias Baaz, Agata Ciabattoni, Christian G. Fermüller, Helmut Veith |
| 1998 | Randomness vs. Completeness: On the Diagonalization Strength of Resource-Bounded Random Sets. Klaus Ambos-Spies, Steffen Lempp, Gunther Mainhardt |
| 1998 | Reasoning About the Past. Mogens Nielsen |
| 1998 | Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms. Marek Chrobak, Christoph Dürr |
| 1998 | Reducing AC-Termination to Termination. Maria C. F. Ferreira, Delia Kesner, Laurence Puel |
| 1998 | Representing Hyper-Graphs by Regular Languages. Salvatore La Torre, Margherita Napoli |
| 1998 | Satisfiability - Algorithms and Logic. Pavel Pudlák |
| 1998 | Shuffle on Trajectories: The Schützenberger Product and Related Operations. Tero Harju, Alexandru Mateescu, Arto Salomaa |
| 1998 | Spatial and Temporal Refinement of Typed Graph Transformation Systems. Martin Große-Rhode, Francesco Parisi-Presicce, Marta Simeoni |
| 1998 | Speeding-Up Nondeterministic Single-Tape Off-Line Computations by One Alternation. Jirí Wiedermann |
| 1998 | Tally NP Sets and Easy Census Functions. Judy Goldsmith, Mitsunori Ogihara, Jörg Rothe |
| 1998 | Tarskian Set Constraints Are in NEXPTIME. Pawel Mielniczuk, Leszek Pacholski |
| 1998 | The Equivalence Problem for Deterministic Pushdown Transducers into Abelian Groups. Géraud Sénizergues |
| 1998 | The Head Hierarchy for Oblivious Finite Automata with Polynomial Advice Collapses. Holger Petersen |
| 1998 | The Joys of Bisimulation. Colin Stirling |
| 1998 | The Semi-Full Closure of Pure Type Systems. Gilles Barthe |
| 1998 | Timed Bisimulation and Open Maps. Thomas Hune, Mogens Nielsen |
| 1998 | Topological Definitions of Chaos Applied to Cellular Automata Dynamics. Gianpiero Cattaneo, Luciano Margara |
| 1998 | Towards Algorithmic Explanation of Mind Evolution and Functioning. Jirí Wiedermann |
| 1998 | Towards a Theory of Recursive Structures. David Harel |
| 1998 | Tree Decompositions of Small Diameter. Hans L. Bodlaender, Torben Hagerup |
| 1998 | When Can an Equational Simple Graph Be Generated by Hyperedge Replacement? Klaus Barthelmann |
| 1998 | forall exists*-Equational Theory of Context Unification is Pi Sergei G. Vorobyov |