| 2000 | 0-1 Laws for Fragments of Existential Second-Order Logic: A Survey. Phokion G. Kolaitis, Moshe Y. Vardi |
| 2000 | A Compositional Model for Confluent Dynamic Data-Flow Networks. Frank S. de Boer, Marcello M. Bonsangue |
| 2000 | A Family of NFA's Which Need 2 Kazuo Iwama, Akihiro Matsuura, Mike Paterson |
| 2000 | A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism. Petr Savický, Detlef Sieling |
| 2000 | Abstract Data Types in Computer Algebra. James H. Davenport |
| 2000 | Abstract Syntax and Variable Binding for Linear Binders. Miki Tanaka |
| 2000 | Algebraic and Uniqueness Properties of Parity Ordered Binary Decision Diagrams and Their Generalization. Daniel Král |
| 2000 | Alternating and Empty Alternating Auxiliary Stack Automata. Markus Holzer, Pierre McKenzie |
| 2000 | An Algorithm Constructing the Semilinear Post Alain Finkel, Grégoire Sutre |
| 2000 | An Automata-Based Recognition Algorithm for Semi-extended Regular Expressions. Hiroaki Yamamoto |
| 2000 | And/Or Hierarchies and Round Abstraction. Radu Grosu |
| 2000 | Automatic Graphs and Graph Olivier Ly |
| 2000 | Axiomatizing Fully Complete Models for ML Polymorphic Types. Samson Abramsky, Marina Lenisa |
| 2000 | Balanced Therese C. Biedl, Eowyn Cenek, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Ming-wei Wang |
| 2000 | Bilinear Functions and Trees over the (max, +) Semiring. Sabrina Mantaci, Vincent D. Blondel, Jean Mairesse |
| 2000 | Binary Decision Diagrams by Shard Rewriting. Jaco van de Pol, Hans Zantema |
| 2000 | Compositional Characterizations of lambda-Terms Using Intersection Types. Mariangiola Dezani-Ciancaglini, Furio Honsell, Yoko Motohama |
| 2000 | Computational Politics: Electoral Systems. Edith Hemaspaandra, Lane A. Hemaspaandra |
| 2000 | Conter Machines: Decidable Properties and Applications to Verification Problems. Oscar H. Ibarra, Jianwen Su, Zhe Dang, Tevfik Bultan, Richard A. Kemmerer |
| 2000 | Derivability in Locally Quantified Modal Logics via Translation in Set Theory. Angelo Montanari, Alberto Policriti, Matteo Slanina |
| 2000 | Edge-Bisection of Chordal Rings. Lali Barrière, Josep Fàbrega |
| 2000 | Embedding Fibonacci Cubes into Hypercubes with Rostislav Caha, Petr Gregor |
| 2000 | Equation Satisfiability and Program Satisfiability for Finite Monoids. David A. Mix Barrington, Pierre McKenzie, Cristopher Moore, Pascal Tesson, Denis Thérien |
| 2000 | Explicit Fusions. Philippa Gardner, Lucian Wischik |
| 2000 | Expressiveness of Updatable Timed Automata. Patricia Bouyer, Catherine Dufourd, Emmanuel Fleury, Antoine Petit |
| 2000 | Factorizing Codes and Schützenberger Conjectures. Clelia De Felice |
| 2000 | Formal Series over Algebras. Werner Kuich |
| 2000 | Informative Labeling Schemes for Graphs. David Peleg |
| 2000 | Iteration Theories of Boolean Functions. Zoltán Ésik |
| 2000 | Iterative Arrays with Small Time Bounds. Thomas Buchholz, Andreas Klein, Martin Kutrib |
| 2000 | Matching Modulo Associativity and Idempotency Is NP-Complete. Ondrej Klíma, Jirí Srba |
| 2000 | Mathematical Foundations of Computer Science 2000, 25th International Symposium, MFCS 2000, Bratislava, Slovakia, August 28 - September 1, 2000, Proceedings Mogens Nielsen, Branislav Rovan |
| 2000 | Measure Theoretic Completeness Notions for the Exponential Time Classes. Klaus Ambos-Spies |
| 2000 | NP-Completeness Results and Efficient Approximations for Radiocoloring in Planar Graphs. Dimitris Fotakis, Sotiris E. Nikoletseas, Vicky G. Papadopoulou, Paul G. Spirakis |
| 2000 | On Algorithms and Interaction. Jan van Leeuwen, Jirí Wiedermann |
| 2000 | On Diving in Trees. Thomas Schwentick |
| 2000 | On NP-Partitions over Posets with an Application to Reducing the Set of Solutions of NP Problems. Sven Kosub |
| 2000 | On a Generalization of Bi-Complement Reducible Graphs. Vadim V. Lozin |
| 2000 | On the Autoreducibility of Random Sequences. Todd Ebert, Heribert Vollmer |
| 2000 | On the Lower Bounds for One-Way Quantum Automata. Farid M. Ablayev, Aida Gainutdinova |
| 2000 | On the Use of Duality and Geometry in Layouts for ATM Networks. Shmuel Zaks |
| 2000 | Optical Routing of Uniform Instances in Tori. Francesc Comellas, Margarida Mitjana, Lata Narayanan, Jaroslav Opatrny |
| 2000 | Optimal Satisfiability for Propositional Calculi and Constraint Satisfaction Problems. Steffen Reith, Heribert Vollmer |
| 2000 | Periodic-Like Words. Arturo Carpi, Aldo de Luca |
| 2000 | Preemptive Scheduling on Dedicated Processors: Applications of Fractional Graph Coloring. Klaus Jansen, Lorant Porkolab |
| 2000 | Reducing the Number of Solutions of NP Functions. Lane A. Hemaspaandra, Mitsunori Ogihara, Gerd Wechsung |
| 2000 | Region Analysis and a pi-Calculus wiht Groups. Silvano Dal-Zilio, Andrew D. Gordon |
| 2000 | Regular Collections of Message Sequence Charts. Jesper G. Henriksen, Madhavan Mukund, K. Narayan Kumar, P. S. Thiagarajan |
| 2000 | Regularity of Congruential Graphs. Tanguy Urvoy |
| 2000 | Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication. Beate Bollig |
| 2000 | Separation Results for Rebound Automata. Holger Petersen |
| 2000 | Simplifying Flow Networks. Therese C. Biedl, Brona Brejová, Tomás Vinar |
| 2000 | State Space Reduction Using Partial tau-Confluence. Jan Friso Groote, Jaco van de Pol |
| 2000 | Sublinear Ambiguity. Klaus Wich |
| 2000 | Subtractive Reductions and Complete Problems for Counting Complexity Classes. Arnaud Durand, Miki Hermann, Phokion G. Kolaitis |
| 2000 | The Infinite Versions of LOGSPACE != P Are Consistent with the Axioms of Set Theory. Grégory Lafitte, Jacques Mazoyer |
| 2000 | The Monadic Theory of Morphic Infinite Words and Generalizations. Olivier Carton, Wolfgang Thomas |
| 2000 | Time and Message Optimal Leader Election in Asynchronous Oriented Complete Networks. Stefan Dobrev |
| 2000 | Timed Automata with Monotonic Activities. Ruggero Lanotte, Andrea Maggiolo-Schettini |
| 2000 | Unary Pushdown Automata and Auxiliary Space Lower Bounds. Giovanni Pighizzini |
| 2000 | Verifying Single and Multi-mutator Garbage Collectors with Owicki-Gries in Isabelle/HOL. Leonor Prensa Nieto, Javier Esparza |
| 2000 | What Do We Learn from Experimental Algorithmics? Camil Demetrescu, Giuseppe F. Italiano |
| 2000 | Why so Many Temporal Logics Climb up the Trees? Alexander Moshe Rabinovich, Shahar Maoz |
| 2000 | XML Grammars. Jean Berstel, Luc Boasson |
| 2000 | pi-Calculus, Structured Coalgebras, and Minimal HD-Automata. Ugo Montanari, Marco Pistore |
| 2000 | µ-Calculus Synthesis. Orna Kupferman, Moshe Y. Vardi |