| 2009 | A Cryptosystem Based on the Composition of Reversible Cellular Automata. Adam Clarridge, Kai Salomaa |
| 2009 | A Kleene Theorem for Forest Languages. Lutz Straßburger |
| 2009 | A Language-Based Comparison of Extensions of Petri Nets with and without Whole-Place Operations. Parosh Aziz Abdulla, Giorgio Delzanno, Laurent Van Begin |
| 2009 | A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions. Tomás Masopust |
| 2009 | A Series of Run-Rich Strings. Wataru Matsubara, Kazuhiko Kusano, Hideo Bannai, Ayumi Shinohara |
| 2009 | Absolute Convergence of Rational Series Is Semi-decidable. Raphaël Bailly, François Denis |
| 2009 | An Answer to a Conjecture on Overlaps in Partial Words Using Periodicity Algorithms. Francine Blanchet-Sadri, Robert Mercas, Abraham Rashin, Elara Willett |
| 2009 | An Application of Generalized Complexity Spaces to Denotational Semantics via the Domain of Words. Jordi Llull-Chavarría, Óscar Valero |
| 2009 | Analysing Complexity in Classes of Unary Automatic Structures. Jiamou Liu, Mia Minnes |
| 2009 | Automata on Gauss Words. Alexei Lisitsa, Igor Potapov, Rafiq Saleh |
| 2009 | Bounded Delay and Concurrency for Earliest Query Answering. Olivier Gauwin, Joachim Niehren, Sophie Tison |
| 2009 | Bounded Hairpin Completion. Masami Ito, Peter Leupold, Victor Mitrana |
| 2009 | Commutative Regular Shuffle Closed Languages, Noetherian Property, and Learning Theory. Yohji Akama |
| 2009 | Constructing Infinite Words of Intermediate Arithmetical Complexity. Paul V. Salimov |
| 2009 | Converting Self-verifying Automata into Deterministic Automata. Galina Jirásková, Giovanni Pighizzini |
| 2009 | Counting Parameterized Border Arrays for a Binary Alphabet. Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda |
| 2009 | Decision Problems for Convex Languages. Janusz A. Brzozowski, Jeffrey O. Shallit, Zhi Xu |
| 2009 | Descriptional and Computational Complexity of Finite Automata. Markus Holzer, Martin Kutrib |
| 2009 | Determinization and Expressiveness of Integer Reset Timed Automata with Silent Transitions. P. Vijay Suman, Paritosh K. Pandya |
| 2009 | Efficiency of the Symmetry Bias in Grammar Acquisition. Ryuichi Matoba, Makoto Nakamura, Satoshi Tojo |
| 2009 | Finitely Generated Synchronizing Automata. Elena V. Pribavkina, Emanuele Rodaro |
| 2009 | From Gene Trees to Species Trees through a Supertree Approach. Céline Scornavacca, Vincent Berry, Vincent Ranwez |
| 2009 | Genetic Algorithm for Synchronization. Adam Roman |
| 2009 | Grammars Controlled by Special Petri Nets. Jürgen Dassow, Sherzod Turaev |
| 2009 | How Many Holes Can an Unbordered Partial Word Contain?. Francine Blanchet-Sadri, Emily Allen, Cameron Byrum, Robert Mercas |
| 2009 | Hypothesis Spaces for Learning. Sanjay Jain |
| 2009 | Language and Automata Theory and Applications, Third International Conference, LATA 2009, Tarragona, Spain, April 2-8, 2009. Proceedings Adrian-Horia Dediu, Armand-Mihai Ionescu, Carlos Martín-Vide |
| 2009 | Larger Lower Bounds on the OBDD Complexity of Integer Multiplication. Beate Bollig |
| 2009 | Learning by Erasing in Dynamic Epistemic Logic. Nina Gierasimczuk |
| 2009 | Matching Trace Patterns with Regular Policies. Franz Baader, Andreas Bauer, Alwen Tiu |
| 2009 | Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata. Nutan Limaye, Meena Mahajan |
| 2009 | Minimal Union-Free Decompositions of Regular Languages. Sergey A. Afonin, Denis Golomazov |
| 2009 | Monadic Datalog Tree Transducers. Matthias Büchse, Torsten Stüber |
| 2009 | Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications. Bruno Courcelle |
| 2009 | Multi-tilde Operators and Their Glushkov Automata. Pascal Caron, Jean-Marc Champarnaud, Ludovic Mignot |
| 2009 | Nested Counters in Bit-Parallel String Matching. Kimmo Fredriksson, Szymon Grabowski |
| 2009 | New Morphic Characterizations of Languages in Chomsky Hierarchy Using Insertion and Locality. Kaoru Onodera |
| 2009 | Non-solvable Groups Are Not in FO+MOD+MÂJ2[REG]. Christoph Behle, Andreas Krebs, Stephanie Reifferscheid |
| 2009 | Non-uniform Cellular Automata. Gianpiero Cattaneo, Alberto Dennunzio, Enrico Formenti, Julien Provillard |
| 2009 | Nondeterministic Instance Complexity and Proof Systems with Advice. Olaf Beyersdorff, Johannes Köbler, Sebastian Müller |
| 2009 | On Accepting Networks of Evolutionary Processors with at Most Two Types of Nodes. Victor Mitrana, Bianca Truthe |
| 2009 | On Extended Regular Expressions. Benjamin Carle, Paliath Narendran |
| 2009 | On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata. Dana Pardubská, Martin Plátek, Friedrich Otto |
| 2009 | On a Family of Morphic Images of Arnoux-Rauzy Words. Michelangelo Bucci, Alessandro De Luca |
| 2009 | On the Average Size of Glushkov's Automata. Cyril Nicaud |
| 2009 | One-Clock Deterministic Timed Automata Are Efficiently Identifiable in the Limit. Sicco Verwer, Mathijs de Weerdt, Cees Witteveen |
| 2009 | Partial Projection of Sets Represented by Finite Automata, with Application to State-Space Visualization. Bernard Boigelot, Jean-François Degbomont |
| 2009 | Picture Languages Generated by Assembling Tiles. Paola Bonizzoni, Claudio Ferretti, Anthonath Roslin Sagaya Mary, Giancarlo Mauri |
| 2009 | Prediction of Creole Emergence in Spatial Language Dynamics. Makoto Nakamura, Takashi Hashimoto, Satoshi Tojo |
| 2009 | Recent Developments in Algorithmic Teaching. Frank J. Balbach, Thomas Zeugmann |
| 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 | Rigid Tree Automata. Florent Jacquemard, Francis Klay, Camille Vacher |
| 2009 | Segmentation Charts for Czech - Relations among Segments in Complex Sentences. Markéta Lopatková, Tomás Holan |
| 2009 | Self-overlapping Occurrences and Knuth-Morris-Pratt Algorithm for Weighted Matching. Aude Liefooghe, Hélène Touzet, Jean-Stéphane Varré |
| 2009 | State Complexity of Combined Operations for Prefix-Free Regular Languages. Yo-Sub Han, Kai Salomaa, Sheng Yu |
| 2009 | State Complexity of Nested Word Automata. Kai Salomaa |
| 2009 | Termination of Priority Rewriting. Isabelle Gnaedig |
| 2009 | The Fault Tolerance of NP-Hard Problems. Christian Glaßer, Aduri Pavan, Stephen D. Travers |
| 2009 | The Halting Problem and Undecidability of Document Generation under Access Control for Tree Updates. Neil Moore |
| 2009 | Tiling the Plane with a Fixed Number of Polyominoes. Nicolas Ollinger |
| 2009 | Towards a Taxonomy for ECFG and RRPG Parsing. Kees Hemerik |
| 2009 | Two Equivalent Regularizations for Tree Adjoining Grammars. Anna Kasprzik |
| 2009 | Undecidability of Operation Problems for T0L Languages and Subclasses. Henning Bordihn, Markus Holzer, Martin Kutrib |