Characterization and Decidability of FC-Definable Regular Languages

Sam M. Thompson, Nicole Schweikardt, Dominik D. Freydenberger

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…