{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T18:13:14Z","timestamp":1771697594137,"version":"3.50.1"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2013,8,1]],"date-time":"2013-08-01T00:00:00Z","timestamp":1375315200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-08-DEFIS-004"],"award-info":[{"award-number":["ANR-08-DEFIS-004"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2013,8]]},"abstract":"<jats:p>Type inclusion is a fundamental operation in every type-checking compiler, but it is quite expensive for XML manipulation languages. A polynomial inclusion checking algorithm for an expressive family of XML type languages is known, but it runs in quadratic time both in the best and in the worst cases. We present here an algorithm that has a linear-time backbone, and resorts to the quadratic approach for some specific parts of the compared types. Our experiments show that the new algorithm is much faster than the quadratic one, and that it typically runs in linear time, hence it can be used as a building block for a practical type-checking compiler.<\/jats:p>","DOI":"10.1145\/2508020.2508022","type":"journal-article","created":{"date-parts":[[2013,9,3]],"date-time":"2013-09-03T11:57:11Z","timestamp":1378209431000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Almost-linear inclusion for XML regular expression types"],"prefix":"10.1145","volume":"38","author":[{"given":"Dario","family":"Colazzo","sequence":"first","affiliation":[{"name":"Universit\u00e9 Paris Sud\/INRIA, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giorgio","family":"Ghelli","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luca","family":"Pardini","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carlo","family":"Sartiani","sequence":"additional","affiliation":[{"name":"Universit\u00e0 della Basilicata, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,9,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/646388.690192"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017074.1017095"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 32nd International Conference on Very Large Data Bases. U. Dayal, K.-Y. Whang, D. B. Lomet, G. Alonso, G. M. Lohman, M. L. Kersten, S. K. Cha, and Y.-K. Kim, Eds., ACM Press","author":"Bex G. J.","unstructured":"Bex , G. J. , Neven , F. , Schwentick , T. , and Tuyls , K . 2006. Inference of concise dtds from XML data . In Proceedings of the 32nd International Conference on Very Large Data Bases. U. Dayal, K.-Y. Whang, D. B. Lomet, G. Alonso, G. M. Lohman, M. L. Kersten, S. K. Cha, and Y.-K. Kim, Eds., ACM Press , New York, 115--126. Bex, G. J., Neven, F., Schwentick, T., and Tuyls, K. 2006. Inference of concise dtds from XML data. In Proceedings of the 32nd International Conference on Very Large Data Bases. U. Dayal, K.-Y. Whang, D. B. Lomet, G. Alonso, G. M. Lohman, M. L. Kersten, S. K. Cha, and Y.-K. Kim, Eds., ACM Press, New York, 115--126."},{"key":"e_1_2_1_4_1","unstructured":"Biron P. V. and Malhotra A. 2004. XML schema part 2: Datatypes 2nd ed. Tech. rep. World Wide Web Consortium.W3C Recommendation. http:\/\/www.w3.org\/TR\/xmlschema-2\/.  Biron P. V. and Malhotra A. 2004. XML schema part 2: Datatypes 2 nd ed. Tech. rep. World Wide Web Consortium.W3C Recommendation. http:\/\/www.w3.org\/TR\/xmlschema-2\/."},{"key":"e_1_2_1_5_1","unstructured":"Bray T. Paoli J. Sperberg-Mcqueen C. M. Maler E. and Yergeau F. 2008. Extensible markup language (XML) 1.0 5th ed. Tech. rep. World Wide Web Consortium. W3C Recommendation. http:\/\/www.w3.org\/TR\/REC-xml\/.  Bray T. Paoli J. Sperberg-Mcqueen C. M. Maler E. and Yergeau F. 2008. Extensible markup language (XML) 1.0 5 th ed. Tech. rep. World Wide Web Consortium. W3C Recommendation. http:\/\/www.w3.org\/TR\/REC-xml\/."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.03.003"},{"key":"e_1_2_1_7_1","unstructured":"Clark J. and Murata M. 2001. RELAX NG specification. Tech. rep. The Organization for the Advancement of Structured Information Standards (oasis). http:\/\/relaxng.org\/.  Clark J. and Murata M. 2001. RELAX NG specification. Tech. rep. The Organization for the Advancement of Structured Information Standards (oasis). http:\/\/relaxng.org\/."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1645973"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Colazzo D. Ghelli G. Pardini L. and Sartiani C. 2013. Efficient asymmetric inclusion of regular expressions with interleaving and counting for XML type-checking. https:\/\/team.inria.fr\/oak\/2013\/04\/25\/tcs-efficient-asymmetric-inclusion-of-regular-expressions-with-interleaving-and-counting-for-xml-type-checking\/.  Colazzo D. Ghelli G. Pardini L. and Sartiani C. 2013. Efficient asymmetric inclusion of regular expressions with interleaving and counting for XML type-checking. https:\/\/team.inria.fr\/oak\/2013\/04\/25\/tcs-efficient-asymmetric-inclusion-of-regular-expressions-with-interleaving-and-counting-for-xml-type-checking\/.","DOI":"10.1016\/j.tcs.2013.04.023"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514916"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2008.10.001"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2003476.2003490"},{"key":"e_1_2_1_13_1","unstructured":"Fallside D. C. and Walmsley P. 2004. XML schema part 0: Primer -- 2nd ed. W3C Recommendation. http:\/\/dret.net\/biblio\/reference\/xmlschema0sec.  Fallside D. C. and Walmsley P. 2004. XML schema part 0: Primer -- 2 nd ed. W3C Recommendation. http:\/\/dret.net\/biblio\/reference\/xmlschema0sec."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the ACM SIGPLAN Workshop on Programming Language Technologies for XML (PLAN-X'07)","author":"Foster J. N.","unstructured":"Foster J. N. , Pierce , B. C. , and Schmitt , A . 2007. A logic your typechecker can count on: Unordered tree types in practice . In Proceedings of the ACM SIGPLAN Workshop on Programming Language Technologies for XML (PLAN-X'07) , colocated with ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'07). 80--90. Foster J. N., Pierce, B. C., and Schmitt, A. 2007. A logic your typechecker can count on: Unordered tree types in practice. In Proceedings of the ACM SIGPLAN Workshop on Programming Language Technologies for XML (PLAN-X'07), colocated with ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'07). 80--90."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03816-7_32"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11965893_19"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Ghelli G. Colazzo D. and \n      Sartiani C\n  . \n  2007\n  . Efficient inclusion for a class of XML types with interleaving and counting. In Proceedings of the 11th International Symposium on Database Programming Languages (DBPL'07). M. Arenas and M. I. Schwartzbach Eds. Lecture Notes in Computer Science vol. \n  4797 Springer 231--245.   Ghelli G. Colazzo D. and Sartiani C. 2007. Efficient inclusion for a class of XML types with interleaving and counting. In Proceedings of the 11 th International Symposium on Database Programming Languages (DBPL'07). M. Arenas and M. I. Schwartzbach Eds. Lecture Notes in Computer Science vol. 4797 Springer 231--245.","DOI":"10.1007\/978-3-540-75987-4_16"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13089-2_26"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 8th Symposium on Programming Languages and Software Tools (SPLST'03)","author":"Kilpelainen P.","unstructured":"Kilpelainen , P. and Tuhkanen , R . 2003. Regular expressions with numerical occurrence indicators - Preliminary results . In Proceedings of the 8th Symposium on Programming Languages and Software Tools (SPLST'03) . P. Kilpelainen and N. Paivinen, Eds., 163--173. Kilpelainen, P. and Tuhkanen, R. 2003. Regular expressions with numerical occurrence indicators - Preliminary results. In Proceedings of the 8th Symposium on Programming Languages and Software Tools (SPLST'03). P. Kilpelainen and N. Paivinen, Eds., 163--173."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.12.003"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.16"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1098"},{"key":"e_1_2_1_23_1","unstructured":"Thompson H. S. Beech D. Maloney M. and Mendelsohn N. 2004. XML Schema part 1: Structures 2nd ed. Tech. rep. World Wide Web Consortium. W3C Recommendation. http:\/\/www.w3.org\/TR\/xmlschema-1\/.  Thompson H. S. Beech D. Maloney M. and Mendelsohn N. 2004. XML Schema part 1: Structures 2 nd ed. Tech. rep. World Wide Web Consortium. W3C Recommendation. http:\/\/www.w3.org\/TR\/xmlschema-1\/."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2508020.2508022","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2508020.2508022","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:34:09Z","timestamp":1750232049000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2508020.2508022"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,8]]}},"alternative-id":["10.1145\/2508020.2508022"],"URL":"https:\/\/doi.org\/10.1145\/2508020.2508022","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,8]]},"assertion":[{"value":"2012-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-09-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}