| 2004 | On the Language Inclusion Problem for Timed Automata: Closing a Decidability Gap. | Jol Ouaknine, James Worrell |
| 2004 | An Algebraic Approach to the Complexity of Propositional Circumscription. | Gustav Nordh, Peter Jonsson |
| 2004 | VTC | Phuong Nguyen, Stephen A. Cook |
| 2004 | Towards Imperative Modules: Reasoning about Invariants and Sharing of Mutable State. | David A. Naumann, Michael Barnett |
| 2004 | Congruence for SOS with Data. | Mohammad Reza Mousavi, Michel A. Reniers, Jan Friso Groote |
| 2004 | Semantics of a Sequential Language for Exact Real-Number Computation. | Jos Raymundo Marcial-Romero, Martn Htzel Escard |
| 2004 | Equicardinality on Linear Orders. | Kerkko Luosto |
| 2004 | Proving Termination Assertions in Dynamic Logics. | Daniel Leivant |
| 2004 | From Automata to Formulas: Convex Integer Polyhedra. | Louis Latour |
| 2004 | On the Automata Size for Presburger Arithmetic. | Felix Klaedtke |
| 2004 | Automatic Structures: Richness and Limitations. | Bakhadyr Khoussainov, Andr Nies, Sasha Rubin, Frank Stephan |
| 2004 | The Omega Rule is II_2^0-Hard in the lambda beta -Calculus. | Benedetto Intrigila, Richard Statman |
| 2004 | Beyond Image-Finiteness: Labelled Transition Systems as a Stone Space. | Michael Huth |
| 2004 | Self-Adjusting Computation. | Robert Harper |
| 2004 | Vector Addition Tree Automata. | Philippe de Groote, Bruno Guillaume, Sylvain Salvati |
| 2004 | The Succinctness of First-Order Logic on Linear Orders. | Martin Grohe, Nicole Schweikardt |
| 2004 | A Sequent Calculus for Nominal Logic. | Murdoch Gabbay, James Cheney |
| 2004 | On the Geometry of Interaction for Classical Logic. | Carsten Fhrmann, David J. Pym |
| 2004 | Model-Checking Problems as a Basis for Parameterized Intractability. | Jrg Flum, Martin Grohe |
| 2004 | Model Checking Probabilistic Pushdown Automata. | Javier Esparza, Antonn Kucera, Richard Mayr |
| 2004 | Parametric Limits. | Brian P. Dunphy, Uday S. Reddy |
| 2004 | The Existence of Finite Abstractions for Branching Time Model Checking. | Dennis Dams, Kedar S. Namjoshi |
| 2004 | First-Order Definable Retraction Problems for Posets and Reflexive Graph. | Vctor Dalmau, Andrei A. Krokhin, Benot Larose |
| 2004 | The Strength of Replacement in Weak Arithmetic. | Stephen A. Cook, Neil Thapen |
| 2004 | A Second-Order Theory for NL. | Stephen A. Cook, Antonina Kolokolova |