{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:19:53Z","timestamp":1725517193621},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540852377"},{"type":"electronic","value":"9783540852384"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85238-4_29","type":"book-chapter","created":{"date-parts":[[2008,8,18]],"date-time":"2008-08-18T15:34:36Z","timestamp":1219073676000},"page":"363-374","source":"Crossref","is-referenced-by-count":5,"title":["Succinctness of Regular Expressions with Interleaving, Intersection and Counting"],"prefix":"10.1007","author":[{"given":"Wouter","family":"Gelade","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"29_CR1","doi-asserted-by":"crossref","unstructured":"Bex, G., Gelade, W., Neven, F., Vansummeren, S.: Learning deterministic regular expressions for the inference of schemas from XML data. In: WWW, pp. 825\u2013834 (2008)","DOI":"10.1145\/1367497.1367609"},{"key":"29_CR2","unstructured":"Bex, G., Neven, F., Schwentick, T., Tuyls, K.: Inference of concise DTDs from XML data. In: VLDB, pp. 115\u2013126 (2006)"},{"key":"29_CR3","unstructured":"Bex, G., Neven, F., Vansummeren, S.: Inferring XML Schema Definitions from XML data. In: VLDB, pp. 998\u20131009 (2007)"},{"issue":"2","key":"29_CR4","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0304-3975(93)90287-4","volume":"120","author":"A. Bruggemann-Klein","year":"1993","unstructured":"Bruggemann-Klein, A.: Regular expressions into finite automata. Theoretical Computer Science\u00a0120(2), 197\u2013213 (1993)","journal-title":"Theoretical Computer Science"},{"key":"29_CR5","unstructured":"Clark, J., Murata, M.: RELAX NG Specification. OASIS (December 2001)"},{"issue":"2","key":"29_CR6","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/S0019-9958(72)90288-4","volume":"20","author":"R.S. Cohen","year":"1972","unstructured":"Cohen, R.S.: Rank-non-increasing transformations on transition graphs. Information and Control\u00a020(2), 93\u2013113 (1972)","journal-title":"Information and Control"},{"key":"29_CR7","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1307\/mmj\/1028998975","volume":"10","author":"L.C. Eggan","year":"1963","unstructured":"Eggan, L.C.: Transition graphs and the star height of regular events. Michigan Mathematical Journal\u00a010, 385\u2013397 (1963)","journal-title":"Michigan Mathematical Journal"},{"issue":"2","key":"29_CR8","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/S0022-0000(76)80034-7","volume":"12","author":"A. Ehrenfeucht","year":"1976","unstructured":"Ehrenfeucht, A., Zeiger, H.: Complexity measures for regular expressions. Journal of Computer and System Sciences\u00a012(2), 134\u2013146 (1976)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"29_CR9","first-page":"407","volume":"10","author":"K. Ellul","year":"2005","unstructured":"Ellul, K., Krawetz, B., Shallit, J., Wang, M.: Regular expressions: New results and open problems. Journal of Automata, Languages and Combinatorics\u00a010(4), 407\u2013437 (2005)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"29_CR10","doi-asserted-by":"crossref","unstructured":"F\u00fcrer, M.: The complexity of the inequivalence problem for regular expressions with intersection. In: ICALP, pp. 234\u2013245 (1980)","DOI":"10.1007\/3-540-10003-2_74"},{"key":"29_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/11965893_19","volume-title":"Database Theory \u2013 ICDT 2007","author":"W. Gelade","year":"2006","unstructured":"Gelade, W., Martens, W., Neven, F.: Optimizing schema languages for XML: Numerical constraints and interleaving. In: Schwentick, T., Suciu, D. (eds.) ICDT 2007. LNCS, vol.\u00a04353, pp. 269\u2013283. Springer, Heidelberg (2006)"},{"key":"29_CR12","unstructured":"Gelade, W., Neven, F.: Succinctness of the complement and intersection of regular expressions. In: STACS, pp. 325\u2013336 (2008)"},{"key":"29_CR13","doi-asserted-by":"crossref","unstructured":"Gruber, H., Holzer, M.: Finite automata, digraph connectivity, and regular expression size. In: ICALP (to appear, 2008)","DOI":"10.1007\/978-3-540-70583-3_4"},{"key":"29_CR14","unstructured":"Gruber, H., Holzer, M.: Language operations with regular expressions of polynomial size. In: DCFS (to appear, 2008)"},{"key":"29_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/978-3-540-78499-9_20","volume-title":"Foundations of Software Science and Computational Structures","author":"H. Gruber","year":"2008","unstructured":"Gruber, H., Johannsen, J.: Optimal lower bounds on regular expression size using communication complexity. In: Amadio, R.M. (ed.) FOSSACS 2008. LNCS, vol.\u00a04962, pp. 273\u2013286. Springer, Heidelberg (2008)"},{"issue":"11","key":"29_CR16","doi-asserted-by":"publisher","first-page":"1063","DOI":"10.1002\/spe.4380181105","volume":"18","author":"A. Hume","year":"1988","unstructured":"Hume, A.: A tale of two greps. Software, Practice and Experience\u00a018(11), 1063\u20131072 (1988)","journal-title":"Software, Practice and Experience"},{"issue":"1","key":"29_CR17","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/S0020-0190(05)80006-7","volume":"40","author":"T. Jiang","year":"1991","unstructured":"Jiang, T., Ravikumar, B.: A note on the space complexity of some decision problems for finite automata. Information Processing Letters\u00a040(1), 25\u201331 (1991)","journal-title":"Information Processing Letters"},{"key":"29_CR18","unstructured":"Kilpelainen, P., Tuhkanen, R.: Regular expressions with numerical occurrence indicators \u2014 preliminary results. In: SPLST 2003, pp. 163\u2013173 (2003)"},{"key":"29_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1007\/3-540-45687-2_37","volume-title":"Mathematical Foundations of Computer Science 2002","author":"O. Kupferman","year":"2002","unstructured":"Kupferman, O., Zuhovitzky, S.: An improved algorithm for the membership problem for extended regular expressions. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol.\u00a02420, pp. 446\u2013458. Springer, Heidelberg (2002)"},{"issue":"2","key":"29_CR20","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-this time with interleaving. Information and Computation\u00a0115(2), 293\u2013311 (1994)","journal-title":"Information and Computation"},{"issue":"1\/2","key":"29_CR21","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0019-9958(67)90481-0","volume":"11","author":"R. McNaughton","year":"1967","unstructured":"McNaughton, R.: The loop complexity of pure-group events. Information and Control\u00a011(1\/2), 167\u2013176 (1967)","journal-title":"Information and Control"},{"issue":"3","key":"29_CR22","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/S0020-0255(69)80016-2","volume":"1","author":"R. McNaughton","year":"1969","unstructured":"McNaughton, R.: The loop complexity of regular events. Information Sciences\u00a01(3), 305\u2013328 (1969)","journal-title":"Information Sciences"},{"key":"29_CR23","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential space. In: FOCS, pp. 125\u2013129 (1972)","DOI":"10.1109\/SWAT.1972.29"},{"key":"29_CR24","unstructured":"Petersen, H.: Decision problems for generalized regular expressions. In: DCAGRS, pp. 22\u201329 (2000)"},{"key":"29_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/3-540-45841-7_42","volume-title":"STACS 2002","author":"H. Petersen","year":"2002","unstructured":"Petersen, H.: The membership problem for regular expressions with intersection is complete in LOGCFL. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol.\u00a02285, pp. 513\u2013522. Springer, Heidelberg (2002)"},{"issue":"5","key":"29_CR26","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0020-0190(79)90073-5","volume":"9","author":"J.M. Robson","year":"1979","unstructured":"Robson, J.M.: The emptiness of complement problem for semi extended regular expressions requires c $^{\\mbox{n}}$ space. Information Processing Letters\u00a09(5), 220\u2013222 (1979)","journal-title":"Information Processing Letters"},{"issue":"4","key":"29_CR27","first-page":"579","volume":"74","author":"R. Schott","year":"2006","unstructured":"Schott, R., Spehner, J.C.: Shuffle of words and araucaria trees. Fundamenta Informatica\u00a074(4), 579\u2013601 (2006)","journal-title":"Fundamenta Informatica"},{"key":"29_CR28","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":"29_CR29","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time: Preliminary report. In: STOC, pp. 1\u20139 (1973)","DOI":"10.1145\/800125.804029"},{"key":"29_CR30","volume-title":"Programming Perl","author":"L. Wall","year":"2000","unstructured":"Wall, L., Christiansen, T., Orwant, J.: Programming Perl, 3rd edn. OReilly, Sebastopol (2000)","edition":"3"},{"key":"29_CR31","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/978-3-642-59136-5_2","volume-title":"Handbook of formal languages, ch. 2","author":"S. Yu","year":"1997","unstructured":"Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of formal languages, ch. 2, vol.\u00a01, pp. 41\u2013110. Springer, Heidelberg (1997)"},{"issue":"2","key":"29_CR32","first-page":"221","volume":"6","author":"S. Yu","year":"2001","unstructured":"Yu, S.: State complexity of regular languages. Journal of Automata, Languages and Combinatorics\u00a06(2), 221\u2013234 (2001)","journal-title":"Journal of Automata, Languages and Combinatorics"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2008"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85238-4_29.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:23:28Z","timestamp":1606184608000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85238-4_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540852377","9783540852384"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85238-4_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}