| 1998 | A Generalization of Resource-Bounded Measure, With an Application (Extended Abstract). Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss |
| 1998 | A Logical Characterization of Systolic Languages. Angelo Monti, Adriano Peron |
| 1998 | A Synthesis on Partition Refinement: A Useful Routine for Strings, Graphs, Boolean Matrices and Automata. Michel Habib, Christophe Paul, Laurent Viennot |
| 1998 | Attractors of D-dimensional Linear Cellular Automata. Giovanni Manzini, Luciano Margara |
| 1998 | Axiomatizing the Equational Theory of Regular Tree Languages (Extended Anstract). Zoltán Ésik |
| 1998 | Bounded Size Dictionary Compression: SC Sergio De Agostino, Riccardo Silvestri |
| 1998 | Cell Flipping in Permutation Diagrams. Martin Charles Golumbic, Haim Kaplan |
| 1998 | Communication-Efficient Deterministic Parallel Algorithms for Planar Point Location and 2d Voronoi Diagram. Mohamadou Diallo, Afonso Ferreira, Andrew Rau-Chaplin |
| 1998 | Complexity of Problems on Graphs Represented as OBDDs (Extended Abstract). Joan Feigenbaum, Sampath Kannan, Moshe Y. Vardi, Mahesh Viswanathan |
| 1998 | Construction of Non-intersecting Colored Flows Through a Planar Cellular Figure. Marius Dorkenoo, Marie-Christine Eglin-Leclerc, Eric Rémila |
| 1998 | Distributed Online Frequency Assignment in Cellular Networks. Jeannette C. M. Janssen, Danny Krizanc, Lata Narayanan, Sunil M. Shende |
| 1998 | Equivalence Test and Ordering Transformation for Parity-OBDDs of Different Variable Ordering. Jan Behrens, Stephan Waack |
| 1998 | Expressive Completeness of LTrL on Finite Traces: An Algebraic Proof. Raphaël Meyer, Antoine Petit |
| 1998 | Floats, Integers, and Single Source Shortest Paths. Mikkel Thorup |
| 1998 | Hierarchies of Principal Twist-Closed Trios. Matthias Jantzen |
| 1998 | Inducing an Order on Cellular Automata by a Grouping Operation. Jacques Mazoyer, Ivan Rapaport |
| 1998 | Interactive Protocols on the Reals. Sergei Ivanov, Michel de Rougemont |
| 1998 | Languages Defined With Modular Counting Quantifiers (Extended Abstract). Howard Straubing |
| 1998 | Local Normal Forms for First-Order Logic with Applications to Games and Automata. Thomas Schwentick, Klaus Barthelmann |
| 1998 | Lower Bounds for Randomized Read-k-Times Branching Programs (Extended Abstract). Martin Sauerhoff |
| 1998 | Massaging a Linear Programming Solution to Give a 2-Approximation for a Generalization of the Vertex Cover Problem. Nader H. Bshouty, Lynn Burroughs |
| 1998 | Minimum Spanning Trees for Minor-Closed Graph Classes in Parallel. Jens Gustedt |
| 1998 | Nearly Optimal Language Compression Using Extractors. Lance Fortnow, Sophie Laplante |
| 1998 | On Batcher's Merge Sorts as Parallel Sorting Algorithms. Christine Rüb |
| 1998 | On Disguised Double Horn Functions and Extensions. Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino |
| 1998 | On Uniform DOL Words. Anna E. Frid |
| 1998 | On the Approximation of Finding A(nother) Hamilton Cycle in Cubic Hamilton Graphs (Extended Abstract). Cristina Bazgan, Miklos Santha, Zsolt Tuza |
| 1998 | On the Existence of Polynomial Time Approximation Schemes for OBDD Minimization (Extended Abstract). Detlef Sieling |
| 1998 | On the Expected Number of Nodes at Level k in 0-balanced Trees. Rainer Kemp |
| 1998 | On the Structure of Valiant's Complexity Classes. Peter Bürgisser |
| 1998 | Optimal Broadcasting in Almost Trees and Partial k-trees. Anders Dessmark, Andrzej Lingas, Hans Olsson, Hiroaki Yamamoto |
| 1998 | Optimal Proof Systems for Propositional Logic and Complete Sets. Jochen Meßner, Jacobo Torán |
| 1998 | Optimal Simulations Between Unary Automata. Carlo Mereghetti, Giovanni Pighizzini |
| 1998 | Partially Persistent Search Trees with Transcript Operations. Kim S. Larsen |
| 1998 | Provable Security for Block Ciphers by Decorrelation. Serge Vaudenay |
| 1998 | Radix Representations of Algebraic Number Fields and Finite Automata. Taoufik Safer |
| 1998 | Random Graphs, Random Walks, Differential Equations and the Probabilistic Analysis of Algorithms. Richard M. Karp |
| 1998 | Random Sparse Bit Strings at the Threshold of Adjacency. Joel Spencer, Katherine St. John |
| 1998 | Recognizability Equals Monadic Second-Order Definability for Sets of Graphs of Bounded Tree-Width. Denis Lapoire |
| 1998 | Recursively Enumerable Reals and Chaitin Omega Numbers. Cristian Calude, Peter Hertling, Bakhadyr Khoussainov, Yongge Wang |
| 1998 | Relating Hierarchies of Word and Tree Automata. Damian Niwinski, Igor Walukiewicz |
| 1998 | Result-Indistinguishable Zero-Knowledge Proofs: Increased Power and Constant-Round Protocols. Giovanni Di Crescenzo, Kouichi Sakurai, Moti Yung |
| 1998 | STACS 98, 15th Annual Symposium on Theoretical Aspects of Computer Science, Paris, France, February 25-27, 1998, Proceedings Michel Morvan, Christoph Meinel, Daniel Krob |
| 1998 | Searching Constant Width Mazes Captures the AC David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum |
| 1998 | Series-Parallel Posets: Algebra, Automata and Languages. Kamal Lodaya, Pascal Weil |
| 1998 | Shuffle of omega-Words: Algebraic Aspects (Extended Abstract). Alexandru Mateescu |
| 1998 | Simplifying the Modal Mu-Calculus Alternation Hierarchy. Julian C. Bradfield |
| 1998 | Size and Structure of Random Ordered Binary Decision Diagrams (Extended Abstract). Clemens Gröpl, Hans Jürgen Prömel, Anand Srivastav |
| 1998 | Sorting and Searching on the Word RAM. Torben Hagerup |
| 1998 | The (Parallel) Approximability of Non-Boolean Satisfiability Problems and Restricted Integer Programming. Maria J. Serna, Luca Trevisan, Fatos Xhafa |
| 1998 | The Complexity of Modular Graph Automorphism. Vikraman Arvind, Richard Beigel, Antoni Lozano |
| 1998 | The Complexity of Propositional Linear Temporal Logics in Simple Cases (Extended Abstract). Stéphane Demri, Philippe Schnoebelen |
| 1998 | The Mutual Exclusion Scheduling Problem for Permutation and Comparability Graphs. Klaus Jansen |
| 1998 | Unary Quantifiers, Transitive Closure, and Relations of Large Degree. Leonid Libkin, Limsoon Wong |
| 1998 | Uniformly Defining Complexity Classes of Functions. Sven Kosub, Heinz Schmitz, Heribert Vollmer |