{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T17:32:10Z","timestamp":1772299930210,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540692690","type":"print"},{"value":"9783540692706","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11965893_19","type":"book-chapter","created":{"date-parts":[[2006,12,7]],"date-time":"2006-12-07T02:52:22Z","timestamp":1165459942000},"page":"269-283","source":"Crossref","is-referenced-by-count":17,"title":["Optimizing Schema Languages for XML: Numerical Constraints and Interleaving"],"prefix":"10.1007","author":[{"given":"Wouter","family":"Gelade","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wim","family":"Martens","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Neven","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"19_CR1","volume-title":"Data on the Web : From Relations to Semistructured Data and XML","author":"S. Abiteboul","year":"1999","unstructured":"Abiteboul, S., Buneman, P., Suciu, D.: Data on the Web: From Relations to Semistructured Data and XML. Morgan Kaufmann, San Francisco (1999)"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"Benedikt, M., Fan, W., Geerts, F.: XPath satisfiability in the presence of DTDs. In: PODS 2005, pp. 25\u201336 (2005)","DOI":"10.1145\/1065167.1065172"},{"key":"19_CR3","unstructured":"Bex, G.J., Neven, F., Schwentick, T., Tuyls, K.: Inference of concise DTDs from XML data. In: VLDB 2006, pp. 115\u2013126 (2006)"},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"Bex, G.J., Neven, F., Van den Bussche, J.: DTDs versus XML schema: A practical study. In: WebDB 2004, pp. 79\u201384 (2004)","DOI":"10.1145\/1017074.1017095"},{"key":"19_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/3-540-57273-2_45","volume-title":"Algorithms - ESA 1993","author":"A. Br\u00fcggemann-Klein","year":"1993","unstructured":"Br\u00fcggemann-Klein, A.: Unambiguity of extended regular expressions in SGML document grammars. In: Lengauer, T. (ed.) ESA 1993. LNCS, vol.\u00a0726, pp. 73\u201384. Springer, Heidelberg (1993)"},{"key":"#cr-split#-19_CR6.1","unstructured":"Br??ggemann-Klein, A., Murata, M., Wood, D.: Regular tree and regular hedge languages over unranked alphabets: Version 1 (April 3, 2001);"},{"key":"#cr-split#-19_CR6.2","unstructured":"Technical Report HKUST-TCSC-2001-0, The Hongkong University of Science and Technology (2001)"},{"issue":"2","key":"19_CR7","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"},{"key":"19_CR8","unstructured":"Clark, J., Murata, M.: RELAX NG Specification. OASIS (December 2001)"},{"key":"19_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/11537311_7","volume-title":"Fundamentals of Computation Theory","author":"J. Cristau","year":"2005","unstructured":"Cristau, J., L\u00f6ding, C., Thomas, W.: Deterministic automata on unranked trees. In: Li\u015bkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol.\u00a03623, pp. 68\u201379. Springer, Heidelberg (2005)"},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"Dal-Zilio, S., Lugiez, D.: XML schema, tree logic and sheaves automata. In: RTA, pp. 246\u2013263 (2003)","DOI":"10.1007\/3-540-44881-0_18"},{"key":"19_CR11","doi-asserted-by":"crossref","unstructured":"Deutsch, A., Fernandez, M.F., Suciu, D.: Storing Semistructured Data with STORED. In: SIGMOD 1999, pp. 431\u2013442 (1999)","DOI":"10.1145\/304182.304220"},{"key":"19_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1007\/3-540-10003-2_74","volume-title":"Automata, Languages and Programming","author":"M. F\u00fcrer","year":"1980","unstructured":"F\u00fcrer, M.: The complexity of the inequivalence problem for regular expressions with intersection. In: de Bakker, J.W., van Leeuwen, J. (eds.) ICALP 1980. LNCS, vol.\u00a085, pp. 234\u2013245. Springer, Heidelberg (1980)"},{"key":"19_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04880-1","volume-title":"Complexity Theory Companion","author":"L. Hemaspaandra","year":"2002","unstructured":"Hemaspaandra, L., Ogihara, M.: Complexity Theory Companion. Springer, Heidelberg (2002)"},{"key":"19_CR14","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J.E. Hopcroft","year":"2001","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 2nd edn. Addison-Wesley, Reading (2001)","edition":"2"},{"issue":"2","key":"19_CR15","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 Trans. Inter. Tech.\u00a03(2), 117\u2013148 (2003)","journal-title":"ACM Trans. Inter. Tech."},{"issue":"1-2","key":"19_CR16","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0304-3975(99)00109-7","volume":"250","author":"J. Je\u0327drzejowicz","year":"2001","unstructured":"Je\u0327drzejowicz, J., Szepietowski, A.: Shuffle languages are in P. Theoretical Computer Science\u00a0250(1-2), 31\u201353 (2001)","journal-title":"Theoretical Computer Science"},{"key":"19_CR17","unstructured":"Kilpel\u00e4inen, P.: Inclusion of unambiguous #REs is NP-hard, University of Kuopio, Finland (May 2004) (unpublished note)"},{"key":"19_CR18","unstructured":"Kilpel\u00e4inen, P., Tuhkanen, R.: One-unambiguity of regular expressions with numeric occurrence indicators. Tech. Rep. A\/2006\/2, Univ. Kuopio, Finland (2006)"},{"key":"19_CR19","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1145\/1030397.1030441","volume-title":"DOCENG 2004","author":"P. Kilpel\u00e4inen","year":"2004","unstructured":"Kilpel\u00e4inen, P., Tuhkanen, R.: Towards efficient implementation of XML schema content models. In: DOCENG 2004, pp. 239\u2013241. ACM Press, New York (2004)"},{"key":"19_CR20","doi-asserted-by":"crossref","unstructured":"Koch, C., Scherzinger, S., Schweikardt, N., Stegmaier, B.: Schema-based scheduling of event processors and buffer minimization for queries on structured data streams. In: VLDB 2004, pp. 228\u2013239 (2004)","DOI":"10.1016\/B978-012088469-8.50023-1"},{"key":"19_CR21","first-page":"254","volume-title":"FOCS 1977","author":"D. Kozen","year":"1977","unstructured":"Kozen, D.: Lower bounds for natural proof systems. In: FOCS 1977, pp. 254\u2013266. IEEE, Los Alamitos (1977)"},{"key":"19_CR22","unstructured":"Mani, M.: Keeping chess alive \u2014 Do we need 1-unambiguous content models? In: Extreme Markup Languages, Montreal, Canada (2001)"},{"key":"19_CR23","unstructured":"Manolescu, I., Florescu, D., Kossmann, D.: Answering XML Queries on Heterogeneous Data Sources. In: VLDB 2001, pp. 241\u2013250 (2001)"},{"key":"19_CR24","doi-asserted-by":"crossref","unstructured":"Martens, W., Neven, F.: Frontiers of tractability for typechecking simple XML transformations. Journal of Computer and System Sciences (to appear, 2006)","DOI":"10.1016\/j.jcss.2006.10.005"},{"key":"19_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1007\/978-3-540-28629-5_70","volume-title":"Mathematical Foundations of Computer Science 2004","author":"W. Martens","year":"2004","unstructured":"Martens, W., Neven, F., Schwentick, T.: Complexity of decision problems for simple regular expressions. In: Fiala, J., Koubek, V., Kratochv\u00edl, J. (eds.) MFCS 2004. LNCS, vol.\u00a03153, pp. 889\u2013900. Springer, Heidelberg (2004)"},{"key":"19_CR26","doi-asserted-by":"crossref","unstructured":"Martens, W., Neven, F., Schwentick, T., Bex, G.J.: Expressiveness and complexity of XML schema. ACM Trans. Database Systems\u00a031(3) (to appear, 2006)","DOI":"10.1145\/1166074.1166076"},{"key":"19_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/11601524_15","volume-title":"Database Programming Languages","author":"W. Martens","year":"2005","unstructured":"Martens, W., Niehren, J.: Minimizing tree automata for unranked trees. In: Bierman, G., Koch, C. (eds.) DBPL 2005. LNCS, vol.\u00a03774, pp. 232\u2013246. Springer, Heidelberg (2005)"},{"issue":"2","key":"19_CR28","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1006\/inco.1994.1098","volume":"115","author":"A.J. Mayer","year":"1994","unstructured":"Mayer, A.J., Stockmeyer, L.J.: Word problems \u2014 this time with interleaving. Information and Computation\u00a0115(2), 293\u2013311 (1994)","journal-title":"Information and Computation"},{"issue":"4","key":"19_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1111627.1111631","volume":"5","author":"M. Murata","year":"2005","unstructured":"Murata, M., Lee, D., Mani, M., Kawaguchi, K.: Taxonomy of XML schema languages using formal language theory. ACM Trans. Inter. Tech.\u00a05(4), 1\u201345 (2005)","journal-title":"ACM Trans. Inter. Tech."},{"key":"19_CR30","doi-asserted-by":"crossref","unstructured":"Neven, F., Schwentick, T.: XPath containment in the presence of disjunction, DTDs, and variables. Logical Methods in Computer Science (to appear, 2006)","DOI":"10.2168\/LMCS-2(3:1)2006"},{"key":"19_CR31","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1145\/335168.335173","volume-title":"PODS 2000","author":"Y. Papakonstantinou","year":"2000","unstructured":"Papakonstantinou, Y., Vianu, V.: DTD inference for views of XML data. In: PODS 2000, pp. 35\u201346. ACM Press, New York (2000)"},{"key":"19_CR32","unstructured":"Reuter, F.: An enhanced W3C XML Schema-based language binding for object oriented programming languages (2006) manuscript"},{"issue":"3","key":"19_CR33","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":"19_CR34","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":"19_CR35","unstructured":"Sperberg-McQueen, C.M.: XML Schema 1.0: A language for document grammars. In: XML 2003 (2003)"},{"key":"19_CR36","doi-asserted-by":"crossref","unstructured":"Sperberg-McQueen, C.M., Thompson, H.: XML Schema (2005), http:\/\/www.w3.org\/XML\/Schema","DOI":"10.1145\/1103822.1103834"},{"key":"19_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/800125.804029","volume-title":"STOC 1973","author":"L.J. Stockmeyer","year":"1973","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time: Preliminary report. In: STOC 1973, pp. 1\u20139. ACM Press, New York (1973)"},{"key":"19_CR38","volume-title":"XML Schema","author":"E. Vlist van der","year":"2002","unstructured":"van der Vlist, E.: XML Schema. O\u2019Reilly, Sebastopol (2002)"},{"key":"19_CR39","doi-asserted-by":"crossref","unstructured":"van Emde Boas, P.: The convenience of tilings. In: Complexity, Logic and Recursion Theory. Lec. Notes in Pure and App. Math., vol.\u00a0187, pp. 331\u2013363 (1997)","DOI":"10.1201\/9780429187490-12"},{"key":"19_CR40","unstructured":"Wang, G., Liu, M., Yu, J.X., Sun, B., Yu, G., Lv, J., Lu, H.: Effective schema-based XML query optimization techniques. In: IDEAS 2003, pp. 230\u2013235 (2003)"}],"container-title":["Lecture Notes in Computer Science","Database Theory \u2013 ICDT 2007"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11965893_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:00:45Z","timestamp":1605625245000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11965893_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540692690","9783540692706"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/11965893_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}