{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:46:39Z","timestamp":1725536799202},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642038150"},{"type":"electronic","value":"9783642038167"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03816-7_32","type":"book-chapter","created":{"date-parts":[[2009,8,19]],"date-time":"2009-08-19T10:43:03Z","timestamp":1250678583000},"page":"369-381","source":"Crossref","is-referenced-by-count":9,"title":["Regular Expressions with Counting: Weak versus Strong Determinism"],"prefix":"10.1007","author":[{"given":"Wouter","family":"Gelade","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Gyssens","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wim","family":"Martens","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"32_CR1","first-page":"197","volume":"120","author":"A. Br\u00fcggemann-Klein","year":"1993","unstructured":"Br\u00fcggemann-Klein, A.: Regular expressions into finite automata. Theor.\u00a0Comput.\u00a0Sci.\u00a0120(2), 197\u2013213 (1993)","journal-title":"Theor.\u00a0Comput.\u00a0Sci."},{"issue":"2","key":"32_CR2","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":"32_CR3","doi-asserted-by":"crossref","unstructured":"Colazzo, D., Ghelli, G., Sartiani, C.: Efficient asymmetric inclusion between regular expression types. In: ICDT, pp. 174\u2013182 (2009)","DOI":"10.1145\/1514894.1514916"},{"key":"32_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/3-540-44881-0_18","volume-title":"Rewriting Techniques and Applications","author":"S. Dal-Zilio","year":"2003","unstructured":"Dal-Zilio, S., Lugiez, D.: XML schema, tree logic and sheaves automata. In: Nieuwenhuis, R. (ed.) RTA 2003. LNCS, vol.\u00a02706, pp. 246\u2013263. Springer, Heidelberg (2003)"},{"key":"32_CR5","doi-asserted-by":"crossref","unstructured":"Esparza, J.: Decidability and complexity of Petri net problems \u2013 an introduction. In: Petri Nets, pp. 374\u2013428 (1996)","DOI":"10.1007\/3-540-65306-6_20"},{"key":"32_CR6","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"32_CR7","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":"2007","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 (2007)"},{"key":"32_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/978-3-540-85238-4_29","volume-title":"Mathematical Foundations of Computer Science 2008","author":"W. Gelade","year":"2008","unstructured":"Gelade, W.: Succinctness of regular expressions with interleaving, intersection and counting. In: Ochma\u0144ski, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol.\u00a05162, pp. 363\u2013374. Springer, Heidelberg (2008)"},{"issue":"11","key":"32_CR9","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. Softw. Pract. and Exp.\u00a018(11), 1063\u20131072 (1988)","journal-title":"Softw. Pract. and Exp."},{"key":"32_CR10","unstructured":"Kilpel\u00e4inen, P.: Inclusion of unambiguous #res is NP-hard (May 2004) (unpublished)"},{"key":"32_CR11","unstructured":"Kilpel\u00e4inen, P., Tuhkanen, R.: Regular expressions with numerical occurrence indicators \u2014 preliminary results. In: SPLST 2003, pp. 163\u2013173 (2003)"},{"key":"32_CR12","first-page":"239","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, New York (2004)"},{"issue":"6","key":"32_CR13","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.\u00a0Comput.\u00a0205(6), 890\u2013916 (2007)","journal-title":"Inform.\u00a0Comput."},{"issue":"3","key":"32_CR14","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/s00778-005-0169-1","volume":"16","author":"C. Koch","year":"2007","unstructured":"Koch, C., Scherzinger, S.: Attribute grammars for scalable query processing on XML streams. VLDB Journal\u00a016(3), 317\u2013342 (2007)","journal-title":"VLDB Journal"},{"key":"32_CR15","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":"32_CR16","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":"32_CR17","unstructured":"Mount, D.W.: Bioinformatics: Sequence and Genome Analysis. Cold Spring Harbor Laboratory Press (September 2004)"},{"key":"32_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1136","DOI":"10.1007\/978-3-540-27836-8_94","volume-title":"Automata, Languages and Programming","author":"H. Seidl","year":"2004","unstructured":"Seidl, H., Schwentick, T., Muscholl, A., Habermehl, P.: Counting in trees for free. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 1136\u20131149. Springer, Heidelberg (2004)"},{"issue":"1","key":"32_CR19","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1142\/S012905410200100X","volume":"13","author":"G. Pighizzini","year":"2002","unstructured":"Pighizzini, G., Shallit, J.: Unary language operations, state complexity and Jacobsthal\u2019s function. Int. J. Found. Comp. Sc.\u00a013(1), 145\u2013159 (2002)","journal-title":"Int. J. Found. Comp. Sc."},{"key":"32_CR20","unstructured":"Sperberg-McQueen, C.M.: Notes on finite state automata with counters (2004), http:\/\/www.w3.org\/XML\/2004\/05\/msm-cfa.html"},{"key":"32_CR21","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":"32_CR22","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: From monadic logic to PSL. Pillars of Computer Science, 656\u2013681 (2008)","DOI":"10.1007\/978-3-540-78127-1_36"},{"key":"32_CR23","volume-title":"Programming Perl","author":"L. Wall","year":"2000","unstructured":"Wall, L., Christiansen, T., Orwant, J.: Programming Perl. O\u2019Reilly, Sebastopol (2000)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03816-7_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T22:33:42Z","timestamp":1558478022000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03816-7_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642038150","9783642038167"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03816-7_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}