{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T07:22:49Z","timestamp":1760080969054,"version":"3.44.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100006374","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\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>Despite considerable research on document spanners, little is known about the expressive power of generalized core spanners. In this paper, we use Ehrenfeucht-Fra\u00efss\u00e9 games to obtain general inexpressibility lemmas for the logic FC (a finite model variant of the theory of concatenation). Applying these lemmas give inexpressibility results for FC that we lift to generalized core spanners. In particular, we give several relations that cannot be selected by generalized core spanners, thus demonstrating the effectiveness of the inexpressibility lemmas. As an immediate consequence, we also gain new insights into the expressive power of core spanners.<\/jats:p>","DOI":"10.1145\/3651143","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-18","source":"Crossref","is-referenced-by-count":3,"title":["Generalized Core Spanner Inexpressibility via Ehrenfeucht-Fra\u00efss\u00e9 Games for FC"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3476-6739","authenticated-orcid":false,"given":"Sam M.","family":"Thompson","sequence":"first","affiliation":[{"name":"Loughborough University, Loughborough, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5088-0067","authenticated-orcid":false,"given":"Dominik D.","family":"Freydenberger","sequence":"additional","affiliation":[{"name":"Loughborough University, Loughborough, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exab048"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3422648.3422655"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics. 128--137","author":"Chiticariu Laura","year":"2010","unstructured":"Laura Chiticariu, Rajasekar Krishnamurthy, Yunyao Li, Sriram Raghavan, Frederick Reiss, and Shivakumar Vaithyanathan. 2010. SystemT: An algebraic approach to declarative information extraction. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics. 128--137."},{"volume-title":"Finite model theory","author":"Ebbinghaus Heinz-Dieter","key":"e_1_2_1_4_1","unstructured":"Heinz-Dieter Ebbinghaus and J\u00f6rg Flum. 1999. Finite model theory. Springer Science & Business Media."},{"key":"e_1_2_1_5_1","volume-title":"Easier ways to win logical games. Descriptive complexity and finite models","author":"Fagin Ronald","year":"1996","unstructured":"Ronald Fagin. 1996. Easier ways to win logical games. Descriptive complexity and finite models , Vol. 31 (1996), 1--32."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699442"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1965-0174934-9"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3351451"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-018-9874-1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9770-0"},{"key":"e_1_2_1_11_1","volume-title":"The theory of concatenation over finite models. arXiv preprint arXiv:1912.06110","author":"Freydenberger Dominik D","year":"2019","unstructured":"Dominik D Freydenberger and Liat Peterfreund. 2019. The theory of concatenation over finite models. arXiv preprint arXiv:1912.06110 (2019)."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of ICALP","author":"Dominik","year":"2021","unstructured":"Dominik D. Freydenberger and Liat Peterfreund. 2021. The theory of concatenation over finite models. In Proceedings of ICALP 2021. 130:1--130:17."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of ICDT","author":"Dominik","year":"2022","unstructured":"Dominik D. Freydenberger and Sam M. Thompson. 2022. Splitting Spanner Atoms: A Tool for Acyclic Core Spanners. In Proceedings of ICDT 2022. 6:1--6:18."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1966.16.285"},{"volume-title":"Language and Automata Theory and Applications: 9th International Conference, LATA 2015, Nice, France, March 2--6, 2015, Proceedings. Springer, 414--423","author":"Hadravov\u00e1 Jana","key":"e_1_2_1_15_1","unstructured":"Jana Hadravov\u00e1 and vS tve p\u00e1n Holub. 2015. Equation $x^i y^j x^k = u^i v^j u^k$ in Words. In Language and Automata Theory and Applications: 9th International Conference, LATA 2015, Nice, France, March 2--6, 2015, Proceedings. Springer, 414--423."},{"volume-title":"Descriptive complexity","author":"Immerman Neil","key":"e_1_2_1_16_1","unstructured":"Neil Immerman. 1998. Descriptive complexity. Springer Science & Business Media."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90002-1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/337244.337255"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1519103.1519105"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the ACL-HLT 2011 System Demonstrations. 109--114","author":"Li Yunyao","year":"2011","unstructured":"Yunyao Li, Frederick Reiss, and Laura Chiticariu. 2011. SystemT: A declarative information extraction system. In Proceedings of the ACL-HLT 2011 System Demonstrations. 109--114."},{"volume-title":"Elements of finite model theory","author":"Libkin Leonid","key":"e_1_2_1_21_1","unstructured":"Leonid Libkin. 2004. Elements of finite model theory. Springer."},{"volume-title":"Combinatorics on words","author":"Lothaire M.","key":"e_1_2_1_22_1","unstructured":"M. Lothaire. 1997. Combinatorics on words. Vol. 17. Cambridge university press."},{"volume-title":"Algebraic combinatorics on words","author":"Lothaire M.","key":"e_1_2_1_23_1","unstructured":"M. Lothaire. 2002. Algebraic combinatorics on words. Vol. 90. Cambridge university press."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2003.11.002"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of ICDT","author":"Peterfreund Liat","year":"2021","unstructured":"Liat Peterfreund. 2021. Grammars for Document Spanners. In Proceedings of ICDT 2021. 7:1--7:18."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of ICDT","author":"Peterfreund Liat","year":"2019","unstructured":"Liat Peterfreund, Balder ten Cate, Ronald Fagin, and Benny Kimelfeld. 2019. Recursive Programs for Document Spanners. In Proceedings of ICDT 2019. 13:1--13:18."},{"volume-title":"Grammar","author":"Rozenberg Grzegorz","key":"e_1_2_1_27_1","unstructured":"Grzegorz Rozenberg and Arto Salomaa. 1997. Handbook of Formal Languages, Volume 1: Word, Language, Grammar. Springer."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of ICDT","author":"Markus","year":"2021","unstructured":"Markus L. Schmid and Nicole Schweikardt. 2021a. A Purely Regular Approach to Non-Regular Core Spanners. In Proceedings of ICDT 2021. 4:1--4:19."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of PODS","author":"Markus","year":"2021","unstructured":"Markus L. Schmid and Nicole Schweikardt. 2021b. Spanner evaluation over SLP-compressed documents. In Proceedings of PODS 2021. 153--165."},{"volume-title":"Colloquium on Trees in Algebra and Programming","author":"Thomas Wolfgang","key":"e_1_2_1_30_1","unstructured":"Wolfgang Thomas. 1993. On the Ehrenfeucht-Fra\"iss\u00e9 game in theoretical computer science. In Colloquium on Trees in Algebra and Programming. Springer, 559--568."},{"key":"e_1_2_1_31_1","volume-title":"2023 a. Generalized Core Spanner Inexpressibility via Ehrenfeucht-Fra\" iss\u00e9 Games for FC. arXiv preprint arXiv:2306.16364","author":"Thompson Sam M","year":"2023","unstructured":"Sam M Thompson and Dominik D Freydenberger. 2023 a. Generalized Core Spanner Inexpressibility via Ehrenfeucht-Fra\" iss\u00e9 Games for FC. arXiv preprint arXiv:2306.16364 (2023)."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of DLT","author":"Sam","year":"2023","unstructured":"Sam M. Thompson and Dominik D. Freydenberger. 2023 b. Languages Generated by Conjunctive Query Fragments of FC[REG]. In Proceedings of DLT 2023. 233--245."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651143","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651143","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:39:22Z","timestamp":1755898762000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651143"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651143"],"URL":"https:\/\/doi.org\/10.1145\/3651143","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}