Languages generated by conjunctive query fragments of FC[REG]

FC is a finite model variant on the theory of concatenation, FC[REG] extends 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 FC[REG]−CQ to that of various related language generators, such as regular expressions, patterns, and typed patterns. We then consider decision problems for FC−CQ and FC[REG]−CQ, and show that certain static analysis problems (such as equivalence and regularity) are undecidable. While this paper defines FC−CQ based on the logic FC, it can equally be understood as synchronized intersections of pattern languages, or as systems of restricted word equations.