Algebraic Characterizations of Classes of Regular Languages in DynFO
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912849668866048 |
|---|---|
| author | Barloy, Corentin Tschirbs, Felix Vortmeier, Nils Zeume, Thomas |
| author_facet | Barloy, Corentin Tschirbs, Felix Vortmeier, Nils Zeume, Thomas |
| contents | This paper explores the fine-grained structure of classes of regular languages maintainable in fragments of first-order logic within the dynamic descriptive complexity framework of Patnaik and Immerman. A result by Hesse states that the class of regular languages is maintainable by first-order formulas even if only unary auxiliary relations can be used. Another result by Gelade, Marquardt,and Schwentick states that the class of regular languages coincides with the class of languages maintainable by quantifier-free formulas with binary auxiliary relations. We refine Hesse's result and show that with unary auxiliary data formulas with one quantifier alternation can maintain all regular languages. We then obtain precise algebraic characterizations of the classes of languages maintainable with quantifier-free formulas and positive existential formulas in the presence of unary auxiliary relations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_18429 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Algebraic Characterizations of Classes of Regular Languages in DynFO Barloy, Corentin Tschirbs, Felix Vortmeier, Nils Zeume, Thomas Logic in Computer Science Formal Languages and Automata Theory This paper explores the fine-grained structure of classes of regular languages maintainable in fragments of first-order logic within the dynamic descriptive complexity framework of Patnaik and Immerman. A result by Hesse states that the class of regular languages is maintainable by first-order formulas even if only unary auxiliary relations can be used. Another result by Gelade, Marquardt,and Schwentick states that the class of regular languages coincides with the class of languages maintainable by quantifier-free formulas with binary auxiliary relations. We refine Hesse's result and show that with unary auxiliary data formulas with one quantifier alternation can maintain all regular languages. We then obtain precise algebraic characterizations of the classes of languages maintainable with quantifier-free formulas and positive existential formulas in the presence of unary auxiliary relations. |
| title | Algebraic Characterizations of Classes of Regular Languages in DynFO |
| topic | Logic in Computer Science Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2601.18429 |