| 2009 | Nested Counters in Bit-Parallel String Matching. | Kimmo Fredriksson, Szymon Grabowski |
| 2009 | Grammars Controlled by Special Petri Nets. | Jrgen Dassow, Sherzod Turaev |
| 2009 | Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications. | Bruno Courcelle |
| 2009 | A Cryptosystem Based on the Composition of Reversible Cellular Automata. | Adam Clarridge, Kai Salomaa |
| 2009 | Non-uniform Cellular Automata. | Gianpiero Cattaneo, Alberto Dennunzio, Enrico Formenti, Julien Provillard |
| 2009 | Multi-tilde Operators and Their Glushkov Automata. | Pascal Caron, Jean-Marc Champarnaud, Ludovic Mignot |
| 2009 | On Extended Regular Expressions. | Benjamin Carle, Paliath Narendran |
| 2009 | Monadic Datalog Tree Transducers. | Matthias Bchse, Torsten Stber |
| 2009 | On a Family of Morphic Images of Arnoux-Rauzy Words. | Michelangelo Bucci, Alessandro De Luca |
| 2009 | Decision Problems for Convex Languages. | Janusz A. Brzozowski, Jeffrey O. Shallit, Zhi Xu |
| 2009 | Undecidability of Operation Problems for T0L Languages and Subclasses. | Henning Bordihn, Markus Holzer, Martin Kutrib |
| 2009 | Picture Languages Generated by Assembling Tiles. | Paola Bonizzoni, Claudio Ferretti, Anthonath Roslin Sagaya Mary, Giancarlo Mauri |
| 2009 | Larger Lower Bounds on the OBDD Complexity of Integer Multiplication. | Beate Bollig |
| 2009 | Partial Projection of Sets Represented by Finite Automata, with Application to State-Space Visualization. | Bernard Boigelot, Jean-Franois Degbomont |
| 2009 | An Answer to a Conjecture on Overlaps in Partial Words Using Periodicity Algorithms. | Francine Blanchet-Sadri, Robert Mercas, Abraham Rashin, Elara Willett |
| 2009 | How Many Holes Can an Unbordered Partial Word Contain?. | Francine Blanchet-Sadri, Emily Allen, Cameron Byrum, Robert Mercas |
| 2009 | Nondeterministic Instance Complexity and Proof Systems with Advice. | Olaf Beyersdorff, Johannes Kbler, Sebastian Mller |
| 2009 | Refinement and Consistency of Timed Modal Specifications. | Nathalie Bertrand, Sophie Pinchinat, Jean-Baptiste Raclet |
| 2009 | Reoptimization of Traveling Salesperson Problems: Changing Single Edge-Weights. | Tobias Berg, Harald Hempel |
| 2009 | Non-solvable Groups Are Not in FO+MOD+MJ2[REG]. | Christoph Behle, Andreas Krebs, Stephanie Reifferscheid |
| 2009 | Recent Developments in Algorithmic Teaching. | Frank J. Balbach, Thomas Zeugmann |
| 2009 | Absolute Convergence of Rational Series Is Semi-decidable. | Raphal Bailly, Franois Denis |
| 2009 | Matching Trace Patterns with Regular Policies. | Franz Baader, Andreas Bauer, Alwen Tiu |
| 2009 | Commutative Regular Shuffle Closed Languages, Noetherian Property, and Learning Theory. | Yohji Akama |
| 2009 | Minimal Union-Free Decompositions of Regular Languages. | Sergey A. Afonin, Denis Golomazov |