{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T21:13:30Z","timestamp":1791148410334,"version":"4.1.0"},"reference-count":56,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>We study the complexity of the inclusion, equivalence, and intersection problem of extended chain regular expressions (eCHAREs). These are regular expressions with a very simple structure: they basically consist of the concatenation of factors, where each factor is a disjunction of strings, possibly extended with \u201c$*$\u201d, \u201c$+$\u201d, or \u201c$?$\u201d. Though of a very simple form, the usage of such expressions is widespread as eCHAREs, for instance, constitute a super class of the regular expressions most frequently used in practice in schema languages for XML. In particular, we show that all our lower and upper bounds for the inclusion and equivalence problem carry over to the corresponding decision problems for extended context-free grammars, and to single-type and restrained competition tree grammars. These grammars form abstractions of document type definitions (DTDs), XML schema definitions (XSDs) and the class of one-pass preorder typeable XML Schemas, respectively. For the intersection problem, we show that obtained complexities only carry over to DTDs. In this respect, we also study two other classes of regular expressions related to XML: deterministic expressions and expressions where the number of occurrences of alphabet symbols is bounded by a constant.<\/jats:p>","DOI":"10.1137\/080743457","type":"journal-article","created":{"date-parts":[[2009,11,25]],"date-time":"2009-11-25T22:22:23Z","timestamp":1259187743000},"page":"1486-1530","source":"Crossref","is-referenced-by-count":35,"title":["Complexity of Decision Problems for XML Schemas and Chain Regular Expressions"],"prefix":"10.1137","volume":"39","author":[{"given":"Wim","family":"Martens","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Frank","family":"Neven","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2009,11,25]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1023\/B:FORM.0000033962.51898.1a"},{"key":"R2","unstructured":"S. Abiteboul, P. Buneman, and D. Suciu,\n                      Data on the Web: From Relations to Semistructured Data and XML\n                      , Morgan Kaufmann, San Francisco, 1999."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00294-2"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45465-9_15"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"M. Benedikt, W. Fan, and F. Geerts,\n                      Xpath satisfiability in the presence of DTDs\n                      , Journal of the ACM, 55(2), 2008.","DOI":"10.1145\/1346330.1346333"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"G. J. Bex, W. Martens, F. Neven, and T. Schwentick,\n                      Expressiveness of XSDs: from practice to theory, there and back again\n                      , in Proceedings of the 14th International Conference on World Wide Web (WWW), pages 712\u2013721, USA, 2005. ACM.","DOI":"10.1145\/1060745.1060848"},{"key":"R7","first-page":"115","author":"Bex G. J.","year":"2006","journal-title":"in Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB), ACM"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"G.J. Bex, F. Neven, and J. Van den Bussche,\n                      DTDs versus XML Schema: A practical study\n                      , in Proceedings of the 7th International Workshop on the Web and Databases (WebDB), (2004), pp. 79\u201384.","DOI":"10.1145\/1017074.1017095"},{"key":"R9","unstructured":"T. Bray, J. Paoli, C.M. Sperberg-McQueen, E. Maler, and F. Yergeau,\n                      Extensible Markup Language (XML)\n                      , Technical report, World Wide Web Consortium, February 2004. http:\/\/www.w3.org\/TR\/REC-xml\/."},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2688"},{"key":"R11","unstructured":"A. Br\u00fcggemann-Klein, M. Murata, and D. Wood,\n                      Regular tree and regular hedge languages over unranked alphabets\n                      , Technical Report HKUST-TCSC-2001-0, The Hong Kong University of Science and Technology, 2001."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2695"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1162\/109966200750410613"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/959060.959076"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90036-X"},{"key":"R16","unstructured":"B. Choi,\n                      What are real DTDs like?\n                      , In Proceedings of the 5th International Workshop on the Web and Databases (WebDB), (2002), pp. 43\u201348."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/304181.304220"},{"key":"R18","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP-Completeness\n                      , W.H. Freeman, New York, NA, 1979."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"W. Gelade, M. Gyssens, and W. Martens,\n                      Regular expressions with counting: Weak versus strong determinism\n                      , In Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science (MFCS), 2009.","DOI":"10.1007\/978-3-642-03816-7_32"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/070697367"},{"key":"R21","unstructured":"G. Ghelli, D. Colazzo, and C. Sartiani,\n                      Efficient inclusion for a class of XML types with interleaving and counting\n                      , 11th International Symposium on Database Programming Languages (DBPL), 2007."},{"key":"R22","first-page":"3","volume":"16","author":"Glushkov V.","year":"1961","journal-title":"Uspekhi Matematicheskikh Nauk","ISSN":"https:\/\/id.crossref.org\/issn\/0042-1316","issn-type":"print"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"L. Hemaspaandra and M. Ogihara,\n                      The Complexity Theory Companion\n                      , Springer-Verlag, Berlin, 2002.","DOI":"10.1007\/978-3-662-04880-1"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"H. Hosoya and B. C. Pierce,\n                      XDuce: A statically typed XML processing language\n                      , ACM Trans. Internet Tech. (2003), pp. 117\u2013148.","DOI":"10.1145\/767193.767195"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80038-4"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.12.003"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"C. Koch, S. Scherzinger, N. Schweikardt, and B. Stegmaier,\n                      Schema-based scheduling of event processors and buffer minimization for queries on structured data streams\n                      , In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB), pp. 228\u2013239, San Francisco, 2004.","DOI":"10.1016\/B978-012088469-8\/50023-1"},{"key":"R28","first-page":"254","author":"Kozen D.","year":"1977","journal-title":"In Proceedings of the 18th Annual Symposium on Foundations of Computer Science (FOCS)"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"L. Libkin,\n                      Logics for unranked trees: An overview\n                      , Logical Methods in Computer Science, 2(3), 2006.","DOI":"10.2168\/LMCS-2(3:2)2006"},{"key":"R30","unstructured":"M. Mani,\n                      Keeping chess alive - Do we need 1-unambiguous content models?\n                      , In Extreme Markup Languages, Montreal, Canada, 2001."},{"key":"R31","unstructured":"I. Manolescu, D. Florescu, and D. Kossmann,\n                      Answering XML Queries on Heterogeneous Data Sources\n                      , In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB), pp. 241\u2013250, San Francisco, 2001."},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.035"},{"key":"R33","first-page":"889","author":"Martens W.","year":"2004","journal-title":"In Proceedings of the 29th Symposium on Mathematical Foundations of Computer Science (MFCS), Berlin"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166076"},{"key":"R35","first-page":"477","author":"Marx M.","year":"2004","journal-title":"In Proceedings of the 9th International Conference on Extending Database Technology (EDBT), Berlin"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1145\/962446.962448"},{"key":"R37","first-page":"277","author":"Milo T.","year":"1999","journal-title":"In Proceedings of the 7th International Conference on Database Theory (ICDT), Berlin"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00030-2"},{"key":"R39","unstructured":"D. Mount,\n                      Bioinformatics: Sequence and Genome Analysis\n                      , Cold Spring Harbor Laboratory Press, 2001."},{"key":"R40","unstructured":"M. Murata,\n                      Relax NG\n                      , http:\/\/www.relaxng.org\/."},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1145\/1111627.1111631"},{"key":"R42","first-page":"2","author":"Neven F.","year":"2002","journal-title":"In Proceedings of the 16th Conference for Computer Science Logic (CSL 2002), Berlin"},{"key":"R43","doi-asserted-by":"crossref","unstructured":"F. Neven and T. Schwentick,\n                      On the complexity of XPath containment in the presence of disjunction, DTDs, and variables\n                      , Logical Methods in Computer Science, 2, 2006.","DOI":"10.2168\/LMCS-2(3:1)2006"},{"key":"R44","first-page":"35","author":"Papakonstantinou Y.","year":"2000","journal-title":"In Proceedings of the 19th Symposium on Principles of Database Systems (PODS), ACM Press"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.003"},{"key":"R46","unstructured":"R. Sedgewick,\n                      Algorithms\n                      . Addison-Wesley, Reading, MA, 1983."},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1137\/0219027"},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00130-8"},{"key":"R49","unstructured":"C. M. Sperberg-McQueen,\n                      XML Schema\n                      1.0:\n                      A language for document grammars\n                      , In XML 2003 Conference Proceedings, 2003."},{"key":"R50","unstructured":"C. M. Sperberg-McQueen and H. Thompson,\n                      XML Schema\n                      , http:\/\/www.w3.org\/XML\/Schema, 2005."},{"key":"R51","first-page":"1","author":"Stockmeyer L. J.","year":"1973","journal-title":"In Conference Record of the 5th Annual ACM Symposium on Theory of Computing (STOC)"},{"key":"R52","doi-asserted-by":"crossref","unstructured":"B. ten Cate\n                      The expressivity of XPath with transitive closure\n                      , In Proceedings of the 25th Symposium on Principles of Database Systems (PODS), (2006), pp. 328\u2013337.","DOI":"10.1145\/1142351.1142398"},{"key":"R53","unstructured":"E. van der Vlist,\n                      XML Schema\n                      , O'Reilly, Cambridge, MA, 2002."},{"key":"R54","unstructured":"E. van der Vlist,\n                      Relax NG\n                      , O'Reilly, Cambridge, MA, 2003."},{"key":"R55","doi-asserted-by":"publisher","DOI":"10.1145\/776985.776999"},{"key":"R56","unstructured":"G. Wang, M. Liu, J. Xu Yu, B. Sun, G. Yu, J. Lv, and H. Lu,\n                      Effective schema-based XML query optimization techniques\n                      , In\n                      International Database Engineering and Applications Symposium (IDEAS)\n                      , (2003), pp. 230\u2013235."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080743457","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:31:01Z","timestamp":1787337061000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080743457"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,11,25]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/080743457"],"URL":"https:\/\/doi.org\/10.1137\/080743457","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,11,25]]}}}