{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T08:32:37Z","timestamp":1785227557544,"version":"3.55.0"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>The regular spanners (characterised by vset-automata) are closed under the\nalgebraic operations of union, join and projection, and have desirable\nalgorithmic properties. The core spanners (introduced by Fagin, Kimelfeld,\nReiss, and Vansummeren (PODS 2013, JACM 2015) as a formalisation of the core\nfunctionality of the query language AQL used in IBM's SystemT) additionally\nneed string-equality selections and it has been shown by Freydenberger and\nHolldack (ICDT 2016, Theory of Computing Systems 2018) that this leads to high\ncomplexity and even undecidability of the typical problems in static analysis\nand query evaluation. We propose an alternative approach to core spanners: by\nincorporating the string-equality selections directly into the regular language\nthat represents the underlying regular spanner (instead of treating it as an\nalgebraic operation on the table extracted by the regular spanner), we obtain a\nfragment of core spanners that, while having slightly weaker expressive power\nthan the full class of core spanners, arguably still covers the intuitive\napplications of string-equality selections for information extraction and has\nmuch better upper complexity bounds of the typical problems in static analysis\nand query evaluation.<\/jats:p>","DOI":"10.46298\/lmcs-20(4:16)2024","type":"journal-article","created":{"date-parts":[[2024,11,21]],"date-time":"2024-11-21T23:20:07Z","timestamp":1732231207000},"source":"Crossref","is-referenced-by-count":1,"title":["Refl-Spanners: A Purely Regular Approach to Non-Regular Core Spanners"],"prefix":"10.46298","volume":"Volume 20, Issue 4","author":[{"given":"Markus L.","family":"Schmid","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicole","family":"Schweikardt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"25203","published-online":{"date-parts":[[2024,11,21]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/14824\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/14824\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,21]],"date-time":"2024-11-21T23:20:07Z","timestamp":1732231207000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/8614"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,21]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-20(4:16)2024","relation":{"has-preprint":[{"id-type":"arxiv","id":"2010.13442v5","asserted-by":"subject"},{"id-type":"arxiv","id":"2010.13442v3","asserted-by":"subject"},{"id-type":"arxiv","id":"2010.13442v2","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2010.13442","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2010.13442","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,21]]},"article-number":"8614"}}