| 1998 | On Repetition-Free Binary Words of Minimal Density. | Roman M. Kolpakov, Gregory Kucherov, Yuriy V. Tarannikov |
| 1998 | Average-Case Intractability vs. Worst-Case Intractability. | Johannes Kbler, Rainer Schuler |
| 1998 | Modularization and Abstraction: The Keys to Practical Formal Verification. | Yonit Kesten, Amir Pnueli |
| 1998 | On Determinism in Eco-Grammar Systems. | Alica Kelemenov, Radim Petr |
| 1998 | Foreword. | Alica Kelemenov |
| 1998 | Colonies - A Theory of Reactive Agents (Preliminary Survey). | Jozef Kelemen |
| 1998 | On Defect Effect of Bi-Infinite Words. | Juhani Karhumki, Jn Manuch, Wojciech Plandowski |
| 1998 | Optimizing OBDDs Is Still Intractable for Monotone Functions. | Kazuo Iwama, Mitsushi Nouzoe, Shuzo Yajima |
| 1998 | Improved Time and Space Hierarchies of One-Tape Off-Line TMs. | Kazuo Iwama, Chuzo Iwamoto |
| 1998 | Timed Bisimulation and Open Maps. | Thomas Hune, Mogens Nielsen |
| 1998 | Communication Complexity and Lower Bounds on Multilective Computations. | Juraj Hromkovic |
| 1998 | Approximating Maximum Independent Sets in Uniform Hypergraphs. | Thomas Hofmeister, Hanno Lefmann |
| 1998 | On the Word, Subsumption, and Complement Problem for Recurrent Term Schematizations. | Miki Hermann, Gernot Salzer |
| 1998 | A Second Step Towards Circuit Complexity-Theoretic Analogs of Rice's Theorem. | Lane A. Hemaspaandra, Jrg Rothe |
| 1998 | Shuffle on Trajectories: The Schtzenberger Product and Related Operations. | Tero Harju, Alexandru Mateescu, Arto Salomaa |
| 1998 | Towards a Theory of Recursive Structures. | David Harel |
| 1998 | Computing epsilon-Free NFA from Regular Expressions in O(n log²(n)) Time. | Christian Hagenah, Anca Muscholl |
| 1998 | Spatial and Temporal Refinement of Typed Graph Transformation Systems. | Martin Groe-Rhode, Francesco Parisi-Presicce, Marta Simeoni |
| 1998 | Locality of Order-Invariant First-Order Formulas. | Martin Grohe, Thomas Schwentick |
| 1998 | Tally NP Sets and Easy Census Functions. | Judy Goldsmith, Mitsunori Ogihara, Jrg Rothe |
| 1998 | Complete Abstract Interpretations Made Constructive. | Roberto Giacobazzi, Francesco Ranzato, Francesca Scozzari |
| 1998 | A (Non-elementary) Modular Decision Procedure for LTrL. | Paul Gastin, Raphal Meyer, Antoine Petit |
| 1998 | Unreliable Colonies as Systems of Stochastic Grammars. | Jn Gaso |
| 1998 | On One-Pass Term Rewriting. | Zoltn Flp, Eija Jurvanen, Magnus Steinby, Sndor Vgvlgyi |
| 1998 | Array Grammar Systems. | Rudolf Freund |