| 2009 | Boundedness vs. Unboundedness of Lock Chains: Characterizing Decidability of Pairwise CFL-Reachability for Threads Communicating via Locks. | Vineet Kahlon |
| 2009 | Pointer Programs and Undirected Reachability. | Martin Hofmann, Ulrich Schpp |
| 2009 | Winning Concurrent Reachability Games Requires Doubly-Exponential Patience. | Kristoffer Arnsfelt Hansen, Michal Kouck, Peter Bro Miltersen |
| 2009 | On the Computational Complexity of Verifying One-Counter Processes. | Stefan Gller, Richard Mayr, Anthony Widjaja To |
| 2009 | Clipping: A Semantics-Directed Syntactic Approximation. | Dan R. Ghica, Adam Bakewell |
| 2009 | Applications of Game Semantics: From Program Analysis to Hardware Synthesis. | Dan R. Ghica |
| 2009 | An Exponential Lower Bound for the Parity Game Strategy Improvement Algorithm as We Know it. | Oliver Friedmann |
| 2009 | Trichotomy in the Complexity of Minimal Inference. | Arnaud Durand, Miki Hermann, Gustav Nordh |
| 2009 | Logical Step-Indexed Logical Relations. | Derek Dreyer, Amal Ahmed, Lars Birkedal |
| 2009 | Fully Abstract Logical Bisimilarity for a Polymorphic Object Calculus. | Lus Dominguez |
| 2009 | Logics with Rank Operators. | Anuj Dawar, Martin Grohe, Bjarki Holm, Bastian Laubner |
| 2009 | Non-linear Rewrite Closure and Weak Normalization. | Carles Creus, Guillem Godoy, Francesc Massanes, Ashish Tiwari |
| 2009 | My 27-year Quest to Overcome the State Explosion Problem. | Edmund M. Clarke |
| 2009 | Quantitative Model Checking of Continuous-Time Markov Chains Against Timed Automata Specifications. | Taolue Chen, Tingting Han, Joost-Pieter Katoen, Alexandru Mereacre |
| 2009 | A Logic for PTIME and a Parameterized Halting Problem. | Yijia Chen, Jrg Flum |
| 2009 | Expressiveness and Closure Properties for Quantitative Languages. | Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger |
| 2009 | Reflexive Scott Domains are Not Complete for the Extensional Lambda Calculus. | Alberto Carraro, Antonino Salibra |
| 2009 | An Improved Lower Bound for the Complementation of Rabin Automata. | Yang Cai, Ting Zhang, Haifeng Luo |
| 2009 | The Complexity of Global Cardinality Constraints. | Andrei A. Bulatov, Dniel Marx |
| 2009 | An Algebra for Kripke Polynomial Coalgebras. | Marcello M. Bonsangue, Jan J. M. M. Rutten, Alexandra Silva |
| 2009 | Co-ing Bchi Made Tight and Useful. | Udi Boker, Orna Kupferman |
| 2009 | Wreath Products of Forest Algebras, with Applications to Tree Logics. | Mikolaj Bojanczyk, Howard Straubing, Igor Walukiewicz |
| 2009 | Graded Computation Tree Logic. | Alessandro Bianco, Fabio Mogavero, Aniello Murano |
| 2009 | Qualitative Determinacy and Decidability of Stochastic Games with Signals. | Nathalie Bertrand, Blaise Genest, Hugo Gimbert |
| 2009 | Psi-calculi: Mobile Processes, Nominal Data, and Logic. | Jesper Bengtson, Magnus Johansson, Joachim Parrow, Bjrn Victor |