arXiv Open Access 2025

Characterization and Decidability of FC-Definable Regular Languages

Sam M. Thompson Nicole Schweikardt Dominik D. Freydenberger

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.LO cs.FL

Penulis (3)

Sam M. Thompson

Nicole Schweikardt

Dominik D. Freydenberger

Format Sitasi

APA MLA BibTeX

Thompson, S.M., Schweikardt, N., Freydenberger, D.D. (2025). Characterization and Decidability of FC-Definable Regular Languages. https://arxiv.org/abs/2505.09772

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2025
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓