{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T23:10:07Z","timestamp":1771024207438,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642387708","type":"print"},{"value":"9783642387715","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38771-5_8","type":"book-chapter","created":{"date-parts":[[2013,6,9]],"date-time":"2013-06-09T22:16:25Z","timestamp":1370816185000},"page":"70-81","source":"Crossref","is-referenced-by-count":8,"title":["Cuts in Regular Expressions"],"prefix":"10.1007","author":[{"given":"Martin","family":"Berglund","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henrik","family":"Bj\u00f6rklund","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Drewes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Brink","family":"van der Merwe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bruce","family":"Watson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"8_CR1","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A.K. Chandra","year":"1981","unstructured":"Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation. J. ACM\u00a028(1), 114\u2013133 (1981)","journal-title":"J. ACM"},{"key":"8_CR2","volume-title":"Mastering Regular Expressions","author":"J.E.F. Friedl","year":"1997","unstructured":"Friedl, J.E.F.: Mastering Regular Expressions. Reilly & Associates, Inc., Sebastopol (1997)"},{"key":"8_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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)"},{"issue":"31-33","key":"8_CR4","doi-asserted-by":"publisher","first-page":"2987","DOI":"10.1016\/j.tcs.2010.04.036","volume":"411","author":"W. Gelade","year":"2011","unstructured":"Gelade, W.: Succinctness of regular expressions with interleaving, intersection and counting. Theor. Comput. Sci.\u00a0411(31-33), 2987\u20132998 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"8_CR5","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."},{"issue":"1","key":"8_CR6","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/2071368.2071372","volume":"13","author":"W. Gelade","year":"2012","unstructured":"Gelade, W., Neven, F.: Succinctness of the complement and intersection of regular expressions. ACM Trans. Comput. Logic\u00a013(1), Article 4 (2012)","journal-title":"ACM Trans. Comput. Logic"},{"key":"8_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1070\/RM1961v016n05ABEH004112","volume":"16","author":"V.M. Glushkov","year":"1961","unstructured":"Glushkov, V.M.: The abstract theory of automata. Russian Mathematical Surveys\u00a016, 1\u201353 (1961)","journal-title":"Russian Mathematical Surveys"},{"key":"8_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/978-3-642-02737-6_22","volume-title":"Developments in Language Theory","author":"H. Gruber","year":"2009","unstructured":"Gruber, H., Holzer, M.: Tight bounds on the descriptional complexity of regular expressions. In: Diekert, V., Nowotka, D. (eds.) DLT 2009. LNCS, vol.\u00a05583, pp. 276\u2013287. Springer, Heidelberg (2009)"},{"key":"8_CR9","unstructured":"Kilpel\u00e4inen, P., Tuhkanen, R.: Regular expressions with numerical occurrence indicators - preliminary results. In: SPLST, pp. 163\u2013173 (2003)"},{"key":"8_CR10","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":"8_CR11","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. Inform. and Comput.\u00a0115(2), 293\u2013311 (1994)","journal-title":"Inform. and Comput."},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential time. In: SWAT (FOCS), pp. 125\u2013129 (1972)","DOI":"10.1109\/SWAT.1972.29"},{"key":"8_CR13","unstructured":"Perl 5 Porters. perlre (2012), \n                    \n                      http:\/\/perldoc.perl.org\/perlre.html\n                    \n                    \n                   (accessed January 16, 2013)"},{"key":"8_CR14","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":"8_CR15","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\n                  \n                    n\n                   space. Inform. Processing Letters\u00a09(5), 220\u2013222 (1979)","journal-title":"Inform. Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38771-5_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T20:31:43Z","timestamp":1557779503000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38771-5_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642387708","9783642387715"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38771-5_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}