| 2009 | Prediction of Creole Emergence in Spatial Language Dynamics. | Makoto Nakamura, Takashi Hashimoto, Satoshi Tojo |
| 2009 | The Halting Problem and Undecidability of Document Generation under Access Control for Tree Updates. | Neil Moore |
| 2009 | On Accepting Networks of Evolutionary Processors with at Most Two Types of Nodes. | Victor Mitrana, Bianca Truthe |
| 2009 | A Series of Run-Rich Strings. | Wataru Matsubara, Kazuhiko Kusano, Hideo Bannai, Ayumi Shinohara |
| 2009 | Efficiency of the Symmetry Bias in Grammar Acquisition. | Ryuichi Matoba, Makoto Nakamura, Satoshi Tojo |
| 2009 | A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions. | Toms Masopust |
| 2009 | Segmentation Charts for Czech - Relations among Segments in Complex Sentences. | Markta Lopatkov, Toms Holan |
| 2009 | An Application of Generalized Complexity Spaces to Denotational Semantics via the Domain of Words. | Jordi Llull-Chavarra, 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 | Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata. | Nutan Limaye, Meena Mahajan |
| 2009 | Self-overlapping Occurrences and Knuth-Morris-Pratt Algorithm for Weighted Matching. | Aude Liefooghe, Hlne Touzet, Jean-Stphane Varr |
| 2009 | Two Equivalent Regularizations for Tree Adjoining Grammars. | Anna Kasprzik |
| 2009 | Converting Self-verifying Automata into Deterministic Automata. | Galina Jirskov, Giovanni Pighizzini |
| 2009 | Hypothesis Spaces for Learning. | Sanjay Jain |
| 2009 | Rigid Tree Automata. | Florent Jacquemard, Francis Klay, Camille Vacher |
| 2009 | Bounded Hairpin Completion. | Masami Ito, Peter Leupold, Victor Mitrana |
| 2009 | Counting Parameterized Border Arrays for a Binary Alphabet. | Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda |
| 2009 | Descriptional and Computational Complexity of Finite Automata. | Markus Holzer, Martin Kutrib |
| 2009 | Towards a Taxonomy for ECFG and RRPG Parsing. | Kees Hemerik |
| 2009 | State Complexity of Combined Operations for Prefix-Free Regular Languages. | Yo-Sub Han, Kai Salomaa, Sheng Yu |
| 2009 | Termination of Priority Rewriting. | Isabelle Gnaedig |
| 2009 | The Fault Tolerance of NP-Hard Problems. | Christian Glaer, Aduri Pavan, Stephen D. Travers |
| 2009 | Learning by Erasing in Dynamic Epistemic Logic. | Nina Gierasimczuk |
| 2009 | Bounded Delay and Concurrency for Earliest Query Answering. | Olivier Gauwin, Joachim Niehren, Sophie Tison |