{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:53:24Z","timestamp":1756000404350},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642370748"},{"type":"electronic","value":"9783642370755"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-37075-5_19","type":"book-chapter","created":{"date-parts":[[2013,2,18]],"date-time":"2013-02-18T14:37:23Z","timestamp":1361198243000},"page":"289-304","source":"Crossref","is-referenced-by-count":5,"title":["Deciding Definability by Deterministic Regular Expressions"],"prefix":"10.1007","author":[{"given":"Wojciech","family":"Czerwi\u0144ski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Claire","family":"David","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katja","family":"Losemann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wim","family":"Martens","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"Arenas, M., Barcel\u00f3, P., Libkin, L., Murlak, F.: Foundations of Data Exchange. Book (to appear, 2013)","DOI":"10.1017\/CBO9781139060158"},{"issue":"4","key":"19_CR2","doi-asserted-by":"publisher","first-page":"710","DOI":"10.1145\/1042046.1042050","volume":"29","author":"A. Balmin","year":"2004","unstructured":"Balmin, A., Papakonstantinou, Y., Vianu, V.: Incremental validation of XML documents. ACM Trans. on Datab. Syst.\u00a029(4), 710\u2013751 (2004)","journal-title":"ACM Trans. on Datab. Syst."},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"Bex, G.J., Gelade, W., Martens, W., Neven, F.: Simplifying XML Schema: effortless handling of nondeterministic regular expressions. In: ACM SIGMOD International Conference on Management of Data (SIGMOD), pp. 731\u2013744 (2009)","DOI":"10.1145\/1559845.1559922"},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"Bex, G.J., Gelade, W., Neven, F., Vansummeren, S.: Learning deterministic regular expressions for the inference of schemas from XML data. In: World Wide Web Conference (WWW), pp. 825\u2013834 (2008)","DOI":"10.1145\/1367497.1367609"},{"key":"19_CR5","unstructured":"Bray, T., Paoli, J., Sperberg-McQueen, C.M., Maler, E., Yergeau, F.: Extensible Markup Language XML 1.0, 5th edn. W3C Recommendation (November 2008)"},{"key":"19_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/3-540-55210-3_182","volume-title":"STACS 92","author":"A. Br\u00fcggemann-Klein","year":"1992","unstructured":"Br\u00fcggemann-Klein, A., Wood, D.: Deterministic Regular Languages. In: Finkel, A., Jantzen, M. (eds.) STACS 1992. LNCS, vol.\u00a0577, pp. 173\u2013184. Springer, Heidelberg (1992)"},{"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. Inf. and Comput.\u00a0142(2), 182\u2013206 (1998)","journal-title":"Inf. and Comput."},{"key":"19_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/978-3-540-85762-4_7","volume-title":"Theoretical Aspects of Computing - ICTAC 2008","author":"H. Chen","year":"2008","unstructured":"Chen, H., Chen, L.: Inclusion Test Algorithms for One-Unambiguous Regular Expressions. In: Fitzgerald, J.S., Haxthausen, A.E., Yenigun, H. (eds.) ICTAC 2008. LNCS, vol.\u00a05160, pp. 96\u2013110. Springer, Heidelberg (2008)"},{"issue":"7","key":"19_CR9","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1016\/j.is.2008.10.001","volume":"34","author":"D. Colazzo","year":"2009","unstructured":"Colazzo, D., Ghelli, G., Sartiani, C.: Efficient inclusion for a class of XML types with interleaving and counting. Inform. Syst.\u00a034(7), 643\u2013656 (2009)","journal-title":"Inform. Syst."},{"key":"19_CR10","unstructured":"Fallside, D., Walmsley, P.: XML Schema Part 0: Primer, 2nd edn. World Wide Web Consortium (October 2004)"},{"issue":"1","key":"19_CR11","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1137\/100814196","volume":"41","author":"W. Gelade","year":"2012","unstructured":"Gelade, W., Gyssens, M., Martens, W.: Regular expressions with counting: Weak versus strong determinism. SIAM J. Comput.\u00a041(1), 160\u2013190 (2012)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"19_CR12","doi-asserted-by":"publisher","first-page":"2021","DOI":"10.1137\/070697367","volume":"38","author":"W. Gelade","year":"2009","unstructured":"Gelade, W., Martens, W., Neven, F.: Optimizing schema languages for XML: Numerical constraints and interleaving. SIAM J. Comput.\u00a038(5), 2021\u20132043 (2009)","journal-title":"SIAM J. Comput."},{"key":"19_CR13","first-page":"1","volume":"4","author":"W. Gelade","year":"2012","unstructured":"Gelade, W., Neven, F.: Succinctness of the complement and intersection of regular expressions. ACM Trans. on Comput. Logic\u00a04, 1\u201319 (2012)","journal-title":"ACM Trans. on Comput. Logic"},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"Groz, B., Maneth, S., Staworko, S.: Deterministic regular expressions in linear time. In: ACM Symposium on Principles of Database Systems (PODS), pp. 49\u201360 (2012)","DOI":"10.1145\/2213556.2213566"},{"key":"19_CR15","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison Wesley (2007)"},{"key":"19_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/978-3-642-03466-4_15","volume-title":"Theoretical Aspects of Computing - ICTAC 2009","author":"D. Hovland","year":"2009","unstructured":"Hovland, D.: Regular Expressions with Numerical Constraints and Automata with Counters. In: Leucker, M., Morgan, C. (eds.) ICTAC 2009. LNCS, vol.\u00a05684, pp. 231\u2013245. Springer, Heidelberg (2009)"},{"issue":"1","key":"19_CR17","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"N.D. Jones","year":"1975","unstructured":"Jones, N.D.: Space-bounded reducibility among combinatorial problems. J. Comput. Syst. Sci.\u00a011(1), 68\u201385 (1975)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"19_CR18","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1016\/j.is.2010.10.001","volume":"36","author":"P. Kilpel\u00e4inen","year":"2011","unstructured":"Kilpel\u00e4inen, P.: Checking determinism of XML Schema content models in optimal time. Inform. Syst.\u00a036(3), 596\u2013617 (2011)","journal-title":"Inform. Syst."},{"issue":"6","key":"19_CR19","doi-asserted-by":"publisher","first-page":"890","DOI":"10.1016\/j.ic.2006.12.003","volume":"205","author":"P. Kilpel\u00e4inen","year":"2007","unstructured":"Kilpel\u00e4inen, P., Tuhkanen, R.: One-unambiguity of regular expressions with numeric occurrence indicators. Inform. and Comput.\u00a0205(6), 890\u2013916 (2007)","journal-title":"Inform. and Comput."},{"key":"19_CR20","doi-asserted-by":"crossref","unstructured":"Konrad, C., Magniez, F.: Validating XML documents in the streaming model with external memory. In: International Conference on Database Theory (ICDT), pp. 34\u201345 (2012)","DOI":"10.1145\/2274576.2274581"},{"key":"19_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/978-3-642-32589-2_56","volume-title":"Mathematical Foundations of Computer Science 2012","author":"K. Losemann","year":"2012","unstructured":"Losemann, K., Martens, W., Niewerth, M.: Descriptional Complexity of Deterministic Regular Expressions. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol.\u00a07464, pp. 643\u2013654. Springer, Heidelberg (2012)"},{"key":"19_CR22","doi-asserted-by":"crossref","unstructured":"Maneth, S., Berlea, A., Perst, T., Seidl, H.: XML type checking with macro tree transducers. In: ACM Symposium on Principles of Database Systems (PODS), pp. 283\u2013294 (2005)","DOI":"10.1145\/1065167.1065203"},{"issue":"1","key":"19_CR23","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/j.tcs.2004.10.035","volume":"336","author":"W. Martens","year":"2005","unstructured":"Martens, W., Neven, F.: On the complexity of typechecking top-down XML transformations. Theor. Comp. Sc.\u00a0336(1), 153\u2013180 (2005)","journal-title":"Theor. Comp. Sc."},{"issue":"1","key":"19_CR24","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. J. Comput. Syst. Sci.\u00a066(1), 66\u201397 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"19_CR25","doi-asserted-by":"crossref","unstructured":"Neven, F., Schwentick, T.: On the complexity of XPath containment in the presence of disjunction, DTDs, and variables. Log. Meth. in Comp. Sc.\u00a02(3) (2006)","DOI":"10.2168\/LMCS-2(3:1)2006"},{"key":"19_CR26","doi-asserted-by":"crossref","unstructured":"Segoufin, L., Vianu, V.: Validating streaming XML documents. In: ACM Symposium on Principles of Database Systems (PODS), pp. 53\u201364 (2002)","DOI":"10.1145\/543613.543622"},{"key":"19_CR27","doi-asserted-by":"crossref","unstructured":"van Emde Boas, P.: The convenience of tilings. In: Complexity, Logic and Recursion Theory, pp. 331\u2013363. Marcel Dekker Inc. (1997)","DOI":"10.1201\/9780429187490-12"},{"key":"19_CR28","series-title":"Lecture Notes in Computer Science","first-page":"297","volume-title":"Database Theory - ICDT 2003","author":"P.T. Wood","year":"2002","unstructured":"Wood, P.T.: Containment for XPath Fragments under DTD Constraints. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds.) ICDT 2003. LNCS, vol.\u00a02572, pp. 297\u2013311. Springer, Heidelberg (2002)"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-37075-5_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,29]],"date-time":"2023-06-29T11:55:55Z","timestamp":1688039755000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-37075-5_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642370748","9783642370755"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-37075-5_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}