Automata Theory and Formal Languages
From International Center for Computational Logic
Automata Theory and Formal Languages
Automata theory is concerned with the study of abstract machines, their computations and computational problems. In essence, automata can be understood as finite representations of (potentially) infinite formal languages, and they vary in their expressive power depending on their specific design.
Finite-state automata, recognizing the regular languages, are one of the most fundamental formalisms in theoretical computer science and have proven to be a useful tool in many areas, such as compiler construction, formal verification, or as a means of proving the decidability of expressive logics applied to knowledge representation.
Especially in the areas mentioned, it is desirable to model situations that go beyond regularity. In this research project, we are interested in (tree) automata models that are enriched by counting mechanisms.Professors and Research Group Leaders
Scientific Staff
Journal Articles
Luisa Herrmann
Linear weighted tree automata with storage and inverse linear tree homomorphisms
Information and Computation, 281, 2021
Details
Luisa Herrmann, Heiko Vogler, Manfred Droste
Weighted automata with storage
Information and Computation, 269, 2019
Details
Johannes Osterholzer, Toni Dietze, Luisa Herrmann
Linear context-free tree languages and inverse homomorphisms
Information and Computation, 269, 2019
Details
Zoltán Fülöp, Luisa Herrmann, Heiko Vogler
Weighted Regular Tree Grammars with Storage
Discrete Mathematics & Theoretical Computer Science, 20(1), 2018
Details
Proceedings Articles
Luisa Herrmann, Johannes Osterholzer
Non-Global Parikh Tree Automata
In Florin Manea, Giovanni Pighizzini, eds., 14th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2024), volume 407 of Electronic Proceedings in Theoretical Computer Science, 100--117, 2024. OPA
Details
Luisa Herrmann, Richard Mörbitz
Global One-Counter Tree Automata
In Szilárd Zsolt Fazekas, eds., 28th International Conference on Implementation and Application of Automata (CIAA 2024), volume 15015 of Lecture Notes in Computer Science, 166--179, September 2024. Springer
Details
Luisa Herrmann, Vincent Peth, Sebastian Rudolph
Decidable (Ac)counting with Parikh and Muller: Adding Presburger Arithmetic to Monadic Second-Order Logic over Tree-Interpretable Structures
In Aniello Murano, Alexandra Silva, eds., CSL '24: Proceedings of the 32nd EACSL Annual Conference on Computer Science Logic 2024, volume 288 of LIPIcs, 33:1-33:19, 2024. Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Details Download
Luisa Herrmann
A Medvedev Characterization of Recognizable Tree Series
In Émilie Charlier, Julien Leroy, Michel Rigo, eds., Developments in Language Theory, volume 10396 of Lecture Notes in Computer Science, 210-221, 2017. Springer
Details
Luisa Herrmann, Heiko Vogler
Weighted Symbolic Automata with Data Storage
In Srečko Brlek, Christophe Reutenauer, eds., Developments in Language Theory, volume 9840 of Lecture Notes in Computer Science, 203-215, 2016. Springer
Details
Johannes Osterholzer, Toni Dietze, Luisa Herrmann
Linear Context-Free Tree Languages and Inverse Homomorphisms
In Adrian-Horia DediuJan Janoušek, Carlos Martín-Vide, Bianca Truthe, eds., Language and Automata Theory and Applications, volume 9618 of Lecture Notes in Computer Science, 478-489, 2016. Springer
Details
Heiko Vogler, Manfred Droste, Luisa Herrmann
A Weighted MSO Logic with Storage Behaviour and Its Büchi-Elgot-Trakhtenbrot Theorem
In Adrian-Horia DediuJan Janoušek, Carlos Martín-Vide, Bianca Truthe, eds., Language and Automata Theory and Applications, volume 9618 of Lecture Notes in Computer Science, 127-139, 2016. Springer
Details
Luisa Herrmann, Heiko Vogler
A Chomsky-Schützenberger Theorem for Weighted Automata with Storage
In Andreas Maletti, eds., Algebraic Informatics, volume 9270 of Lecture Notes in Computer Science, 115-127, 2015. Springer
Details
Doctoral Theses
Luisa Herrmann
Weighted Automata with Storage
Phd thesis, Technische Universität Dresden, 2020/09/29
Details Download
