| 2005 | A BDD-Representation for the Logic of Equality and Uninterpreted Functions. | Jaco van de Pol, Olga Tveretina |
| 2005 | Event Structures for the Collective Tokens Philosophy of Inhibitor Nets. | G. Michele Pinna |
| 2005 | Strict Language Inequalities and Their Decision Problems. | Alexander Okhotin |
| 2005 | Completeness and Degeneracy in Information Dynamics of Cellular Automata. | Hidenosuke Nishio |
| 2005 | Concurrent Automata vs. Asynchronous Systems. | Rmi Morin |
| 2005 | Asynchronous Deterministic Rendezvous in Graphs. | Gianluca De Marco, Luisa Gargano, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, Ugo Vaccaro |
| 2005 | Dimension Is Compression. | Mara Lpez-Valds, Elvira Mayordomo |
| 2005 | Inverse Monoids: Decidability and Complexity of Algebraic Questions. | Markus Lohrey, Nicole Ondrusch |
| 2005 | An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules. | Minming Li, Frances F. Yao |
| 2005 | The Complexity of Model Checking Higher Order Fixpoint Logic. | Martin Lange, Rafal Somla |
| 2005 | Tight Approximability Results for the Maximum Solution Equation Problem over Z | Fredrik Kuivinen |
| 2005 | Greedy Approximation via Duality for Packing, Combinatorial Auctions and Routing. | Piotr Krysta |
| 2005 | An Asymptotically Optimal Linear-Time Algorithm for Locally Consistent Constraint Satisfaction Problems. | Daniel Krl, Ondrej Pangrc |
| 2005 | Random Databases and Threshold for Monotone Non-recursive Datalog. | Konstantin Korovin, Andrei Voronkov |
| 2005 | Approximating Reversal Distance for Strings with Bounded Number of Duplicates. | Petr Kolman |
| 2005 | On the Parameterized Complexity of Exact Satisfiability Problems. | Joachim Kneis, Daniel Mlle, Stefan Richter, Peter Rossmanith |
| 2005 | Generating All Minimal Integral Solutions to Monotone and, or-Systems of Linear, Transversal and Polymatroid Inequalities. | Leonid Khachiyan, Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich |
| 2005 | Removing Bidirectionality from Nondeterministic Finite Automata. | Christos A. Kapoutsis |
| 2005 | Shrinking Restarting Automata. | Tomasz Jurdzinski, Friedrich Otto |
| 2005 | Online and Dynamic Recognition of Squarefree Strings. | Jesper Jansson, Zeshan Peng |
| 2005 | Basic Mereology with Equivalence Relations. | Ryszard Janicki |
| 2005 | Some Computational Issues in Membrane Computing. | Oscar H. Ibarra |
| 2005 | Complexity Bounds for Regular Games. | Paul Hunter, Anuj Dawar |
| 2005 | Combining Self-reducibility and Partial Information Algorithms. | Andr Hernich, Arfst Nickelsen |
| 2005 | Algebras as Knowledge Structures. | Bernhard Heinemann |