| 2000 | The Curry-Howard Correspondence in Set Theory. | Jean-Louis Krivine |
| 2000 | From the Church-Turing Thesis to the First-Order Algorithm Theorem. | Saul Kripke |
| 2000 | A Decision Procedure for the Existential Theory of Term Algebras with the Knuth-Bendix Ordering. | Konstantin Korovin, Andrei Voronkov |
| 2000 | A Theory of Bisimulation for a Fragment of Concurrent ML with Local Names. | Alan Jeffrey, Julian Rathke |
| 2000 | On First-Order Topological Queries. | Martin Grohe, Luc Segoufin |
| 2000 | Back and Forth between Guarded and Modal Logics. | Erich Grdel, Colin Hirsch, Martin Otto |
| 2000 | Paramodulation with Built-in Abelian Groups. | Guillem Godoy, Robert Nieuwenhuis |
| 2000 | Logic, Complexity, and Games. | Ronald Fagin |
| 2000 | Virtual Symmetry Reduction. | E. Allen Emerson, John Havlicek, Richard J. Trefler |
| 2000 | Approximating Labeled Markov Processes. | Jose Desharnais, Vineet Gupta, Radha Jagadeesan, Prakash Panangaden |
| 2000 | Probabilistic Game Semantics. | Vincent Danos, Russell Harmer |
| 2000 | Game Semantics and Subtyping. | Juliusz Chroboczek |
| 2000 | Models for Name-Passing Processes: Interleaving and Causal. | Gian Luca Cattani, Peter Sewell |
| 2000 | View-Based Query Processing and Constraint Satisfaction. | Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Moshe Y. Vardi |
| 2000 | Resource-Bounded Continuity and Sequentiality for Type-Two Functionals. | Samuel R. Buss, Bruce M. Kapron |
| 2000 | Automatic Structures. | Achim Blumensath, Erich Grdel |
| 2000 | Precongruence Formats for Decorated Trace Preorders. | Bard Bloom, Wan J. Fokkink, Rob J. van Glabbeek |
| 2000 | A General Notion of Realizability. | Lars Birkedal |
| 2000 | Computational Complexity of Some Problems Involving Congruences on Algebras. | Clifford Bergman, Giora Slutzki |
| 2000 | Concurrent Omega-Regular Games. | Luca de Alfaro, Thomas A. Henzinger |
| 2000 | Definability and Compression. | Foto N. Afrati, Hans Lei, Michel de Rougemont |
| 2000 | A Syntactical Analysis of Non-Size-Increasing Polynomial Time Computation. | Klaus Aehlig, Helmut Schwichtenberg |
| 2000 | Better is Better than Well: On Efficient Verification of Infinite-State Systems. | Parosh Aziz Abdulla, Aletta Nyln |
| 1999 | Elementary Axioms for Categories of Classes. | Alex K. Simpson |
| 1999 | Counting and Addition Cannot Express Deterministic Transitive Closure. | Matthias Ruhl |