| 2016 | A Weighted MSO Logic with Storage Behaviour and Its Bchi-Elgot-Trakhtenbrot Theorem. | Heiko Vogler, Manfred Droste, Luisa Herrmann |
| 2016 | On the Levenshtein Automaton and the Size of the Neighbourhood of a Word. | Hlne Touzet |
| 2016 | Forkable Regular Expressions. | Martin Sulzmann, Peter Thiemann |
| 2016 | On Limited Nondeterminism and ACC Circuit Lower Bounds. | Holger Spakowski |
| 2016 | Minimal Separating Sequences for All Pairs of States. | Rick Smetsers, Joshua Moerman, David N. Jansen |
| 2016 | An Error Correcting Parser for Context Free Grammars that Takes Less Than Cubic Time. | Sanguthevar Rajasekaran, Marius Nicolae |
| 2016 | Restricted Turing Machines and Language Recognition. | Giovanni Pighizzini |
| 2016 | Linear Context-Free Tree Languages and Inverse Homomorphisms. | Johannes Osterholzer, Toni Dietze, Luisa Herrmann |
| 2016 | On Del-Robust Primitive Partial Words with One Hole. | Ananda Chandra Nayak, Amit Kumar Srivastava |
| 2016 | Noise Free Multi-armed Bandit Game. | Atsuyoshi Nakamura, David P. Helmbold, Manfred K. Warmuth |
| 2016 | Periodic Generalized Automata over the Reals. | Klaus Meer, Ameen Naif |
| 2016 | Parallelogram Morphisms and Circular Codes. | Alexandre Blondin Mass, Mlodie Lapointe, Hugo Tremblay |
| 2016 | Hankel Matrices for Weighted Visibly Pushdown Automata. | Nadia Labai, Johann A. Makowsky |
| 2016 | Input-Driven Queue Automata with Internal Transductions. | Martin Kutrib, Andreas Malcher, Matthias Wendlandt |
| 2016 | On the Capacity of Capacitated Automata. | Orna Kupferman, Sarai Sheinvald |
| 2016 | Canonical Multi-target Toffoli Circuits. | Hans-Jrg Kreowski, Sabine Kuske, Aaron Lye |
| 2016 | Inferring a Relax NG Schema from XML Documents. | Guen-Hae Kim, Sang-Ki Ko, Yo-Sub Han |
| 2016 | Ogden's Lemma, Multiple Context-Free Grammars, and the Control Language Hierarchy. | Makoto Kanazawa |
| 2016 | The Word Problem for HNN-extensions of Free Inverse Semigroups. | Tatiana Baginov Jajcayov |
| 2016 | The Minimum Entropy Submodular Set Cover Problem. | Gabriel Istrate, Cosmin Bonchis, Liviu P. Dinu |
| 2016 | Compositional Bisimulation Minimization for Interval Markov Decision Processes. | Vahid Hashemi, Holger Hermanns, Lei Song, K. Subramani, Andrea Turrini, Piotr Wojciechowski |
| 2016 | Tangles and Connectivity in Graphs. | Martin Grohe |
| 2016 | Homomorphic Characterizations of Indexed Languages. | Sverine Fratani, El Makki Voundy |
| 2016 | A Complexity Measure on Bchi Automata. | Dana Fisman |
| 2016 | A Kleene Theorem for Weighted Tree Automata over Tree Valuation Monoids. | Manfred Droste, Zoltn Flp, Doreen Gtze |