{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T03:26:40Z","timestamp":1767929200118,"version":"3.49.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2005,1,1]],"date-time":"2005-01-01T00:00:00Z","timestamp":1104537600000},"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. Program. Lang. Syst."],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:p>\n            We propose\n            <jats:italic>regular expression types<\/jats:italic>\n            as a foundation for statically typed XML processing languages. Regular expression types, like most schema languages for XML, introduce regular expression notations such as repetition (*), alternation (|), etc., to describe XML documents. The novelty of our type system is a semantic presentation of subtyping, as inclusion between the sets of documents denoted by two types. We give several examples illustrating the usefulness of this form of subtyping in XML processing.The decision problem for the subtype relation reduces to the inclusion problem between tree automata, which is known to be EXPTIME-complete. To avoid this high complexity in typical cases, we develop a practical algorithm that, unlike classical algorithms based on determinization of tree automata, checks the inclusion relation by a top-down traversal of the original type expressions. The main advantage of this algorithm is that it can exploit the property that type expressions being compared often share portions of their representations. Our algorithm is a variant of Aiken and Murphy's set-inclusion constraint solver, to which are added several new implementation techniques, correctness proofs, and preliminary performance measurements on some small programs in the domain of typed XML processing.\n          <\/jats:p>","DOI":"10.1145\/1053468.1053470","type":"journal-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:30:55Z","timestamp":1123057855000},"page":"46-90","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":102,"title":["Regular expression types for XML"],"prefix":"10.1145","volume":"27","author":[{"given":"Haruo","family":"Hosoya","sequence":"first","affiliation":[{"name":"The University of Tokyo, Tokyo, Japan"}]},{"given":"J\u00e9r\u00f4me","family":"Vouillon","sequence":"additional","affiliation":[{"name":"CNRS and Denis Diderot University, Paris Cedex, France"}]},{"given":"Benjamin C.","family":"Pierce","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}]}],"member":"320","published-online":{"date-parts":[[2005,1]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of Functional Programming and Computer Architecture, J. Hughes, Ed. Lecture Notes in Computer Science","volume":"523","author":"Aiken A.","unstructured":"Aiken , A. and Murphy , B. R . 1991. Implementing regular tree expressions . In Proceedings of Functional Programming and Computer Architecture, J. Hughes, Ed. Lecture Notes in Computer Science , vol. 523 . Springer-Verlag, New York.]] Aiken, A. and Murphy, B. R. 1991. Implementing regular tree expressions. In Proceedings of Functional Programming and Computer Architecture, J. Hughes, Ed. Lecture Notes in Computer Science, vol. 523. Springer-Verlag, New York.]]"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/155183.155231"},{"key":"e_1_2_1_3_1","first-page":"309","article-title":"Coinductive axiomatization of recursive type equality and subtyping","volume":"33","author":"Brandt M.","year":"1998","unstructured":"Brandt , M. and Henglein , F. 1998 . Coinductive axiomatization of recursive type equality and subtyping . Fund. Inf. 33 , 309 -- 338 .]] Brandt, M. and Henglein, F. 1998. Coinductive axiomatization of recursive type equality and subtyping. Fund. Inf. 33, 309--338.]]","journal-title":"Fund. Inf."},{"key":"e_1_2_1_4_1","unstructured":"Bray T. Paoli J. Sperberg-McQueen C. M. and Maler E. 2000. Extensible markup language (XML#8482;). http:\/\/www.w3.org\/XML\/.]]  Bray T. Paoli J. Sperberg-McQueen C. M. and Maler E. 2000. Extensible markup language (XML#8482;). http:\/\/www.w3.org\/XML\/.]]"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the International Conference on Database Theory. Lecture Notes in Computer Science","volume":"1","author":"Buneman P.","unstructured":"Buneman , P. , Davidson , S. , Fernandez , M. , and Suciu , D . 1997. Adding structure to unstructured data . In Proceedings of the International Conference on Database Theory. Lecture Notes in Computer Science , vol. 1 . Springer-Verlag, New York, 336--351.]] Buneman, P., Davidson, S., Fernandez, M., and Suciu, D. 1997. Adding structure to unstructured data. In Proceedings of the International Conference on Database Theory. Lecture Notes in Computer Science, vol. 1. Springer-Verlag, New York, 336--351.]]"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the International Database Programming Languages Workshop. Lecture Notes in Computer Science","volume":"1686","author":"Buneman P.","unstructured":"Buneman , P. and Pierce , B . 1998. Union types for semistructured data . In Proceedings of the International Database Programming Languages Workshop. Lecture Notes in Computer Science , vol. 1686 . Springer-Verlag, New York.]] Buneman, P. and Pierce, B. 1998. Union types for semistructured data. In Proceedings of the International Database Programming Languages Workshop. Lecture Notes in Computer Science, vol. 1686. Springer-Verlag, New York.]]"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00183-J"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 25th International Conference on Very Large Data Bases","author":"Chawathe S. S.","year":"1999","unstructured":"Chawathe , S. S. 1999 . Comparing hierarchical data in external memory . In Proceedings of the 25th International Conference on Very Large Data Bases ( Edinburgh, Scotland, U.K.). 90--101.]] Chawathe, S. S. 1999. Comparing hierarchical data in external memory. In Proceedings of the 25th International Conference on Very Large Data Bases (Edinburgh, Scotland, U.K.). 90--101.]]"},{"key":"e_1_2_1_10_1","unstructured":"Clark J. 1999. XSL Transformations (XSLT). http:\/\/www.w3.org\/TR\/xslt.]]  Clark J. 1999. XSL Transformations (XSLT). http:\/\/www.w3.org\/TR\/xslt.]]"},{"key":"e_1_2_1_11_1","volume-title":"TREX: Tree Regular Expressions for XML","author":"Clark J.","year":"2001","unstructured":"Clark , J. 2001 . TREX: Tree Regular Expressions for XML . http:\/\/www.thaiopensource.com\/trex\/.]] Clark, J. 2001. TREX: Tree Regular Expressions for XML. http:\/\/www.thaiopensource.com\/trex\/.]]"},{"key":"e_1_2_1_12_1","unstructured":"Clark J. and Murata M. 2001. RELAX NG. http:\/\/www.relaxng.org.]]  Clark J. and Murata M. 2001. RELAX NG. http:\/\/www.relaxng.org.]]"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the International Workshop on the Web and Databases (WebDB). 118--135","author":"Cluet S.","unstructured":"Cluet , S. and Sim\u00e9on , J . 1998. Using YAT to build a web server . In Proceedings of the International Workshop on the Web and Databases (WebDB). 118--135 .]] Cluet, S. and Sim\u00e9on, J. 1998. Using YAT to build a web server. In Proceedings of the International Workshop on the Web and Databases (WebDB). 118--135.]]"},{"key":"e_1_2_1_14_1","unstructured":"Comon H. Dauchet M. Gilleron R. Jacquemard F. Lugiez D. Tison S. and Tommasi M. 1999. Tree automata techniques and applications (Draft book; available electronically on http:\/\/www.grappa.univ-lille3.fr\/tata.)]]  Comon H. Dauchet M. Gilleron R. Jacquemard F. Lugiez D. Tison S. and Tommasi M. 1999. Tree automata techniques and applications (Draft book; available electronically on http:\/\/www.grappa.univ-lille3.fr\/tata.)]]"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the Theoretical Aspects of Computer Software, M. Hagiya and J. C. Mitchell, Eds. Lecture Notes in Computer Science","volume":"789","author":"Damm F. M.","year":"1994","unstructured":"Damm , F. M. 1994 . Subtyping with union types, intersection types and recursive types . In Proceedings of the Theoretical Aspects of Computer Software, M. Hagiya and J. C. Mitchell, Eds. Lecture Notes in Computer Science , vol. 789 . Springer-Verlag, New York, 687--706.]] Damm, F. M. 1994. Subtyping with union types, intersection types and recursive types. In Proceedings of the Theoretical Aspects of Computer Software, M. Hagiya and J. C. Mitchell, Eds. Lecture Notes in Computer Science, vol. 789. Springer-Verlag, New York, 687--706.]]"},{"key":"e_1_2_1_16_1","unstructured":"Davidson A. Fuchs M. Hedin M. Jain M. Koistinen J. Lloyd C. Maloney M. and Schwarzhof K. 1999. Schema for object-oriented XML. http:\/\/www.w3.org\/TR\/NOTE-SOX\/.]]  Davidson A. Fuchs M. Hedin M. Jain M. Koistinen J. Lloyd C. Maloney M. and Schwarzhof K. 1999. Schema for object-oriented XML. http:\/\/www.w3.org\/TR\/NOTE-SOX\/.]]"},{"key":"e_1_2_1_17_1","unstructured":"Davies R. 2000. Tree automata inclusion. Personal communication.]]  Davies R. 2000. Tree automata inclusion. Personal communication.]]"},{"key":"e_1_2_1_18_1","unstructured":"Deutsch A. Fernandez M. Florescu D. Levy A. and Suciu D. 1998. XML-QL: A Query Language for XML. http:\/\/www.w3.org\/TR\/NOTE-xml-ql.]]  Deutsch A. Fernandez M. Florescu D. Levy A. and Suciu D. 1998. XML-QL: A Query Language for XML. http:\/\/www.w3.org\/TR\/NOTE-xml-ql.]]"},{"key":"e_1_2_1_19_1","unstructured":"DOM. 2001. Document object model (DOM). http:\/\/www.w3.org\/DOM\/.]]  DOM. 2001. Document object model (DOM). http:\/\/www.w3.org\/DOM\/.]]"},{"key":"e_1_2_1_20_1","unstructured":"Fallside D. C. 2001. XML Schema Part 0: Primer W3C Recommendation. http:\/\/www.w3.org\/TR\/xmlschema-0\/.]]  Fallside D. C. 2001. XML Schema Part 0: Primer W3C Recommendation. http:\/\/www.w3.org\/TR\/xmlschema-0\/.]]"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of 8th International Conference on Database Theory (ICDT","volume":"1973","author":"Fern\u00e1ndez M. F.","year":"2001","unstructured":"Fern\u00e1ndez , M. F. , Sim\u00e9on , J. , and Wadler , P . 2001. A semi-monad for semi-structured data . In Proceedings of 8th International Conference on Database Theory (ICDT 2001 ), J. V. den Bussche and V. Vianu, Eds. Lecture Notes in Computer Science , vol. 1973 . Springer-Verlag, New York, 263--300.]] Fern\u00e1ndez, M. F., Sim\u00e9on, J., and Wadler, P. 2001. A semi-monad for semi-structured data. In Proceedings of 8th International Conference on Database Theory (ICDT 2001), J. V. den Bussche and V. Vianu, Eds. Lecture Notes in Computer Science, vol. 1973. Springer-Verlag, New York, 263--300.]]"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the SIGPLAN '91 Symposium on Language Design and Implementation","author":"Freeman T.","unstructured":"Freeman , T. and Pfenning , F . 1991. Refinement types for ML . In Proceedings of the SIGPLAN '91 Symposium on Language Design and Implementation ( Toronto, Ont. Canada). ACM, New York.]] 10.1145\/113445.113468 Freeman, T. and Pfenning, F. 1991. Refinement types for ML. In Proceedings of the SIGPLAN '91 Symposium on Language Design and Implementation (Toronto, Ont. Canada). ACM, New York.]] 10.1145\/113445.113468"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 17th Annual IEEE Symposium on Logic In Computer Science. 137--146","author":"Frisch A.","unstructured":"Frisch , A. , Castagna , G. , and Benzaken , V . 2002. Semantic subtyping . In Proceedings of the 17th Annual IEEE Symposium on Logic In Computer Science. 137--146 .]] Frisch, A., Castagna, G., and Benzaken, V. 2002. Semantic subtyping. In Proceedings of the 17th Annual IEEE Symposium on Logic In Computer Science. 137--146.]]"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the International Conference on Functional Programming (ICFP). 221--232","author":"Gapeyev V.","unstructured":"Gapeyev , V. , Levin , M. , and Pierce , B . 2000. Recursive subtyping revealed . In Proceedings of the International Conference on Functional Programming (ICFP). 221--232 .]] 10.1145\/351240.351261 Gapeyev, V., Levin, M., and Pierce, B. 2000. Recursive subtyping revealed. In Proceedings of the International Conference on Functional Programming (ICFP). 221--232.]] 10.1145\/351240.351261"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/inco.1998.2747","article-title":"Set constraints and automata","volume":"149","author":"Gilleron R.","year":"1999","unstructured":"Gilleron , R. , Tison , S. , and Tommasi , M. 1999 . Set constraints and automata . Inf. Comput. 149 , 1, 1 -- 41 .]] Gilleron, R., Tison, S., and Tommasi, M. 1999. Set constraints and automata. Inf. Comput. 149, 1, 1--41.]]","journal-title":"Inf. Comput."},{"key":"e_1_2_1_26_1","volume-title":"Dataguides: Enabling query formulation and optimization in semistructured databases. In VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases","author":"Goldman R.","year":"1997","unstructured":"Goldman , R. and Widom , J . 1997 . Dataguides: Enabling query formulation and optimization in semistructured databases. In VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases , M. Jarke, M. J. Carey, K. R. Dittrich, F. H. Lochovsky, P. Loucopoulos, and M. A. Jeusfeld, Eds. Morgan Kaufmann , 436--445.]] Goldman, R. and Widom, J. 1997. Dataguides: Enabling query formulation and optimization in semistructured databases. In VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases, M. Jarke, M. J. Carey, K. R. Dittrich, F. H. Lochovsky, P. Loucopoulos, and M. A. Jeusfeld, Eds. Morgan Kaufmann, 436--445.]]"},{"key":"e_1_2_1_27_1","unstructured":"Hopcroft J. E. and Ullman J. D. 1979. Introduction to Automata Theory Languages and Computation. Addison-Wesley Reading Mass.]]   Hopcroft J. E. and Ullman J. D. 1979. Introduction to Automata Theory Languages and Computation. Addison-Wesley Reading Mass.]]"},{"key":"e_1_2_1_28_1","first-page":"309","article-title":"Labelled trees and their recognition. In","volume":"48","author":"Hornung T.","year":"1996","unstructured":"Hornung , T. 1996 . Labelled trees and their recognition. In Publ. Math. Debrecen. Number 3--4 in 48. 309 -- 316 .]] Hornung, T. 1996. Labelled trees and their recognition. In Publ. Math. Debrecen. Number 3--4 in 48. 309--316.]]","journal-title":"Publ. Math. Debrecen. Number 3--4 in"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/360204.360209"},{"key":"e_1_2_1_31_1","unstructured":"Hosoya H.\n     and \n      Pierce B. C\n  . \n  2003\n  . XDuce: \n  A\n   typed XML processing language. ACM Trans. Internet Tech. 3 2 117--148. (Short version appeared in Proceedings of 3rd International Workshop on the Web and Databases (WebDB2000) volume \n  1997\n   of \n  Lecture Notes in Computer Science\n  . \n  Springer-Verlag New York 2000 pp. \n  226\n  --\n  244\n  .)]]   Hosoya H. and Pierce B. C. 2003. XDuce: A typed XML processing language. ACM Trans. Internet Tech. 3 2 117--148. (Short version appeared in Proceedings of 3rd International Workshop on the Web and Databases (WebDB2000) volume 1997 of Lecture Notes in Computer Science. Springer-Verlag New York 2000 pp. 226--244.)]]"},{"key":"e_1_2_1_32_1","volume-title":"DSD: A schema language for XML","author":"Klarlund N.","year":"2000","unstructured":"Klarlund , N. , M\u00f8ller , A. , and Schwartzbach , M. I . 2000 . DSD: A schema language for XML . http:\/\/www.brics.dk\/DSD\/.]] Klarlund, N., M\u00f8ller, A., and Schwartzbach, M. I. 2000. DSD: A schema language for XML. http:\/\/www.brics.dk\/DSD\/.]]"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the International Conference on Database Theory (ICDT'2001)","author":"Kuper G. M.","unstructured":"Kuper , G. M. and Sim\u00e9on , J . 2001. Subsumption for XML types . In Proceedings of the International Conference on Database Theory (ICDT'2001) . London.]] Kuper, G. M. and Sim\u00e9on, J. 2001. Subsumption for XML types. In Proceedings of the International Conference on Database Theory (ICDT'2001). London.]]"},{"key":"e_1_2_1_34_1","unstructured":"Meijer E. and Shields M. 1999. XM\u03bb: A functional programming language for constructing and manipulating XML documents. Manuscript.]]  Meijer E. and Shields M. 1999. XM\u03bb: A functional programming language for constructing and manipulating XML documents. Manuscript.]]"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. ACM","author":"Milo T.","unstructured":"Milo , T. , Suciu , D. , and Vianu , V . 2000. Typechecking for XML transformers . In Proceedings of the 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. ACM , New York, 11--22.]] 10.1145\/335168.335171 Milo, T., Suciu, D., and Vianu, V. 2000. Typechecking for XML transformers. In Proceedings of the 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. ACM, New York, 11--22.]] 10.1145\/335168.335171"},{"key":"e_1_2_1_36_1","unstructured":"Murata M. 2000. Hedge automata: A formal model for XML schemata. http:\/\/www.xml.gr.jp\/relax\/hedge_nice.html.]]  Murata M. 2000. Hedge automata: A formal model for XML schemata. http:\/\/www.xml.gr.jp\/relax\/hedge_nice.html.]]"},{"key":"e_1_2_1_37_1","unstructured":"Murata M. 2001. RELAX (REgular LAnguage description for XML). http:\/\/www.xml.gr.jp\/relax\/.]]  Murata M. 2001. RELAX (REgular LAnguage description for XML). http:\/\/www.xml.gr.jp\/relax\/.]]"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (Dallas, Tex.). ACM","author":"Papakonstantinou Y.","unstructured":"Papakonstantinou , Y. and Vianu , V . 2000. DTD Inference for views of XML data . In Proceedings of the 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (Dallas, Tex.). ACM , New York, 35--46.]] 10.1145\/335168.335173 Papakonstantinou, Y. and Vianu, V. 2000. DTD Inference for views of XML data. In Proceedings of the 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (Dallas, Tex.). ACM, New York, 35--46.]] 10.1145\/335168.335173"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219027"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 25th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages","author":"Shields M.","unstructured":"Shields , M. and Meijer , E . 2001. Type-indexed rows . In Proceedings of the 25th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages ( London, United Kingdom). ACM New York.]] 10.1145\/360204.360230 Shields, M. and Meijer, E. 2001. Type-indexed rows. In Proceedings of the 25th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (London, United Kingdom). ACM New York.]] 10.1145\/360204.360230"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 4th ACM SIGPLAN International Conference on Functional Programming (ICFP'99)","volume":"9","author":"Wallace M.","unstructured":"Wallace , M. and Runciman , C . 1999. Haskell and XML: Generic combinators or type-based translation? In Proceedings of the 4th ACM SIGPLAN International Conference on Functional Programming (ICFP'99) . ACM SIGPLAN Notices , vol. 34- 9 . ACM, New York, 148--159.]] 10.1145\/317636.317794 Wallace, M. and Runciman, C. 1999. Haskell and XML: Generic combinators or type-based translation? In Proceedings of the 4th ACM SIGPLAN International Conference on Functional Programming (ICFP'99). ACM SIGPLAN Notices, vol. 34-9. ACM, New York, 148--159.]] 10.1145\/317636.317794"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1053468.1053470","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1053468.1053470","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:07:53Z","timestamp":1750262873000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1053468.1053470"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1145\/1053468.1053470"],"URL":"https:\/\/doi.org\/10.1145\/1053468.1053470","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"value":"0164-0925","type":"print"},{"value":"1558-4593","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,1]]},"assertion":[{"value":"2005-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}