2025/05/14 by Sam M. Thompson, Thompson, Sam M., Nicole Schweikardt +3
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO) #cs.FL #cs.LO
paper · pdf · doi:10.48550/arxiv.2505.09772
arxiv created 2026/07/30 · arxiv updated 2026/07/31
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.