Languages Generated by Conjunctive Query Fragments of FC[REG]

Abstract $${\textsf{FC}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>FC</mml:mi> </mml:math> is a finite model variant on the theory of concatenation, $${\textsf{FC}[\textsf{REG}]}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>FC</mml:mi> <mml:mo>[</mml:mo> <mml:mi>REG</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> extends $${\textsf{FC}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>FC</mml:mi> </mml:math> 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}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>FC</mml:mi> <mml:mo>[</mml:mo> <mml:mi>REG</mml:mi> <mml:mo>]</mml:mo> <mml:mo>-</mml:mo> <mml:mi>CQ</mml:mi> </mml:mrow> </mml:math> to that of various related language generators, such as regular expressions, patterns, and typed patterns. We then consider decision problems for $${\textsf {FC-CQ}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>FC</mml:mi> <mml:mo>-</mml:mo> <mml:mi>CQ</mml:mi> </mml:mrow> </mml:math> and $${\textsf {FC[REG]-CQ}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>FC</mml:mi> <mml:mo>[</mml:mo> <mml:mi>REG</mml:mi> <mml:mo>]</mml:mo> <mml:mo>-</mml:mo> <mml:mi>CQ</mml:mi> </mml:mrow> </mml:math> , and show that certain static analysis problems (such as equivalence and regularity) are undecidable. While this paper defines $${\textsf {FC-CQ}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>FC</mml:mi> <mml:mo>-</mml:mo> <mml:mi>CQ</mml:mi> </mml:mrow> </mml:math> based on the logic $${\textsf{FC}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>FC</mml:mi> </mml:math> , it can equally be understood as synchronized intersections of pattern languages, or as systems of restricted word equations.