Languages Generated by Conjunctive Query Fragments of FC[REG]

\({\textsf{FC}}\) $\mathsf{FC}$ is a finite model variant on the theory of concatenation, \({\textsf{FC}[\textsf{REG}]}\) $\mathsf{FC}[\mathsf{REG}]$ extends \({\textsf{FC}}\) $\mathsf{FC}$ with regular constraints. This paper considers the languages generated by their conjunctive query fragments, FC-CQ and FC[REG]-CQ. We compare the expressive power of \({\textsf {FC[REG]-CQ}}\) $\mathsf{FC}[\mathsf{REG}]-\mathsf{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}}\) $\mathsf{FC}-\mathsf{CQ}$ and \({\textsf {FC[REG]-CQ}}\) $\mathsf{FC}[\mathsf{REG}]-\mathsf{CQ}$ , and show that certain static analysis problems (such as equivalence and regularity) are undecidable. While this paper defines \({\textsf {FC-CQ}}\) $\mathsf{FC}-\mathsf{CQ}$ based on the logic \({\textsf{FC}}\) $\mathsf{FC}$ , it can equally be understood as synchronized intersections of pattern languages, or as systems of restricted word equations.