Automatentheorie und formale Sprachen

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche
Toggle side column

Automatentheorie und formale Sprachen

Automatentheorie befasst sich mit der Untersuchung von abstrakten Maschinen, ihren Berechnungen und Berechnungsproblemen. Im Wesentlichen können Automaten als endliche Repräsentationen von (potenziell) unendlichen formalen Sprachen verstanden werden, und sie variieren in ihrer Ausdrucksstärke je nach ihrem spezifischen Design.

Endliche Automaten, die die regulären Sprachen erkennen, sind einer der grundlegendsten Formalismen in der theoretischen Informatik und haben sich in vielen Bereichen als nützliches Werkzeug erwiesen, z. B. beim Bau von Compilern, bei der formalen Verifikation oder als Mittel zum Nachweis der Entscheidbarkeit von ausdrucksstarken Logiken, die zur Wissensrepräsentation eingesetzt werden.

Insbesondere in den genannten Bereichen ist es wünschenswert, Sachverhalte zu modellieren, die über Regularität hinausgehen. In diesem Forschungsprojekt sind wir an (Baum-)Automatenmodellen interessiert, die durch Zählmechanismen erweitert werden.

Professoren und Gruppenleiter

Wissenschaftliche Mitarbeiter


Artikel in Fachzeitschriften

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

Artikel in Tagungsbänden

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, Johannes Osterholzer
Non-Global Parikh Tree Automata
14th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2024), to appear
Details
Luisa Herrmann, Richard Mörbitz
Global One-Counter Tree Automata
28th International Conference on Implementation and Application of Automata (CIAA 2024), to appear
Details
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

Dissertationen

Luisa Herrmann
Weighted Automata with Storage
Phd thesis, Technische Universität Dresden, 2020/09/29
Details Download