| 2009 | (Un)Decidability of Injectivity and Surjectivity in One-Dimensional Sand Automata. Gaétan Richard |
| 2009 | A By-Level Analysis of Multiplicative Exponential Linear Logic. Marco Gaboardi, Luca Roversi, Luca Vercelli |
| 2009 | A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems. Michael R. Fellows, Jiong Guo, Hannes Moser, Rolf Niedermeier |
| 2009 | A Dichotomy Theorem for Polynomial Evaluation. Irénée Briquel, Pascal Koiran |
| 2009 | A Dynamic Algorithm for Reachability Games Played on Trees. Bakhadyr Khoussainov, Jiamou Liu, Imran Khaliq |
| 2009 | A General Class of Models of H Giulio Manzonetto |
| 2009 | A Probabilistic PTAS for Shortest Common Superstring. Kai Plociennik |
| 2009 | Admissible Strategies in Infinite Games over Graphs. Marco Faella |
| 2009 | An Algebraic Characterization of Semirings for Which the Support of Every Recognizable Series Is Recognizable. Daniel Kirsten |
| 2009 | An Improved Approximation Bound for Spanning Star Forest and Color Saving. Stavros Athanassopoulos, Ioannis Caragiannis, Christos Kaklamanis, Maria Kyropoulou |
| 2009 | Arithmetic Circuits, Monomial Algebras and Finite Automata. Vikraman Arvind, Pushkar S. Joglekar |
| 2009 | Balanced Paths in Colored Graphs. Alessandro Bianco, Marco Faella, Fabio Mogavero, Aniello Murano |
| 2009 | Bounds on Non-surjective Cellular Automata. Jarkko Kari, Pascal Vanier, Thomas Zeume |
| 2009 | Branching Programs for Tree Evaluation. Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr |
| 2009 | Choosability of P5-Free Graphs. Petr A. Golovach, Pinar Heggernes |
| 2009 | Colouring Non-sparse Random Intersection Graphs. Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, Paul G. Spirakis |
| 2009 | Constructing Brambles. Mathieu Chapelle, Frédéric Mazoit, Ioan Todinca |
| 2009 | DP-Complete Problems Derived from Extremal NP-Complete Properties. Yi Cao, Joseph C. Culberson, Lorna Stewart |
| 2009 | Energy-Efficient Communication in Multi-interface Wireless Networks. Stavros Athanassopoulos, Ioannis Caragiannis, Christos Kaklamanis, Evi Papaioannou |
| 2009 | FO Model Checking on Nested Pushdown Trees. Alexander Kartzow |
| 2009 | Few Product Gates But Many Zeros. Bernd Borchert, Pierre McKenzie, Klaus Reinhardt |
| 2009 | Four Subareas of the Theory of Constraints, and Their Links. Albert Atserias |
| 2009 | From Parity and Payoff Games to Linear Programming. Sven Schewe |
| 2009 | Future-Looking Logics on Data Words and Trees. Diego Figueira, Luc Segoufin |
| 2009 | Graph Decomposition for Improving Memoryless Periodic Exploration. Adrian Kosowski, Alfredo Navarra |
| 2009 | How to Sort a Train. Peter Widmayer |
| 2009 | How to Use Spanning Trees to Navigate in Graphs. Feodor F. Dragan, Yang Xiang |
| 2009 | Hyper-minimisation Made Efficient. Pawel Gawrychowski, Artur Jez |
| 2009 | Mathematical Foundations of Computer Science 2009, 34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009. Proceedings Rastislav Královic, Damian Niwinski |
| 2009 | On FO2 Quantifier Alternation over Words. Manfred Kufleitner, Pascal Weil |
| 2009 | On Pebble Automata for Data Languages with Decidable Emptiness Problem. Tony Tan |
| 2009 | On the Hybrid Extension of CTL and CTL Ahmet Kara, Volker Weber, Martin Lange, Thomas Schwentick |
| 2009 | On the Recognizability of Self-generating Sets. Tomi Kärki, Anne Lacroix, Michel Rigo |
| 2009 | On the Structure of Optimal Greedy Computation (for Job Scheduling). Periklis A. Papakonstantinou |
| 2009 | Parameterized Complexity Classes under Logical Reductions. Anuj Dawar, Yuguo He |
| 2009 | Partial Randomness and Dimension of Recursively Enumerable Reals. Kohtaro Tadaki |
| 2009 | Partial Solution and Entropy. Tadao Takaoka |
| 2009 | Points on Computable Curves of Computable Lengths. Robert Rettinger, Xizhong Zheng |
| 2009 | Private Capacities in Mechanism Design. Vincenzo Auletta, Paolo Penna, Giuseppe Persiano |
| 2009 | Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm. Martin Rötteler |
| 2009 | Query Automata for Nested Words. P. Madhusudan, Mahesh Viswanathan |
| 2009 | Recent Advances in Population Protocols. Ioannis Chatzigiannakis, Othon Michail, Paul G. Spirakis |
| 2009 | Regular Expressions with Counting: Weak versus Strong Determinism. Wouter Gelade, Marc Gyssens, Wim Martens |
| 2009 | Representing Groups on Graphs. Sagarmoy Dutta, Piyush P. Kurur |
| 2009 | Sampling Edge Covers in 3-Regular Graphs. Ivona Bezáková, William A. Rummler |
| 2009 | Security and Tradeoffs of the Akl-Taylor Scheme and Its Variants. Paolo D'Arco, Alfredo De Santis, Anna Lisa Ferrara, Barbara Masucci |
| 2009 | Self-indexed Text Compression Using Straight-Line Programs. Francisco Claude, Gonzalo Navarro |
| 2009 | Size and Energy of Threshold Circuits Computing Mod Functions. Kei Uchizawa, Takao Nishizeki, Eiji Takimoto |
| 2009 | Snake-Deterministic Tiling Systems. Violetta Lonati, Matteo Pradella |
| 2009 | Stochastic Data Streams. S. Muthukrishnan |
| 2009 | Stochastic Games with Finitary Objectives. Krishnendu Chatterjee, Thomas A. Henzinger, Florian Horn |
| 2009 | Stochastic Process Creation. Javier Esparza |
| 2009 | Synchronization of Regular Automata. Didier Caucal |
| 2009 | Synthesis for Structure Rewriting Systems. Lukasz Kaiser |
| 2009 | The Communication Complexity of Non-signaling Distributions. Julien Degorre, Marc Kaplan, Sophie Laplante, Jérémie Roland |
| 2009 | The Complexity of Satisfiability for Fragments of Hybrid Logic-Part I. Arne Meier, Martin Mundhenk, Thomas Schneider, Michael Thomas, Volker Weber, Felix Weiss |
| 2009 | The Cost of Stability in Network Flow Games. Ezra Resnick, Yoram Bachrach, Reshef Meir, Jeffrey S. Rosenschein |
| 2009 | The Expressive Power of Binary Submodular Functions. Stanislav Zivný, David A. Cohen, Peter G. Jeavons |
| 2009 | The Isomorphism Problem for k-Trees Is Complete for Logspace. Johannes Köbler, Sebastian Kuhnert |
| 2009 | The Longest Path Problem Is Polynomial on Interval Graphs. Kyriaki Ioannidou, George B. Mertzios, Stavros D. Nikolopoulos |
| 2009 | The Prismoid of Resources. Delia Kesner, Fabien Renaud |
| 2009 | The Synchronization Problem for Locally Strongly Transitive Automata. Arturo Carpi, Flavio D'Alessandro |
| 2009 | Time-Bounded Kolmogorov Complexity and Solovay Functions. Rupert Hölzl, Thorsten Kräling, Wolfgang Merkle |
| 2009 | Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules. Nadja Betzler, Britta Dorn |