{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,9]],"date-time":"2025-05-09T05:50:53Z","timestamp":1746769853412},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540228233"},{"type":"electronic","value":"9783540286295"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-28629-5_70","type":"book-chapter","created":{"date-parts":[[2010,12,17]],"date-time":"2010-12-17T17:59:50Z","timestamp":1292608790000},"page":"889-900","source":"Crossref","is-referenced-by-count":32,"title":["Complexity of Decision Problems for Simple Regular Expressions"],"prefix":"10.1007","author":[{"given":"Wim","family":"Martens","sequence":"first","affiliation":[]},{"given":"Frank","family":"Neven","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"70_CR1","doi-asserted-by":"crossref","unstructured":"Abdulla, P.A., Bouajjani, A., Jonsson, B.: On-the-fly analysis of systems with unbounded, lossy FIFO channels. In: Proc. of CAV 1998, pp. 305\u2013318 (1998)","DOI":"10.1007\/BFb0028754"},{"key":"70_CR2","doi-asserted-by":"crossref","unstructured":"Bex, G.J., Neven, F., Van den Bussche, J.: DTDs versus XML Schema: A practical study. To be presented at WebDB 2004","DOI":"10.1145\/1017074.1017095"},{"key":"70_CR3","unstructured":"Br\u00fcggemann-Klein, A., Murata, M., Wood, D.: Regular tree and regular hedge languages over unranked alphabets. Technical Report HKUST-TCSC-2001-0, The Hongkong University of Science and Technology (2001)"},{"issue":"2","key":"70_CR4","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1006\/inco.1997.2695","volume":"142","author":"A. Br\u00fcggemann-Klein","year":"1998","unstructured":"Br\u00fcggemann-Klein, A., Wood, D.: One-unambiguous regular languages. Information and Computation\u00a0142(2), 182\u2013206 (1998)","journal-title":"Information and Computation"},{"issue":"1","key":"70_CR5","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1162\/109966200750410613","volume":"2","author":"A. Br\u00fcggemann-Klein","year":"2000","unstructured":"Br\u00fcggemann-Klein, A., Wood, D.: Caterpillars: A context specification technique. Markup Languages\u00a02(1), 81\u2013106 (2000)","journal-title":"Markup Languages"},{"issue":"4","key":"70_CR6","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1145\/959060.959076","volume":"32","author":"D. Calvanese","year":"2003","unstructured":"Calvanese, D., De Giacomo, G., Lenzerini, M., Vardi, M.Y.: Reasoning on regular path queries. SIGMOD Record\u00a032(4), 83\u201392 (2003)","journal-title":"SIGMOD Record"},{"key":"70_CR7","doi-asserted-by":"crossref","unstructured":"Choi, B.: What are real DTDs like? In: WebDB 2002, pp. 43\u201348 (2002)","DOI":"10.1023\/A:1022665831622"},{"key":"70_CR8","unstructured":"World Wide Web Consortium. Extensible Markup Language (XML), http:\/\/www.w3.org\/XML"},{"key":"70_CR9","unstructured":"World Wide Web Consortium. XML Schema, http:\/\/www.w3.org\/XML\/Schema"},{"key":"70_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04880-1","volume-title":"The Complexity Theory Companion","author":"L. Hemaspaandra","year":"2002","unstructured":"Hemaspaandra, L., Ogihara, M.: The Complexity Theory Companion. Springer, Heidelberg (2002)"},{"issue":"2","key":"70_CR11","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1145\/767193.767195","volume":"3","author":"H. Hosoya","year":"2003","unstructured":"Hosoya, H., Pierce, B.C.: XDuce: A statically typed XML processing language. ACM Transactions on Internet Technology (TOIT)\u00a03(2), 117\u2013148 (2003)","journal-title":"ACM Transactions on Internet Technology (TOIT)"},{"issue":"2","key":"70_CR12","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1016\/S0022-0000(76)80038-4","volume":"12","author":"H.B. Hunt III","year":"1976","unstructured":"Hunt III, H.B., Rosenkrantz, D.J., Szymanski, T.G.: On the equivalence, containment, and covering problems for the regular and context-free languages. Journal of Computer and System Sciences\u00a012(2), 222\u2013268 (1976)","journal-title":"Journal of Computer and System Sciences"},{"key":"70_CR13","first-page":"254","volume-title":"Proc. FOCS 1977","author":"D. Kozen","year":"1977","unstructured":"Kozen, D.: Lower bounds for natural proof systems. In: Proc. FOCS 1977, pp. 254\u2013266. IEEE, Los Alamitos (1977)"},{"key":"70_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/3-540-36285-1_5","volume-title":"Database Theory - ICDT 2003","author":"W. Martens","year":"2002","unstructured":"Martens, W., Neven, F.: Typechecking top-down uniform unranked tree transducers. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds.) ICDT 2003. LNCS, vol.\u00a02572, pp. 64\u201378. Springer, Heidelberg (2002)"},{"key":"70_CR15","unstructured":"Martens, W., Neven, F., Schwentick, T.: Complexity of decision problems for simple regular expressions: Full version, http:\/\/alpha.luc.ac.be\/lucp1436\/pubs.html"},{"key":"70_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/978-3-540-24741-8_28","volume-title":"Advances in Database Technology - EDBT 2004","author":"M. Marx","year":"2004","unstructured":"Marx, M.: XPath with conditional axis relations. In: Bertino, E., Christodoulakis, S., Plexousakis, D., Christophides, V., Koubarakis, M., B\u00f6hm, K., Ferrari, E. (eds.) EDBT 2004. LNCS, vol.\u00a02992, pp. 477\u2013494. Springer, Heidelberg (2004)"},{"key":"70_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/3-540-49257-7_18","volume-title":"Database Theory - ICDT\u201999","author":"T. Milo","year":"1998","unstructured":"Milo, T., Suciu, D.: Index structures for path expressions. In: Beeri, C., Bruneman, P. (eds.) ICDT 1999. LNCS, vol.\u00a01540, pp. 277\u2013295. Springer, Heidelberg (1998)"},{"issue":"1","key":"70_CR18","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/S0022-0000(02)00030-2","volume":"66","author":"T. Milo","year":"2003","unstructured":"Milo, T., Suciu, D., Vianu, V.: Typechecking for XML transformers. Journal of Computer and System Sciences\u00a066(1), 66\u201397 (2003)","journal-title":"Journal of Computer and System Sciences"},{"key":"70_CR19","unstructured":"Murata, M., Lee, D., Mani, M.: Taxonomy of XML schema languages using formal language theory. In: Extreme Markup Languages, Montreal, Canada (2001)"},{"key":"70_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/3-540-45793-3_2","volume-title":"Computer Science Logic","author":"F. Neven","year":"2002","unstructured":"Neven, F.: Automata, logic, and XML. In: Bradfield, J.C. (ed.) CSL 2002 and EACSL 2002. LNCS, vol.\u00a02471, pp. 2\u201326. Springer, Heidelberg (2002)"},{"key":"70_CR21","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1145\/335168.335173","volume-title":"Proc. PODS 2000","author":"Y. Papakonstantinou","year":"2000","unstructured":"Papakonstantinou, Y., Vianu, V.: DTD inference for views of XML data. In: Proc. PODS 2000, pp. 35\u201346. ACM Press, New York (2000)"},{"issue":"3","key":"70_CR22","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1137\/0219027","volume":"19","author":"H. Seidl","year":"1990","unstructured":"Seidl, H.: Deciding equivalence of finite tree automata. SIAM Journal on Computing\u00a019(3), 424\u2013437 (1990)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"70_CR23","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0020-0190(94)00130-8","volume":"52","author":"H. Seidl","year":"1994","unstructured":"Seidl, H.: Haskell overloading is DEXPTIME-complete. Information Processing Letters\u00a052(2), 57\u201360 (1994)","journal-title":"Information Processing Letters"},{"key":"70_CR24","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time: Preliminary report. In: Proc. STOC 1973, pp. 1\u20139 (1973)","DOI":"10.1145\/800125.804029"},{"key":"70_CR25","volume-title":"Relax NG","author":"E. Vlist van der","year":"2003","unstructured":"van der Vlist, E.: Relax NG. O\u2019Reilly, Sebastopol (2003)"},{"key":"70_CR26","doi-asserted-by":"crossref","unstructured":"Vianu, V.: A web odyssey: From Codd to XML. In: Proc. PODS 2001, pp. 1\u201315 (2001)","DOI":"10.1145\/375551.375554"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-28629-5_70.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:25:50Z","timestamp":1605759950000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-28629-5_70"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228233","9783540286295"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-28629-5_70","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}