Languages Generated by Conjunctive Query Fragments of FC[REG]
Sam M. Thompson, Dominik D. Freydenberger · Theory of Computing Systems · 2024
Abstract $${\textsf{FC}}$$ FC is a finite model variant on the theory of concatenation, $${\textsf{FC}[\textsf{REG}]}$$ FC [ REG ] extends $${\textsf{FC}}$$ FC with regular constraints. This paper considers the languages generated by their conjunctive query fragments, and . We compare the expressive power of $${\textsf {FC[REG]-CQ}}$$ FC [ REG ] - CQ to that of various related language generators, such as regular expressions, patterns, and typed patterns. We then consider decision problems for $${\textsf {FC-CQ}}$$ FC - CQ and $${\textsf {FC[REG]-CQ}}$$ FC [ REG ] - CQ , and show that certain static analysis problems (such as equivalence and regularity) are undecidable. While this paper defines $${\textsf {FC-CQ}}$$ FC - CQ based on the logic $${\textsf{FC}}$$ FC , it can equally be understood as synchronized intersections of pattern languages, or as systems of restricted word equations.