{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T07:23:14Z","timestamp":1760080994923,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,10,10]],"date-time":"2024-10-10T00:00:00Z","timestamp":1728518400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,10]],"date-time":"2024-10-10T00:00:00Z","timestamp":1728518400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/T033762\/1"],"award-info":[{"award-number":["EP\/T033762\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,12]]},"abstract":"Abstract<\/jats:title>$${\\textsf{FC}}$$<\/jats:tex-math>\n FC<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is a finite model variant on the theory of concatenation, $${\\textsf{FC}[\\textsf{REG}]}$$<\/jats:tex-math>\n \n FC<\/mml:mi>\n [<\/mml:mo>\n REG<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> extends $${\\textsf{FC}}$$<\/jats:tex-math>\n FC<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> 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}}$$<\/jats:tex-math>\n \n FC<\/mml:mi>\n [<\/mml:mo>\n REG<\/mml:mi>\n ]<\/mml:mo>\n -<\/mml:mo>\n CQ<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> to that of various related language generators, such as regular expressions, patterns, and typed patterns. We then consider decision problems for $${\\textsf {FC-CQ}}$$<\/jats:tex-math>\n \n FC<\/mml:mi>\n -<\/mml:mo>\n CQ<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $${\\textsf {FC[REG]-CQ}}$$<\/jats:tex-math>\n \n FC<\/mml:mi>\n [<\/mml:mo>\n REG<\/mml:mi>\n ]<\/mml:mo>\n -<\/mml:mo>\n CQ<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and show that certain static analysis problems (such as equivalence and regularity) are undecidable. While this paper defines $${\\textsf {FC-CQ}}$$<\/jats:tex-math>\n \n FC<\/mml:mi>\n -<\/mml:mo>\n CQ<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> based on the logic $${\\textsf{FC}}$$<\/jats:tex-math>\n FC<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, it can equally be understood as synchronized intersections of pattern languages, or as systems of restricted word equations.<\/jats:p>","DOI":"10.1007\/s00224-024-10198-4","type":"journal-article","created":{"date-parts":[[2024,10,10]],"date-time":"2024-10-10T07:01:59Z","timestamp":1728543719000},"page":"1640-1682","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Languages Generated by Conjunctive\u00a0Query\u00a0Fragments of\u00a0FC[REG]"],"prefix":"10.1007","volume":"68","author":[{"given":"Sam M.","family":"Thompson","sequence":"first","affiliation":[]},{"given":"Dominik D.","family":"Freydenberger","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,10,10]]},"reference":[{"issue":"3","key":"10198_CR1","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1145\/337244.337255","volume":"47","author":"J Karhum\u00e4ki","year":"2000","unstructured":"Karhum\u00e4ki, J., Mignosi, F., Plandowski, W.: The expressibility of languages and relations by word equations. J. ACM 47(3), 483\u2013505 (2000)","journal-title":"J. ACM"},{"issue":"2","key":"10198_CR2","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.ic.2005.04.002","volume":"202","author":"V Diekert","year":"2005","unstructured":"Diekert, V., Gutierrez, C., Hagenah, C.: The existential theory of equations with rational constraints in free groups is PSPACE-complete. Inf. Comput. 202(2), 105\u2013140 (2005)","journal-title":"Inf. Comput."},{"issue":"5","key":"10198_CR3","doi-asserted-by":"publisher","first-page":"917","DOI":"10.1007\/BF02112533","volume":"36","author":"VG Durnev","year":"1995","unstructured":"Durnev, V.G.: Undecidability of the positive $$\\forall \\exists $$ 3-theory of a free semigroup. Sib. Math. J. 36(5), 917\u2013929 (1995)","journal-title":"Sib. Math. J."},{"key":"10198_CR4","unstructured":"Freydenberger, D.D., Peterfreund, L.: The theory of concatenation over finite models. In: Proceedings of ICALP\u00a02021, pp. 130\u2013113017 (2021)"},{"issue":"2","key":"10198_CR5","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/2699442","volume":"62","author":"R Fagin","year":"2015","unstructured":"Fagin, R., Kimelfeld, B., Reiss, F., Vansummeren, S.: Document spanners: A formal approach to information extraction. J. ACM 62(2), 12 (2015)","journal-title":"J. ACM"},{"key":"10198_CR6","doi-asserted-by":"crossref","unstructured":"Freydenberger, D.D., Kimelfeld, B., Peterfreund, L.: Joining extractions of regular expressions. In: Proceedings of PODS\u00a02018, pp. 137\u2013149 (2018)","DOI":"10.1145\/3196959.3196967"},{"key":"10198_CR7","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases vol. 8. Addison-Wesley Reading, Reading (1995)"},{"key":"10198_CR8","unstructured":"Freydenberger, D.D., Thompson, S.M.: Splitting spanner atoms: A tool for acyclic core spanners. In: Proceedings of ICDT\u00a02022, pp. 6\u20131618 (2022)"},{"issue":"7","key":"10198_CR9","doi-asserted-by":"publisher","first-page":"1679","DOI":"10.1007\/s00224-018-9874-1","volume":"63","author":"DD Freydenberger","year":"2019","unstructured":"Freydenberger, D.D.: A logic for document spanners. Theory Comput. Syst. 63(7), 1679\u20131754 (2019)","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"10198_CR10","doi-asserted-by":"publisher","first-page":"854","DOI":"10.1007\/s00224-017-9770-0","volume":"62","author":"DD Freydenberger","year":"2018","unstructured":"Freydenberger, D.D., Holldack, M.: Document spanners: From expressive power to decision problems. Theory Comput. Syst. 62(4), 854\u2013898 (2018)","journal-title":"Theory Comput. Syst."},{"key":"10198_CR11","doi-asserted-by":"crossref","unstructured":"Thompson, S.M., Freydenberger, D.D.: Generalized core spanner inexpressibility via Ehrenfeucht-Fra\u00efss\u00e9 games for FC. arXiv:2306.16364 (2023)","DOI":"10.1145\/3651143"},{"issue":"1","key":"10198_CR12","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/0022-0000(80)90041-0","volume":"21","author":"D Angluin","year":"1980","unstructured":"Angluin, D.: Finding patterns common to a set of strings. J. Comput. Syst. Sci. 21(1), 46\u201362 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"10198_CR13","doi-asserted-by":"crossref","unstructured":"Geilke, M., Zilles, S.: Polynomial-time algorithms for learning typed pattern languages. In: International Conference on Language and Automata Theory and Applications, pp. 277\u2013288 (2012)","DOI":"10.1007\/978-3-642-28332-1_24"},{"key":"10198_CR14","doi-asserted-by":"crossref","unstructured":"Koshiba, T.: Typed pattern languages and their learnability. In: European Conference on Computational Learning Theory, pp. 367\u2013379 (1995)","DOI":"10.1007\/3-540-59119-2_192"},{"key":"10198_CR15","doi-asserted-by":"crossref","unstructured":"Schmid, M.L.: Inside the class of regex languages. In: Proceedings of DLT\u00a02012, pp. 73\u201384 (2012)","DOI":"10.1007\/978-3-642-31653-1_8"},{"key":"10198_CR16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511566097","volume-title":"Combinatorics on Words","author":"M Lothaire","year":"1997","unstructured":"Lothaire, M.: Combinatorics on Words, vol. 17. Cambridge University Press, Cambridge (1997)"},{"key":"10198_CR17","doi-asserted-by":"crossref","unstructured":"Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages, Volume 1: Word, Language, Grammar. Springer, Berlin (1997)","DOI":"10.1007\/978-3-642-59136-5"},{"key":"10198_CR18","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"JE Hopcroft","year":"2006","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, vol. 3. Addison-Wesley Longman Publishing Co., Inc, New York (2006)"},{"key":"10198_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2019.04.001","volume":"105","author":"DD Freydenberger","year":"2019","unstructured":"Freydenberger, D.D., Schmid, M.L.: Deterministic regular expressions with back-references. J. Comput. Syst. Sci. 105, 1\u201339 (2019)","journal-title":"J. Comput. Syst. Sci."},{"key":"10198_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2016.02.003","volume":"249","author":"ML Schmid","year":"2016","unstructured":"Schmid, M.L.: Characterising REGEX languages by regular languages equipped with factor-referencing. Inf. Comput. 249, 1\u201317 (2016)","journal-title":"Inf. Comput."},{"key":"10198_CR21","doi-asserted-by":"crossref","unstructured":"Carle, B., Narendran, P.: On extended regular expressions. In: Proceedings of LATA\u00a02009, pp. 279\u2013289 (2009)","DOI":"10.1007\/978-3-642-00982-2_24"},{"key":"10198_CR22","doi-asserted-by":"crossref","unstructured":"Shinohara, T.: Polynomial time inference of extended regular pattern languages. In: RIMS Symposia on Software Science and Engineering, pp. 115\u2013127 (1983)","DOI":"10.1007\/3-540-11980-9_19"},{"issue":"2","key":"10198_CR23","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0020-0190(79)90135-2","volume":"9","author":"A Ehrenfreucht","year":"1979","unstructured":"Ehrenfreucht, A., Rozenberg, G.: Finding a homomorphism between two words is NP-complete. Inf. Process. Lett. 9(2), 86\u201388 (1979)","journal-title":"Inf. Process. Lett."},{"key":"10198_CR24","doi-asserted-by":"crossref","unstructured":"Manea, F., Schmid, M.L.: Matching patterns with variables. In: Combinatorics on Words: 12th International Conference, WORDS 2019, Loughborough, UK, September 9\u201313, 2019, Proceedings 12, pp. 1\u201327. Springer (2019)","DOI":"10.1007\/978-3-030-28796-2_1"},{"key":"10198_CR25","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/j.ic.2015.03.006","volume":"242","author":"H Fernau","year":"2015","unstructured":"Fernau, H., Schmid, M.L.: Pattern matching with variables: A multivariate complexity analysis. Inf. Comput. 242, 287\u2013305 (2015)","journal-title":"Inf. Comput."},{"issue":"1","key":"10198_CR26","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/s00224-015-9635-3","volume":"59","author":"H Fernau","year":"2016","unstructured":"Fernau, H., Schmid, M.L., Villanger, Y.: On the parameterised complexity of string morphism problems. Theory Comput. Syst. 59(1), 24\u201351 (2016)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"10198_CR27","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1145\/990308.990312","volume":"51","author":"W Plandowski","year":"2004","unstructured":"Plandowski, W.: Satisfiability of word equations with constants is in PSPACE. J. ACM 51(3), 483\u2013496 (2004)","journal-title":"J. ACM"},{"key":"10198_CR28","doi-asserted-by":"crossref","unstructured":"Manea, F., Nowotka, D., Schmid, M.L.: On the solvability problem for restricted classes of word equations. In: International Conference on Developments in Language Theory, pp. 306\u2013318. Springer (2016)","DOI":"10.1007\/978-3-662-53132-7_25"},{"key":"10198_CR29","unstructured":"Day, J.D., Manea, F., Nowotka, D.: The hardness of solving simple word equations. In: Proceedings of MFCS\u00a02017, pp. 18\u201311814 (2017)"},{"key":"10198_CR30","doi-asserted-by":"crossref","unstructured":"Diekert, V., Robson, J.M.: Quadratic word equations. Jewels are Forever: Contributions on Theoretical Computer Science in Honor of Arto Salomaa, pp. 314\u2013326 (1999)","DOI":"10.1007\/978-3-642-60207-8_28"},{"issue":"2","key":"10198_CR31","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s00224-012-9389-0","volume":"53","author":"DD Freydenberger","year":"2013","unstructured":"Freydenberger, D.D.: Extended regular expressions: Succinctness and decidability. Theory Comput. Syst. 53(2), 159\u2013193 (2013)","journal-title":"Theory Comput. Syst."},{"issue":"05","key":"10198_CR32","doi-asserted-by":"publisher","first-page":"957","DOI":"10.1142\/S0129054105003406","volume":"16","author":"M Kutrib","year":"2005","unstructured":"Kutrib, M.: The phenomenon of non-recursive trade-offs. Int. J. Found. Comput. Sci. 16(05), 957\u2013973 (2005)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"3","key":"10198_CR33","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/0304-3975(83)90016-6","volume":"26","author":"J Hartmanis","year":"1983","unstructured":"Hartmanis, J.: On G\u00f6del speed-up and succinctness of language representations. Theor. Comput. Sci. 26(3), 335\u2013342 (1983)","journal-title":"Theor. Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10198-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10198-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10198-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,14]],"date-time":"2024-12-14T06:03:12Z","timestamp":1734156192000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10198-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,10]]},"references-count":33,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["10198"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10198-4","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2024,10,10]]},"assertion":[{"value":"19 September 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 October 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}