{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,27]],"date-time":"2025-07-27T07:21:03Z","timestamp":1753600863313,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":73,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["1652303, 1909046, 2112533, 2217058, 2218678, 2114269"],"award-info":[{"award-number":["1652303, 1909046, 2112533, 2217058, 2218678, 2114269"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585178","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"377-390","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Weighted Edit Distance Computation: Strings, Trees, and Dyck"],"prefix":"10.1145","author":[{"given":"Debarati","family":"Das","sequence":"first","affiliation":[{"name":"Pennsylvania State University, USA"}]},{"given":"Jacob","family":"Gilbert","sequence":"additional","affiliation":[{"name":"University of Maryland, USA"}]},{"given":"MohammadTaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[{"name":"University of Maryland, USA"}]},{"given":"Tomasz","family":"Kociumaka","sequence":"additional","affiliation":[{"name":"MPI-INF, Germany"}]},{"given":"Barna","family":"Saha","sequence":"additional","affiliation":[{"name":"University of California at San Diego, San Diego, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Amir Abboud. 2014. Hardness for Easy Problems. https:\/\/www.dropbox.com\/s\/jt9uzljjmormkb7\/EasyHardness.pdf Presented at Satellite Workshop of ICALP (YR-ICALP) \t\t\t\t  Amir Abboud. 2014. Hardness for Easy Problems. https:\/\/www.dropbox.com\/s\/jt9uzljjmormkb7\/EasyHardness.pdf Presented at Satellite Workshop of ICALP (YR-ICALP)"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1061771"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201022"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.12"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.43"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00096"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/090767182"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1053128"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902304"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/15m1011032"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.14"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780590"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.12.030"},{"key":"e_1_3_2_1_14_1","volume-title":"Logic and Automata: History and Perspectives (Texts in Logic and Games","volume":"132","author":"Boja\u0144czyk Miko\u0142aj","year":"2008","unstructured":"Miko\u0142aj Boja\u0144czyk and Igor Walukiewicz . 2008 . Forest algebras . In Logic and Automata: History and Perspectives (Texts in Logic and Games , Vol. 2). Amsterdam University Press, 107\u2013 132 . http:\/\/www.jstor.org\/stable\/j.ctt46mv83.8 Miko\u0142aj Boja\u0144czyk and Igor Walukiewicz. 2008. Forest algebras. In Logic and Automata: History and Perspectives (Texts in Logic and Games, Vol. 2). Amsterdam University Press, 107\u2013132. http:\/\/www.jstor.org\/stable\/j.ctt46mv83.8"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3456807"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316388"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384282"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3381878"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M112720X"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/b978-012722442-8\/50021-5"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(97)00179-7"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3422823"},{"key":"e_1_3_2_1_23_1","volume-title":"Comparing Hierarchical Data in External Memory. In 25th International Conference on Very Large Data Bases, VLDB 1999","author":"Chawathe Sudarshan S.","year":"1999","unstructured":"Sudarshan S. Chawathe . 1999 . Comparing Hierarchical Data in External Memory. In 25th International Conference on Very Large Data Bases, VLDB 1999 . Morgan Kaufmann, 90\u2013101. http:\/\/www.vldb.org\/conf\/ 1999\/P8.pdf Sudarshan S. Chawathe. 1999. Comparing Hierarchical Data in External Memory. In 25th International Conference on Very Large Data Bases, VLDB 1999. Morgan Kaufmann, 90\u2013101. http:\/\/www.vldb.org\/conf\/1999\/P8.pdf"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520057"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.23919\/eusipco55093.2022.9909869"},{"key":"e_1_3_2_1_26_1","unstructured":"Debarati Das Jacob Gilbert MohammadTaghi Hajiaghayi Tomasz Kociumaka and Barna Saha. 2023. Weighted Edit Distance Computation: Strings Trees and Dyck. arxiv:2302.04229. \t\t\t\t  Debarati Das Jacob Gilbert MohammadTaghi Hajiaghayi Tomasz Kociumaka and Barna Saha. 2023. Weighted Edit Distance Computation: Strings Trees and Dyck. arxiv:2302.04229."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/focs54457.2022.00071"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.49"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644015.1644017"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Anita D\u00fcrr. 2022. Improved Bounds for Rectangular Monotone Min-Plus Product. arxiv:2208.02862. \t\t\t\t  Anita D\u00fcrr. 2022. Improved Bounds for Rectangular Monotone Min-Plus Product. arxiv:2208.02862.","DOI":"10.2139\/ssrn.4187498"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355547"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1613676.1613680"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.2307\/2034009"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.21437\/Interspeech.2016-431"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.144"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Dvir Fried Shay Golan Tomasz Kociumaka Tsvi Kopelowitz Ely Porat and Tatiana Starikovskaya. 2022. An Improved Algorithm for The k-Dyck Edit Distance Problem. arxiv:2111.02336v2. \t\t\t\t  Dvir Fried Shay Golan Tomasz Kociumaka Tsvi Kopelowitz Ely Porat and Tatiana Starikovskaya. 2022. An Improved Algorithm for The k-Dyck Edit Distance Problem. arxiv:2111.02336v2.","DOI":"10.1137\/1.9781611977073.144"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/2021.sigmorphon-1.12"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00070"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384300"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1017\/cbo9780511574931"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316371"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"e_1_3_2_1_43_1","volume-title":"Introduction to Formal Language Theory","author":"Harrison Michael A.","year":"2010","unstructured":"Michael A. Harrison . 1978. Introduction to Formal Language Theory ( 1 st ed.). Addison-Wesley Longman Publishing Co., Inc. , Boston, MA, USA . isbn:978-0 2010 29550 Michael A. Harrison. 1978. Introduction to Formal Language Theory (1st ed.). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA. isbn:978-0201029550","edition":"1"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/sfcs.2001.959878"},{"key":"e_1_3_2_1_45_1","volume-title":"Martin","author":"Jurafsky Dan","year":"2009","unstructured":"Dan Jurafsky and James H . Martin . 2009 . Speech and language processing: an introduction to natural language processing, computational linguistics, and speech recognition, 2 nd Edition. Prentice Hall , Pearson Education International. isbn:9780135041963 https:\/\/www.worldcat.org\/oclc\/315913020 Dan Jurafsky and James H. Martin. 2009. Speech and language processing: an introduction to natural language processing, computational linguistics, and speech recognition, 2nd Edition. Prentice Hall, Pearson Education International. isbn:9780135041963 https:\/\/www.worldcat.org\/oclc\/315913020","edition":"2"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-68530-8_8"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.36"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00112"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407818"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384307"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1844-9"},{"key":"e_1_3_2_1_52_1","volume-title":"3rd South American Workshop on String Processing, WSP","author":"Kurtz Stefan","year":"1996","unstructured":"Stefan Kurtz . 1996 . Approximate string searching under weighted edit distance . In 3rd South American Workshop on String Processing, WSP 1996. Carleton University Press, 156\u2013170. Stefan Kurtz. 1996. Approximate string searching under weighted edit distance. In 3rd South American Workshop on String Processing, WSP 1996. Carleton University Press, 156\u2013170."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.80"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/s0097539794264810"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90045-1"},{"key":"e_1_3_2_1_56_1","first-page":"707","article-title":"Binary codes capable of correcting deletions, insertions, and reversals. Soviet physics","volume":"10","author":"Levenshtein Vladimir I.","year":"1965","unstructured":"Vladimir I. Levenshtein . 1965 . Binary codes capable of correcting deletions, insertions, and reversals. Soviet physics . Doklady , 10 (1965), 707 \u2013 710 . Vladimir I. Levenshtein. 1965. Binary codes capable of correcting deletions, insertions, and reversals. Soviet physics. Doklady, 10 (1965), 707\u2013710.","journal-title":"Doklady"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00082"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840446"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00007-y"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(70)90057-4"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPR.2002.1047428"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/s0097539702419650"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/focs.2014.71"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.35"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2022.115"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90064-3"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/6.4.309"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-54256-6"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/322139.322143"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1007\/11496656_29"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80046-2"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/321796.321811"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218082"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Orlando FL USA","acronym":"STOC '23"},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585178","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585178","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585178","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:00Z","timestamp":1750178820000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585178"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":73,"alternative-id":["10.1145\/3564246.3585178","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585178","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}