Characterization and Decidability of FC-Definable Regular Languages
By: Sam M. Thompson, Nicole Schweikardt, Dominik D. Freydenberger
Potential Business Impact:
Finds patterns in words computers can't.
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.
Similar Papers
Regular expressions over countable words
Logic in Computer Science
Makes computer rules work for endless lists.
Polyregular Model Checking
Formal Languages and Automata Theory
Checks computer programs for mistakes automatically.
Measure-Theoretic Aspects of Star-Free and Group Languages
Formal Languages and Automata Theory
Helps computers understand language patterns better.