Characterization and Decidability of FC-Definable Regular Languages

Abstract

FC is a first-order logic that reasons over factors of a finite word using concatenation, and can define non-regular languages like that of all squares (ww). In this talk, we will see that there are regular languages that are not FC-definable. Moreover, I will present a decidable characterization of the FC-definable regular languages in terms of algebra, automata, and regular expressions. The last of which is natural and concise: Star-free generalized regular expressions extended with the Kleene star of terminal words.

This talk is based on joint work with Nicole Schweikardt and Dominik D. Freydenberger.