| 2000 | On Algorithms and Interaction. | Jan van Leeuwen, Jir Wiedermann |
| 2000 | Timed Automata with Monotonic Activities. | Ruggero Lanotte, Andrea Maggiolo-Schettini |
| 2000 | The Infinite Versions of LOGSPACE != P Are Consistent with the Axioms of Set Theory. | Grgory Lafitte, Jacques Mazoyer |
| 2000 | µ-Calculus Synthesis. | Orna Kupferman, Moshe Y. Vardi |
| 2000 | Formal Series over Algebras. | Werner Kuich |
| 2000 | Algebraic and Uniqueness Properties of Parity Ordered Binary Decision Diagrams and Their Generalization. | Daniel Krl |
| 2000 | On NP-Partitions over Posets with an Application to Reducing the Set of Solutions of NP Problems. | Sven Kosub |
| 2000 | 0-1 Laws for Fragments of Existential Second-Order Logic: A Survey. | Phokion G. Kolaitis, Moshe Y. Vardi |
| 2000 | Matching Modulo Associativity and Idempotency Is NP-Complete. | Ondrej Klma, Jir Srba |
| 2000 | Preemptive Scheduling on Dedicated Processors: Applications of Fractional Graph Coloring. | Klaus Jansen, Lorant Porkolab |
| 2000 | A Family of NFA's Which Need 2 | Kazuo Iwama, Akihiro Matsuura, Mike Paterson |
| 2000 | Conter Machines: Decidable Properties and Applications to Verification Problems. | Oscar H. Ibarra, Jianwen Su, Zhe Dang, Tevfik Bultan, Richard A. Kemmerer |
| 2000 | Alternating and Empty Alternating Auxiliary Stack Automata. | Markus Holzer, Pierre McKenzie |
| 2000 | Regular Collections of Message Sequence Charts. | Jesper G. Henriksen, Madhavan Mukund, K. Narayan Kumar, P. S. Thiagarajan |
| 2000 | Reducing the Number of Solutions of NP Functions. | Lane A. Hemaspaandra, Mitsunori Ogihara, Gerd Wechsung |
| 2000 | Computational Politics: Electoral Systems. | Edith Hemaspaandra, Lane A. Hemaspaandra |
| 2000 | And/Or Hierarchies and Round Abstraction. | Radu Grosu |
| 2000 | State Space Reduction Using Partial tau-Confluence. | Jan Friso Groote, Jaco van de Pol |
| 2000 | Explicit Fusions. | Philippa Gardner, Lucian Wischik |
| 2000 | NP-Completeness Results and Efficient Approximations for Radiocoloring in Planar Graphs. | Dimitris Fotakis, Sotiris E. Nikoletseas, Vicky G. Papadopoulou, Paul G. Spirakis |
| 2000 | An Algorithm Constructing the Semilinear Post | Alain Finkel, Grgoire Sutre |
| 2000 | Factorizing Codes and Schtzenberger Conjectures. | Clelia de Felice |
| 2000 | Iteration Theories of Boolean Functions. | Zoltn sik |
| 2000 | On the Autoreducibility of Random Sequences. | Todd Ebert, Heribert Vollmer |
| 2000 | Subtractive Reductions and Complete Problems for Counting Complexity Classes. | Arnaud Durand, Miki Hermann, Phokion G. Kolaitis |