{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T22:29:21Z","timestamp":1791412161256,"version":"4.3.3"},"publisher-location":"New York, NY, USA","reference-count":41,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,12]],"date-time":"2022-06-12T00:00:00Z","timestamp":1654992000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["416776735, 431183758"],"award-info":[{"award-number":["416776735, 431183758"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,12]]},"DOI":"10.1145\/3517804.3526069","type":"proceedings-article","created":{"date-parts":[[2022,6,13]],"date-time":"2022-06-13T13:29:54Z","timestamp":1655126994000},"page":"139-150","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Document Spanners - A Brief Overview of Concepts, Results, and Recent Developments"],"prefix":"10.1145","author":[{"given":"Markus L.","family":"Schmid","sequence":"first","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicole","family":"Schweikardt","sequence":"additional","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,6,13]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3422648.3422655"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3436487"},{"key":"e_1_3_2_2_3_1","volume-title":"ICALP","author":"Casel K.","year":"2016","unstructured":"K. Casel , H. Fernau , S. Gaspers , B. Gras , and M.L. Schmid . 2020. On the Complexity of the Smallest Grammar Problem over Fixed Alphabets. Theory of Computing Systems (2020). https:\/\/doi.org\/10.1007\/s00224-020--10013-w Conference version appeared in Proc . ICALP 2016 .. 10.1007\/s00224-020--10013-w K. Casel, H. Fernau, S. Gaspers, B. Gras, and M.L. Schmid. 2020. On the Complexity of the Smallest Grammar Problem over Fixed Alphabets. Theory of Computing Systems (2020). https:\/\/doi.org\/10.1007\/s00224-020--10013-w Conference version appeared in Proc. ICALP 2016.."},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.850116"},{"key":"e_1_3_2_2_5_1","volume-title":"47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8--11, 2020, Saarbr\u00fccken, Germany (Virtual Conference). 124:1--124:16","author":"Joel","year":"2020","unstructured":"Joel D. Day and Florin Manea. 2020. On the Structure of Solution Sets to Regular Word Equations. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8--11, 2020, Saarbr\u00fccken, Germany (Virtual Conference). 124:1--124:16 . https:\/\/doi.org\/10.4230\/LIPIcs.ICALP. 2020 .124 10.4230\/LIPIcs.ICALP.2020.124 Joel D. Day and Florin Manea. 2020. On the Structure of Solution Sets to Regular Word Equations. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8--11, 2020, Saarbr\u00fccken, Germany (Virtual Conference). 124:1--124:16. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.124"},{"key":"e_1_3_2_2_6_1","volume-title":"CAI 2015, Stuttgart, Germany, September 1--4, 2015. Proceedings. 22--28","author":"Diekert Volker","year":"2015","unstructured":"Volker Diekert . 2015 . More Than 1700 Years of Word Equations. In Algebraic Informatics - 6th International Conference , CAI 2015, Stuttgart, Germany, September 1--4, 2015. Proceedings. 22--28 . https:\/\/doi.org\/10.1007\/978--3--319--23021--4_2 10.1007\/978--3--319--23021--4_2 Volker Diekert. 2015. More Than 1700 Years of Word Equations. In Algebraic Informatics - 6th International Conference, CAI 2015, Stuttgart, Germany, September 1--4, 2015. Proceedings. 22--28. https:\/\/doi.org\/10.1007\/978--3--319--23021--4_2"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319684"},{"key":"e_1_3_2_2_8_1","volume-title":"Weight Annotation in Information Extraction. In 23rd International Conference on Database Theory, ICDT 2020","author":"Doleschal Johannes","year":"2020","unstructured":"Johannes Doleschal , Benny Kimelfeld , Wim Martens , and Liat Peterfreund . 2020 . Weight Annotation in Information Extraction. In 23rd International Conference on Database Theory, ICDT 2020 , March 30 - April 2, 2020, Copenhagen, Denmark. 8:1--8:18. https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2020.8 10.4230\/LIPIcs.ICDT.2020.8 Johannes Doleschal, Benny Kimelfeld, Wim Martens, and Liat Peterfreund. 2020. Weight Annotation in Information Extraction. In 23rd International Conference on Database Theory, ICDT 2020, March 30-April 2, 2020, Copenhagen, Denmark. 8:1--8:18. https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2020.8"},{"key":"e_1_3_2_2_9_1","volume-title":"ACM","volume":"62","author":"Fagin R.","year":"2015","unstructured":"R. Fagin , B. Kimelfeld , F. Reiss , and S. Vansummeren . 2015. Document Spanners: A Formal Approach to Information Extraction. J . ACM , Vol. 62 , 2 ( 2015 ), 12:1--12:51. Conference version appeared in Proc. PODS 2013.. R. Fagin, B. Kimelfeld, F. Reiss, and S. Vansummeren. 2015. Document Spanners: A Formal Approach to Information Extraction. J. ACM, Vol. 62, 2 (2015), 12:1--12:51. Conference version appeared in Proc. PODS 2013.."},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3351451"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-018-9874-1"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9770-0"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196967"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2019.04.001"},{"key":"e_1_3_2_2_15_1","volume-title":"Dynamic Complexity of Document Spanners. In 23rd International Conference on Database Theory, ICDT 2020","author":"Dominik","year":"2020","unstructured":"Dominik D. Freydenberger and Sam M. Thompson. 2020 . Dynamic Complexity of Document Spanners. In 23rd International Conference on Database Theory, ICDT 2020 , March 30 - April 2, 2020 , Copenhagen, Denmark. 11:1--11:21. https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2020.11 10.4230\/LIPIcs.ICDT.2020.11 Dominik D. Freydenberger and Sam M. Thompson. 2020. Dynamic Complexity of Document Spanners. In 23rd International Conference on Database Theory, ICDT 2020, March 30-April 2, 2020, Copenhagen, Denmark. 11:1--11:21. https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2020.11"},{"key":"e_1_3_2_2_16_1","volume-title":"Splitting Spanner Atoms: A Tool for Acyclic Core Spanners. In 25th International Conference on Database Theory, ICDT 2022, March 29 to April 1, 2022, Edinburgh, UK (Virtual Conference). 10:1--10:18","author":"Dominik","year":"2022","unstructured":"Dominik D. Freydenberger and Sam M. Thompson. 2022 . Splitting Spanner Atoms: A Tool for Acyclic Core Spanners. In 25th International Conference on Database Theory, ICDT 2022, March 29 to April 1, 2022, Edinburgh, UK (Virtual Conference). 10:1--10:18 . https:\/\/doi.org\/10.4230\/LIPIcs.ICDT. 2022 .10 10.4230\/LIPIcs.ICDT.2022.10 Dominik D. Freydenberger and Sam M. Thompson. 2022. Splitting Spanner Atoms: A Tool for Acyclic Core Spanners. In 25th International Conference on Database Theory, ICDT 2022, March 29 to April 1, 2022, Edinburgh, UK (Virtual Conference). 10:1--10:18. https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2022.10"},{"key":"e_1_3_2_2_17_1","volume-title":"29th Annual European Symposium on Algorithms, ESA 2021, September 6--8, 2021, Lisbon, Portugal (Virtual Conference). 45:1--45:16","author":"Ganardi Moses","year":"2021","unstructured":"Moses Ganardi . 2021 . Compression by Contracting Straight-Line Programs . In 29th Annual European Symposium on Algorithms, ESA 2021, September 6--8, 2021, Lisbon, Portugal (Virtual Conference). 45:1--45:16 . https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2021.45 10.4230\/LIPIcs.ESA.2021.45 Moses Ganardi. 2021. Compression by Contracting Straight-Line Programs. In 29th Annual European Symposium on Algorithms, ESA 2021, September 6--8, 2021, Lisbon, Portugal (Virtual Conference). 45:1--45:16. https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2021.45"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3457389"},{"key":"e_1_3_2_2_19_1","unstructured":"K. Goto S. Maruyama S. Inenaga H. Bannai H. Sakamoto and M. Takeda. 2011. Restructuring Compressed Texts without Explicit Decompression. CoRR Vol. abs\/1107.2729 (2011). http:\/\/arxiv.org\/abs\/1107.2729  K. Goto S. Maruyama S. Inenaga H. Bannai H. Sakamoto and M. Takeda. 2011. Restructuring Compressed Texts without Explicit Decompression. CoRR Vol. abs\/1107.2729 (2011). http:\/\/arxiv.org\/abs\/1107.2729"},{"key":"e_1_3_2_2_20_1","volume-title":"Ullman","author":"Hopcroft John E.","year":"2007","unstructured":"John E. Hopcroft , Rajeev Motwani , and Jeffrey D . Ullman . 2007 . Introduction to automata theory, languages, and computation, 3 rd Edition. Addison-Wesley . John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. 2007. Introduction to automata theory, languages, and computation, 3rd Edition. Addison-Wesley.","edition":"3"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.841160"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1515\/gcc-2012-0016"},{"key":"e_1_3_2_2_23_1","volume-title":"The Compressed Word Problem for Groups Springer Briefs in Mathematics ed.)","author":"Lohrey M.","unstructured":"M. Lohrey . 2014. The Compressed Word Problem for Groups Springer Briefs in Mathematics ed.) . Springer . M. Lohrey. 2014. The Compressed Word Problem for Groups Springer Briefs in Mathematics ed.). Springer."},{"key":"e_1_3_2_2_24_1","volume-title":"WORDS 2019, Loughborough, UK, September 9--13, 2019, Proceedings. 1--27","author":"Manea Florin","unstructured":"Florin Manea and Markus L. Schmid . 2019. Matching Patterns with Variables. In Combinatorics on Words - 12th International Conference , WORDS 2019, Loughborough, UK, September 9--13, 2019, Proceedings. 1--27 . https:\/\/doi.org\/10.1007\/978--3-030--28796--2_1 10.1007\/978--3-030--28796--2_1 Florin Manea and Markus L. Schmid. 2019. Matching Patterns with Variables. In Combinatorics on Words - 12th International Conference, WORDS 2019, Loughborough, UK, September 9--13, 2019, Proceedings. 1--27. https:\/\/doi.org\/10.1007\/978--3-030--28796--2_1"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.01.002"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_4"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196968"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622776.1622780"},{"key":"e_1_3_2_2_29_1","volume-title":"Inferring Sequential Structure. Ph.,D. Dissertation","author":"Nevill-Manning C. G.","unstructured":"C. G. Nevill-Manning . 1996. Inferring Sequential Structure. Ph.,D. Dissertation . University of Waikato , NZ. C. G. Nevill-Manning. 1996. Inferring Sequential Structure. Ph.,D. Dissertation. University of Waikato, NZ."},{"key":"e_1_3_2_2_30_1","unstructured":"L. Peterfreund. 2019. The Complexity of Relational Queries over Extractions from Text. Ph. D. Dissertation.  L. Peterfreund. 2019. The Complexity of Relational Queries over Extractions from Text. Ph. D. Dissertation."},{"key":"e_1_3_2_2_31_1","volume-title":"Grammars for Document Spanners. In 24th International Conference on Database Theory, ICDT 2021","author":"Peterfreund Liat","year":"2021","unstructured":"Liat Peterfreund . 2021 . Grammars for Document Spanners. In 24th International Conference on Database Theory, ICDT 2021 , March 23 --26 , 2021, Nicosia, Cyprus. 7:1--7:18. https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2021.7 10.4230\/LIPIcs.ICDT.2021.7 Liat Peterfreund. 2021. Grammars for Document Spanners. In 24th International Conference on Database Theory, ICDT 2021, March 23--26, 2021, Nicosia, Cyprus. 7:1--7:18. https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2021.7"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319699"},{"key":"e_1_3_2_2_33_1","volume-title":"Recursive Programs for Document Spanners. In 22nd International Conference on Database Theory, ICDT 2019","author":"Peterfreund Liat","year":"2019","unstructured":"Liat Peterfreund , Balder ten Cate , Ronald Fagin , and Benny Kimelfeld . 2019 b . Recursive Programs for Document Spanners. In 22nd International Conference on Database Theory, ICDT 2019 , March 26 --28 , 2019, Lisbon, Portugal. 13:1--13:18. Liat Peterfreund, Balder ten Cate, Ronald Fagin, and Benny Kimelfeld. 2019 b. Recursive Programs for Document Spanners. In 22nd International Conference on Database Theory, ICDT 2019, March 26--28, 2019, Lisbon, Portugal. 13:1--13:18."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"crossref","unstructured":"W. Plandowski and W. Rytter. 1999. Complexity of Language Recognition Problems for Compressed Words. In Jewels are Forever Contributions on Theoretical Computer Science in Honor of Arto Salomaa. 262--272.  W. Plandowski and W. Rytter. 1999. Complexity of Language Recognition Problems for Compressed Words. In Jewels are Forever Contributions on Theoretical Computer Science in Honor of Arto Salomaa. 262--272.","DOI":"10.1007\/978-3-642-60207-8_23"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49116-3_20"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00777-6"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2016.02.003"},{"key":"e_1_3_2_2_38_1","volume-title":"24th International Conference on Database Theory, ICDT 2021","author":"Markus","year":"2021","unstructured":"Markus L. Schmid and Nicole Schweikardt. 2021 a. A Purely Regular Approach to Non-Regular Core Spanners . In 24th International Conference on Database Theory, ICDT 2021 , March 23 --26 , 2021 , Nicosia, Cyprus. 4:1--4:19. https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2021.4 10.4230\/LIPIcs.ICDT.2021.4 Markus L. Schmid and Nicole Schweikardt. 2021 a. A Purely Regular Approach to Non-Regular Core Spanners. In 24th International Conference on Database Theory, ICDT 2021, March 23--26, 2021, Nicosia, Cyprus. 4:1--4:19. https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2021.4"},{"key":"e_1_3_2_2_39_1","volume-title":"PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems","author":"Markus","year":"2021","unstructured":"Markus L. Schmid and Nicole Schweikardt. 2021 b. Spanner Evaluation over SLP-Compressed Documents . In PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems , Virtual Event, China, June 20--25 , 2021 . 153--165. https:\/\/doi.org\/10.1145\/3452021.3458325 10.1145\/3452021.3458325 Markus L. Schmid and Nicole Schweikardt. 2021 b. Spanner Evaluation over SLP-Compressed Documents. In PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Virtual Event, China, June 20--25, 2021. 153--165. https:\/\/doi.org\/10.1145\/3452021.3458325"},{"key":"e_1_3_2_2_40_1","volume-title":"Query Evaluation Over SLP-Represented Document Databases With Complex Document Editing. In PODS'22: Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems.","author":"Markus","unstructured":"Markus L. Schmid and Nicole Schweikardt. 2022 . Query Evaluation Over SLP-Represented Document Databases With Complex Document Editing. In PODS'22: Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. Markus L. Schmid and Nicole Schweikardt. 2022. Query Evaluation Over SLP-Represented Document Databases With Complex Document Editing. In PODS'22: Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems."},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/322344.322346"}],"event":{"name":"SIGMOD\/PODS '22: International Conference on Management of Data","location":"Philadelphia PA USA","acronym":"SIGMOD\/PODS '22","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3517804.3526069","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3517804.3526069","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:04Z","timestamp":1750182544000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3517804.3526069"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,12]]},"references-count":41,"alternative-id":["10.1145\/3517804.3526069","10.1145\/3517804"],"URL":"https:\/\/doi.org\/10.1145\/3517804.3526069","relation":{},"subject":[],"published":{"date-parts":[[2022,6,12]]},"assertion":[{"value":"2022-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}