{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T01:34:26Z","timestamp":1742952866771,"version":"3.40.3"},"publisher-location":"Cham","reference-count":41,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031206429"},{"type":"electronic","value":"9783031206436"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-20643-6_20","type":"book-chapter","created":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T13:18:09Z","timestamp":1667222289000},"page":"275-289","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Matching Patterns with Variables Under Edit Distance"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6993-5440","authenticated-orcid":false,"given":"Pawe\u0142","family":"Gawrychowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6094-3324","authenticated-orcid":false,"given":"Florin","family":"Manea","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7509-8135","authenticated-orcid":false,"given":"Stefan","family":"Siemer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,11,1]]},"reference":[{"key":"20_CR1","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jda.2006.10.001","volume":"5","author":"A Amir","year":"2007","unstructured":"Amir, A., Nor, I.: Generalized function matching. J. Discrete Algorithms 5, 514\u2013523 (2007). https:\/\/doi.org\/10.1016\/j.jda.2006.10.001","journal-title":"J. Discrete Algorithms"},{"issue":"1","key":"20_CR2","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."},{"issue":"3","key":"20_CR3","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1137\/15M1053128","volume":"47","author":"A Backurs","year":"2018","unstructured":"Backurs, A., Indyk, P.: Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). SIAM J. Comput. 47(3), 1087\u20131097 (2018)","journal-title":"SIAM J. Comput."},{"key":"20_CR4","doi-asserted-by":"publisher","unstructured":"Bernardini, G., et al.: String sanitization under edit distance. In: 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). LIPIcs, vol. 161, pp. 7:1\u20137:14 (2020). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2020.7","DOI":"10.4230\/LIPIcs.CPM.2020.7"},{"key":"20_CR5","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.tcs.2019.08.012","volume":"812","author":"G Bernardini","year":"2020","unstructured":"Bernardini, G., Pisanti, N., Pissis, S.P., Rosone, G.: Approximate pattern matching on elastic-degenerate text. Theor. Comput. Sci. 812, 109\u2013122 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR6","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.1142\/S012905410300214X","volume":"14","author":"C C\u00e2mpeanu","year":"2003","unstructured":"C\u00e2mpeanu, C., Salomaa, K., Yu, S.: A formal study of practical regular expressions. Int. J. Found. Comput. Sci. 14, 1007\u20131018 (2003). https:\/\/doi.org\/10.1142\/S012905410300214X","journal-title":"Int. J. Found. Comput. Sci."},{"key":"20_CR7","doi-asserted-by":"publisher","unstructured":"Charalampopoulos, P., Kociumaka, T., Mozes, S.: Dynamic string alignment. In: 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). LIPIcs, vol. 161, pp. 9:1\u20139:13 (2020). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2020.9","DOI":"10.4230\/LIPIcs.CPM.2020.9"},{"key":"20_CR8","doi-asserted-by":"publisher","unstructured":"Charalampopoulos, P., Kociumaka, T., Wellnitz, P.: Faster approximate pattern matching: a unified approach. In: Irani, S. (ed.) 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, pp. 978\u2013989. IEEE (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00095","DOI":"10.1109\/FOCS46700.2020.00095"},{"key":"20_CR9","unstructured":"Charalampopoulos, P., Kociumaka, T., Wellnitz, P.: Faster pattern matching under edit distance. arXiv preprint arXiv:2204.03087 (2022)"},{"key":"20_CR10","doi-asserted-by":"publisher","unstructured":"Day, J.D., Fleischmann, P., Manea, F., Nowotka, D.: Local patterns. In: Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). LIPIcs, vol. 93, pp. 24:1\u201324:14 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2017.24","DOI":"10.4230\/LIPIcs.FSTTCS.2017.24"},{"key":"20_CR11","doi-asserted-by":"publisher","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. In: Monographs in Computer Science, Springer, NY (1999). https:\/\/doi.org\/10.1007\/978-1-4612-0515-9","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"20_CR12","doi-asserted-by":"publisher","unstructured":"Fagin, R., Kimelfeld, B., Reiss, F., Vansummeren, S.: Document spanners: a formal approach to information extraction. J. ACM 62(2), 12:1\u201312:51 (2015). https:\/\/doi.org\/10.1145\/2699442","DOI":"10.1145\/2699442"},{"key":"20_CR13","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.tcs.2018.04.035","volume":"733","author":"H Fernau","year":"2018","unstructured":"Fernau, H., Manea, F., Mercas, R., Schmid, M.L.: Revisiting Shinohara\u2019s algorithm for computing descriptive patterns. Theor. Comput. Sci. 733, 44\u201354 (2018)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR14","doi-asserted-by":"publisher","unstructured":"Fernau, H., Manea, F., Mercas, R., Schmid, M.L.: Pattern matching with variables: efficient algorithms and complexity results. ACM Trans. Comput. Theory 12(1), 6:1\u20136:37 (2020). https:\/\/doi.org\/10.1145\/3369935","DOI":"10.1145\/3369935"},{"key":"20_CR15","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). https:\/\/doi.org\/10.1016\/j.ic.2015.03.006","journal-title":"Inf. Comput."},{"issue":"1","key":"20_CR16","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."},{"key":"20_CR17","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, 159\u2013193 (2013). https:\/\/doi.org\/10.1007\/s00224-012-9389-0","journal-title":"Theory Comput. Syst."},{"issue":"7","key":"20_CR18","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":"20_CR19","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":"20_CR20","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":"20_CR21","volume-title":"Mastering Regular Expressions","author":"JEF Friedl","year":"2006","unstructured":"Friedl, J.E.F.: Mastering Regular Expressions, 3rd edn. O\u2019Reilly, Sebastopol, CA (2006)","edition":"3"},{"key":"20_CR22","doi-asserted-by":"publisher","unstructured":"Gawrychowski, P., Manea, F., Siemer, S.: Matching patterns with variables under hamming distance. In: 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021. LIPIcs, vol. 202, pp. 48:1\u201348:24 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2021.48","DOI":"10.4230\/LIPIcs.MFCS.2021.48"},{"key":"20_CR23","doi-asserted-by":"publisher","unstructured":"Gawrychowski, P., Manea, F., Siemer, S.: Matching patterns with variables under edit distance (2022). https:\/\/doi.org\/10.48550\/ARXIV.2207.07477","DOI":"10.48550\/ARXIV.2207.07477"},{"key":"20_CR24","doi-asserted-by":"publisher","unstructured":"Hoppenworth, G., Bentley, J.W., Gibney, D., Thankachan, S.V.: The fine-grained complexity of median and center string problems under edit distance. In: 28th Annual European Symposium on Algorithms (ESA 2020). LIPIcs, vol. 173, pp. 61:1\u201361:19 (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2020.61","DOI":"10.4230\/LIPIcs.ESA.2020.61"},{"key":"20_CR25","doi-asserted-by":"publisher","unstructured":"Kleest-Mei\u00dfner, S., Sattler, R., Schmid, M.L., Schweikardt, N., Weidlich, M.: Discovering event queries from traces: laying foundations for subsequence-queries with wildcards and gap-size constraints. In: 25th International Conference on Database Theory, ICDT 2022. LIPIcs, vol. 220, pp. 18:1\u201318:21 (2022). https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2022.18","DOI":"10.4230\/LIPIcs.ICDT.2022.18"},{"issue":"2","key":"20_CR26","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0196-6774(89)90010-2","volume":"10","author":"GM Landau","year":"1989","unstructured":"Landau, G.M., Vishkin, U.: Fast parallel and serial approximate string matching. J. Algorithms 10(2), 157\u2013169 (1989)","journal-title":"J. Algorithms"},{"key":"20_CR27","first-page":"8","volume":"1","author":"V Levenshtein","year":"1965","unstructured":"Levenshtein, V.: Binary codes capable of correcting spurious insertions and deletions of ones. Probl. Inf. Transm. 1, 8\u201317 (1965)","journal-title":"Probl. Inf. Transm."},{"key":"20_CR28","first-page":"707","volume":"10","author":"VI Levenshtein","year":"1966","unstructured":"Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions, and reversals. Sov. Phys. Dokl. 10, 707 (1966)","journal-title":"Sov. Phys. Dokl."},{"key":"20_CR29","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511566097","volume-title":"Combinatorics on Words","author":"M Lothaire","year":"1997","unstructured":"Lothaire, M.: Combinatorics on Words. Cambridge University Press, Cambridge (1997). https:\/\/doi.org\/10.1017\/CBO9780511566097"},{"key":"20_CR30","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107326019","volume-title":"Algebraic Combinatorics on Words","author":"M Lothaire","year":"2002","unstructured":"Lothaire, M.: Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002). https:\/\/doi.org\/10.1017\/CBO9781107326019"},{"key":"20_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-030-28796-2_1","volume-title":"Combinatorics on Words","author":"F Manea","year":"2019","unstructured":"Manea, F., Schmid, M.L.: Matching patterns with variables. In: Merca\u015f, R., Reidenbach, D. (eds.) WORDS 2019. LNCS, vol. 11682, pp. 1\u201327. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-28796-2_1"},{"key":"20_CR32","unstructured":"Mieno, T., Pissis, S.P., Stougie, L., Sweering, M.: String sanitization under edit distance: improved and generalized. In: 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021. LIPIcs, vol. 191, pp. 19:1\u201319:18 (2021)"},{"issue":"1","key":"20_CR33","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/375360.375365","volume":"33","author":"G Navarro","year":"2001","unstructured":"Navarro, G.: A guided tour to approximate string matching. ACM Comput. Surv. 33(1), 31\u201388 (2001)","journal-title":"ACM Comput. Surv."},{"issue":"2\u20134","key":"20_CR34","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1016\/j.jda.2004.08.015","volume":"3","author":"F Nicolas","year":"2005","unstructured":"Nicolas, F., Rivals, E.: Hardness results for the center and median string problems under the weighted and unweighted edit distances. J. Discrete Algorithms 3(2\u20134), 390\u2013415 (2005)","journal-title":"J. Discrete Algorithms"},{"key":"20_CR35","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.ic.2014.08.010","volume":"239","author":"D Reidenbach","year":"2014","unstructured":"Reidenbach, D., Schmid, M.L.: Patterns with bounded treewidth. Inf. Comput. 239, 87\u201399 (2014)","journal-title":"Inf. Comput."},{"issue":"1","key":"20_CR36","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1137\/0128004","volume":"28","author":"D Sankoff","year":"1975","unstructured":"Sankoff, D.: Minimal mutation trees of sequences. SIAM J. Appl. Math. 28(1), 35\u201342 (1975)","journal-title":"SIAM J. Appl. Math."},{"issue":"19","key":"20_CR37","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1016\/j.ipl.2013.06.011","volume":"113","author":"ML Schmid","year":"2013","unstructured":"Schmid, M.L.: A note on the complexity of matching patterns with variables. Inf. Process. Lett. 113(19), 729\u2013733 (2013). https:\/\/doi.org\/10.1016\/j.ipl.2013.06.011","journal-title":"Inf. Process. Lett."},{"key":"20_CR38","doi-asserted-by":"publisher","unstructured":"Schmid, M.L., Schweikardt, N.: A purely regular approach to non-regular core spanners. In: Proceedings of the 24th International Conference on Database Theory, ICDT 2021. LIPIcs, vol. 186, pp. 4:1\u20134:19 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2021.4","DOI":"10.4230\/LIPIcs.ICDT.2021.4"},{"key":"20_CR39","doi-asserted-by":"publisher","unstructured":"Schmid, M.L., Schweikardt, N.: Document spanners - a brief overview of concepts, results, and recent developments. In: PODS 2022: International Conference on Management of Data, pp. 139\u2013150. ACM (2022). https:\/\/doi.org\/10.1145\/3517804.3526069","DOI":"10.1145\/3517804.3526069"},{"key":"20_CR40","unstructured":"Shinohara, T.: Polynomial time inference of pattern languages and its application. In: Proceedings of the 7th IBM Symposium on Mathematical Foundations of Computer Science, MFCS, pp. 191\u2013209 (1982)"},{"key":"20_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/3-540-60217-8_13","volume-title":"Algorithmic Learning for Knowledge-Based Systems","author":"T Shinohara","year":"1995","unstructured":"Shinohara, T., Arikawa, S.: Pattern inference. In: Jantke, K.P., Lange, S. (eds.) Algorithmic Learning for Knowledge-Based Systems. LNCS, vol. 961, pp. 259\u2013291. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/3-540-60217-8_13"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-20643-6_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T13:20:50Z","timestamp":1667222450000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-20643-6_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031206429","9783031206436"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-20643-6_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"1 November 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SPIRE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on String Processing and Information Retrieval","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Concepci\u00f3n","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Chile","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 November 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 November 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/spire2022.inf.udec.cl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"43","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"23","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"53% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.62","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}