| 2012 | On Centralized PC Grammar Systems with Context-Sensitive Components. | Friedrich Otto |
| 2012 | Non-erasing Variants of the Chomsky-Schtzenberger Theorem. | Alexander Okhotin |
| 2012 | Morphic Primitivity and Alphabet Reductions. | Hossein Nevisi, Daniel Reidenbach |
| 2012 | Pseudoperiodic Words. | Alexandre Blondin Mass, Sbastien Gaboury, Sylvain Hall |
| 2012 | The Avoidability of Cubes under Permutations. | Florin Manea, Mike Mller, Dirk Nowotka |
| 2012 | Homomorphisms Preserving Deterministic Context-Free Languages. | Tommi Lehtinen, Alexander Okhotin |
| 2012 | Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent Deterministic Automata. | Giovanna J. Lavado, Giovanni Pighizzini, Shinnosuke Seki |
| 2012 | States and Heads Do Count for Unary Multi-head Finite Automata. | Martin Kutrib, Andreas Malcher, Matthias Wendlandt |
| 2012 | Dense Completeness. | Andreas Krebs, Klaus-Jrn Lange |
| 2012 | Biautomata for k-Piecewise Testable Languages. | Ondrej Klma, Libor Polk |
| 2012 | Characterizing Languages by Normalization and Termination in String Rewriting - (Extended Abstract). | Jeroen Ketema, Jakob Grue Simonsen |
| 2012 | Cellular Automata, the Collatz Conjecture and Powers of 3/2. | Jarkko Kari |
| 2012 | Fine and Wilf's Theorem for k-Abelian Periods. | Juhani Karhumki, Svetlana Puzynina, Aleksi Saarela |
| 2012 | Analogs of Fagin's Theorem for Small Nondeterministic Finite Automata. | Christos A. Kapoutsis, Nans Lefebvre |
| 2012 | The State Complexity of Star-Complement-Star. | Galina Jirskov, Jeffrey O. Shallit |
| 2012 | Recovering Strings in Oracles: Quantum and Classic. | Kazuo Iwama |
| 2012 | Determinism vs. Nondeterminism for Two-Way Automata - Representing the Meaning of States by Logical Formul. | Juraj Hromkovic, Rastislav Krlovic, Richard Krlovic, Richard Stefanec |
| 2012 | Generalized Derivations with Synchronized Context-Free Grammars. | Markus Holzer, Sebastian Jakobi, Ian McQuillan |
| 2012 | From Equivalence to Almost-Equivalence, and Beyond - Minimizing Automata with Errors - (Extended Abstract). | Markus Holzer, Sebastian Jakobi |
| 2012 | Computing the Edit-Distance between a Regular Language and a Context-Free Language. | Yo-Sub Han, Sang-Ki Ko, Kai Salomaa |
| 2012 | A Generalization of Girod's Bidirectional Decoding Method to Codes with a Finite Deciphering Delay. | Laura Giambruno, Sabrina Mantaci, Jean Nraud, Carla Selmi |
| 2012 | Unary Coded NP-Complete Languages in ASPACE (log log n). | Viliam Geffert, Dana Pardubsk |
| 2012 | On State Complexity of Finite Word and Tree Languages. | Aniruddh Gandhi, Bakhadyr Khoussainov, Jiamou Liu |
| 2012 | On a Hierarchy of Languages with Catenation and Shuffle. | Nils Erik Flick, Manfred Kudlek |
| 2012 | Hairpin Completion with Bounded Stem-Loop. | Szilrd Zsolt Fazekas, Robert Mercas, Kayoko Shikishima-Tsuji |