{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T17:32:12Z","timestamp":1772299932461,"version":"3.50.1"},"reference-count":30,"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]]},"DOI":"10.1137\/080743457","type":"journal-article","created":{"date-parts":[[2009,11,26]],"date-time":"2009-11-26T03:22:23Z","timestamp":1259205743000},"page":"1486-1530","source":"Crossref","is-referenced-by-count":34,"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":[]},{"given":"Frank","family":"Neven","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[]}],"member":"351","reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1023\/B:FORM.0000033962.51898.1a"},{"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":"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":"R10","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2688"},{"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":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/304181.304220"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/070697367"},{"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":"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":"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":"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":"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":"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":"R47","doi-asserted-by":"publisher","DOI":"10.1137\/0219027"},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00130-8"},{"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":"R55","doi-asserted-by":"publisher","DOI":"10.1145\/776985.776999"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080743457","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,1,29]],"date-time":"2017-01-29T17:12:38Z","timestamp":1485709958000},"score":1,"resource":{"primary":{"URL":"http:\/\/epubs.siam.org\/doi\/10.1137\/080743457"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":30,"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":[[2010,1]]}}}