{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:12:51Z","timestamp":1750306371646,"version":"3.41.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,6,30]],"date-time":"2016-06-30T00:00:00Z","timestamp":1467244800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2016,8,8]]},"abstract":"<jats:p>\n            We study the problem of bounded repairability of a given restriction tree language\n            <jats:italic>R<\/jats:italic>\n            into a target tree language\n            <jats:italic>T<\/jats:italic>\n            . More precisely, we say that\n            <jats:italic>R<\/jats:italic>\n            is bounded repairable with respect to\n            <jats:italic>T<\/jats:italic>\n            if there exists a bound on the number of standard tree editing operations necessary to apply to any tree in\n            <jats:italic>R<\/jats:italic>\n            to obtain a tree in\n            <jats:italic>T<\/jats:italic>\n            . We consider a number of possible specifications for tree languages: bottom-up tree automata (on curry encoding of unranked trees) that capture the class of XML schemas and document type definitions (DTDs). We also consider a special case when the restriction language\n            <jats:italic>R<\/jats:italic>\n            is universal (i.e., contains all trees over a given alphabet).\n          <\/jats:p>\n          <jats:p>\n            We give an effective characterization of bounded repairability between pairs of tree languages represented with automata. This characterization introduces two tools\u2014synopsis trees and a coverage relation between them\u2014allowing one to reason about tree languages that undergo a bounded number of editing operations. We then employ this characterization to provide upper bounds to the complexity of deciding bounded repairability and show that these bounds are tight. In particular, when the input tree languages are specified with arbitrary bottom-up automata, the problem is coNExp-complete. The problem remains coNExp-complete even if we use deterministic nonrecursive DTDs to specify the input languages. The complexity of the problem can be reduced if we assume that the alphabet, the set of node labels, is fixed: the problem becomes PS\n            <jats:sc>pace<\/jats:sc>\n            -complete for nonrecursive DTDs and coNP-complete for deterministic nonrecursive DTDs. Finally, when the restriction tree language\n            <jats:italic>R<\/jats:italic>\n            is universal, we show that the bounded repairability problem becomes E\n            <jats:sc>xp<\/jats:sc>\n            -complete if the target language is specified by an arbitrary bottom-up tree automaton and becomes tractable (P-complete, in fact) when a deterministic bottom-up automaton is used.\n          <\/jats:p>","DOI":"10.1145\/2898995","type":"journal-article","created":{"date-parts":[[2016,7,5]],"date-time":"2016-07-05T14:08:13Z","timestamp":1467727693000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Bounded Repairability for Regular Tree Languages"],"prefix":"10.1145","volume":"41","author":[{"given":"Pierre","family":"Bourhis","sequence":"first","affiliation":[{"name":"CNRS\u2014CRIStAL UMR 9189"}]},{"given":"Gabriele","family":"Puppis","sequence":"additional","affiliation":[{"name":"CNRS\u2014LaBRI, University of Bordeaux"}]},{"given":"Cristian","family":"Riveros","sequence":"additional","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile, Santiago, Chile"}]},{"given":"S\u0142awek","family":"Staworko","sequence":"additional","affiliation":[{"name":"INRIA Lille-Nord Europe, University of Lille and LFCS, University of Edinburgh, Edinburgh, United Kingdom"}]}],"member":"320","published-online":{"date-parts":[[2016,6,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514899"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201022"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516518"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559801"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9428-x"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303983"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1346330.1346332"},{"volume-title":"Green, Longman, Roberts, & Green","author":"Babbage Charles","key":"e_1_2_2_8_1","unstructured":"Charles Babbage . 1864. Passages from the Life of a Philosopher. Longman , Green, Longman, Roberts, & Green , London, England . Charles Babbage. 1864. Passages from the Life of a Philosopher. Longman, Green, Longman, Roberts, & Green, London, England."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.06.001"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.04.021"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2371212"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.12.030"},{"volume-title":"Complexity, Logic, and Recursion Theory","author":"Emde Boas Peter Van","key":"e_1_2_2_13_1","unstructured":"Peter Van Emde Boas . 1997. The convenience of tilings . In Complexity, Logic, and Recursion Theory . Marcel Dekker , 331--363. Peter Van Emde Boas. 1997. The convenience of tilings. In Complexity, Logic, and Recursion Theory. Marcel Dekker, 331--363."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1938551.1938567"},{"key":"e_1_2_2_15_1","series-title":"Lecture Notes in Computer Science","volume-title":"Database and XML Technologies","author":"Boobna Utsav","unstructured":"Utsav Boobna and Michel de Rougemont . 2004. Correctors for XML data . In Database and XML Technologies . Lecture Notes in Computer Science , Vol. 3186 . Springer , 97--111. Utsav Boobna and Michel de Rougemont. 2004. Correctors for XML data. In Database and XML Technologies. Lecture Notes in Computer Science, Vol. 3186. Springer, 97--111."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448496.2448505"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2695"},{"volume-title":"Rewriting Techniques and Applications","author":"Carme Julien","key":"e_1_2_2_18_1","unstructured":"Julien Carme , Joachim Niehren , and Marc Tommasi . 2004. Querying unranked trees with stepwise tree automata . In Rewriting Techniques and Applications . Springer , 105--118. Julien Carme, Joachim Niehren, and Marc Tommasi. 2004. Querying unranked trees with stepwise tree automata. In Rewriting Techniques and Applications. Springer, 105--118."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.03.003"},{"volume-title":"Proceedings of the 2005 International Conference on Internet Computing (ICOMP\u201905)","author":"Chen Shan","key":"e_1_2_2_20_1","unstructured":"Shan Chen , Dan Hong , and Vincent Y. Shen . 2005. An experimental study on validation problems with existing HTML Webpages . In Proceedings of the 2005 International Conference on Internet Computing (ICOMP\u201905) . 373. Shan Chen, Dan Hong, and Vincent Y. Shen. 2005. An experimental study on validation problems with existing HTML Webpages. In Proceedings of the 2005 International Conference on Internet Computing (ICOMP\u201905). 373."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508020.2508022"},{"key":"e_1_2_2_22_1","volume-title":"Tree Automata Techniques and Applications. Retrieved","author":"Comon Hubert","year":"2016","unstructured":"Hubert Comon , Max Dauchet , R\u00e9mi Gilleron , Christof L\u00f6ding , Florent Jacquemard , Denis Lugiez , Sophie Tison , and Marc Tommasi . 2007. Tree Automata Techniques and Applications. Retrieved June 2, 2016 , from http:\/\/www.grappa.univ-lille3.fr\/tata. Hubert Comon, Max Dauchet, R\u00e9mi Gilleron, Christof L\u00f6ding, Florent Jacquemard, Denis Lugiez, Sophie Tison, and Marc Tommasi. 2007. Tree Automata Techniques and Applications. Retrieved June 2, 2016, from http:\/\/www.grappa.univ-lille3.fr\/tata."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186810.1186812"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/362007.362035"},{"volume-title":"XML Schema Part 0: Primer","author":"Fallside David","key":"e_1_2_2_25_1","unstructured":"David Fallside and Priscilla Walmsley . 2004. XML Schema Part 0: Primer Second Edition. W3C Recommendation . David Fallside and Priscilla Walmsley. 2004. XML Schema Part 0: Primer Second Edition. W3C Recommendation."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1331904.1331908"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/11581062_14"},{"volume-title":"Foundations of Information and Knowledge Systems","author":"Grahne G\u00f6sta","key":"e_1_2_2_28_1","unstructured":"G\u00f6sta Grahne and Alex Thomo . 2004. Query answering and containment for regular path queries under distortions . In Foundations of Information and Knowledge Systems . Springer , 98--115. G\u00f6sta Grahne and Alex Thomo. 2004. Query answering and containment for regular path queries under distortions. In Foundations of Information and Knowledge Systems. Springer, 98--115."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2012.12.001"},{"volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft John","key":"e_1_2_2_30_1","unstructured":"John Hopcroft and Jeffrey Ullman . 1979. Introduction to Automata Theory, Languages, and Computation . Addison-Wesley . John Hopcroft and Jeffrey Ullman. 1979. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536360.2536361"},{"volume-title":"Influence Perception, Increase Appeal, Make Better Design Decisions","author":"Lidwell William","key":"e_1_2_2_32_1","unstructured":"William Lidwell , Kritina Holden , and Jill Butler . 2010. Universal Principles of Design, Revised and Updated: 125 Ways to Enhance Usability , Influence Perception, Increase Appeal, Make Better Design Decisions . Rockport Publishers . William Lidwell, Kritina Holden, and Jill Butler. 2010. Universal Principles of Design, Revised and Updated: 125 Ways to Enhance Usability, Influence Perception, Increase Appeal, Make Better Design Decisions. Rockport Publishers."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1957995.1958009"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166076"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.021"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1108\/14684521011024182"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274593"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780100057"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_32"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.003"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/11965893_21"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543622"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219027"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/11896548_16"},{"key":"e_1_2_2_45_1","volume-title":"Proceedings of the International Workshop on Logic in Databases (LiD\u201908)","author":"Staworko Slawomir","year":"2008","unstructured":"Slawomir Staworko , Emmanuel Filiot , and Jan Chomicki . 2008 . Querying regular sets of XML documents . In Proceedings of the International Workshop on Logic in Databases (LiD\u201908) . Slawomir Staworko, Emmanuel Filiot, and Jan Chomicki. 2008. Querying regular sets of XML documents. In Proceedings of the International Workshop on Logic in Databases (LiD\u201908)."},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804029"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066677.1066825"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/322139.322143"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/360980.360995"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)80007-X"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2898995","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2898995","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:56:30Z","timestamp":1750222590000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2898995"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,30]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,8,8]]}},"alternative-id":["10.1145\/2898995"],"URL":"https:\/\/doi.org\/10.1145\/2898995","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2016,6,30]]},"assertion":[{"value":"2014-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-06-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}