Characterization and Decidability of FC-Definable Regular Languages
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909972896415744 |
|---|---|
| author | Thompson, Sam M. Schweikardt, Nicole Freydenberger, Dominik D. |
| author_facet | Thompson, Sam M. Schweikardt, Nicole Freydenberger, Dominik D. |
| contents | FC is a first-order logic that reasons over all factors of a finite word using concatenation, and can define non-regular languages like that of all squares (ww). In this paper, we establish that there are regular languages that are not FC-definable. Moreover, we give a decidable characterization of the FC-definable regular languages in terms of algebra, automata, and regular expressions. The latter of which is natural and concise: Star-free generalized regular expressions extended with the Kleene star of terminal words. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_09772 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Characterization and Decidability of FC-Definable Regular Languages Thompson, Sam M. Schweikardt, Nicole Freydenberger, Dominik D. Logic in Computer Science Formal Languages and Automata Theory FC is a first-order logic that reasons over all factors of a finite word using concatenation, and can define non-regular languages like that of all squares (ww). In this paper, we establish that there are regular languages that are not FC-definable. Moreover, we give a decidable characterization of the FC-definable regular languages in terms of algebra, automata, and regular expressions. The latter of which is natural and concise: Star-free generalized regular expressions extended with the Kleene star of terminal words. |
| title | Characterization and Decidability of FC-Definable Regular Languages |
| topic | Logic in Computer Science Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2505.09772 |