{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:36:30Z","timestamp":1725665790151},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642283314"},{"type":"electronic","value":"9783642283321"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"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":[[2012]]},"DOI":"10.1007\/978-3-642-28332-1_27","type":"book-chapter","created":{"date-parts":[[2012,2,29]],"date-time":"2012-02-29T14:45:36Z","timestamp":1330526736000},"page":"313-324","source":"Crossref","is-referenced-by-count":11,"title":["The Membership Problem for Regular Expressions with Unordered Concatenation and Numerical Constraints"],"prefix":"10.1007","author":[{"given":"Dag","family":"Hovland","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"27_CR1","unstructured":"Bezem, M., Klop, J.W., de Vrijer, R. (eds.): Term Rewriting Systems. Cambridge University Press (2003), \n                    \n                      http:\/\/www.cs.vu.nl\/~terese"},{"key":"27_CR2","unstructured":"Brggemann-Klein, A.: Compiler-construction tools and techniques for SGML parsers: Difficulties and solutions (May 1994), \n                    \n                      http:\/\/xml.coverpages.org\/brugg-standardEP-ps.gz"},{"issue":"2","key":"27_CR3","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0304-3975(93)90287-4","volume":"120","author":"A. Br\u00fcggemann-Klein","year":"1993","unstructured":"Br\u00fcggemann-Klein, A.: Regular expressions into finite automata. Theoretical Computer Science\u00a0120(2), 197\u2013213 (1993)","journal-title":"Theoretical Computer Science"},{"key":"27_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/3-540-57273-2_45","volume-title":"Algorithms - ESA \u201993","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)"},{"issue":"2","key":"27_CR5","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1006\/inco.1997.2688","volume":"140","author":"A. Br\u00fcggemann-Klein","year":"1998","unstructured":"Br\u00fcggemann-Klein, A., Wood, D.: One-unambiguous regular languages. Information and Computation\u00a0140(2), 229\u2013253 (1998)","journal-title":"Information and Computation"},{"key":"27_CR6","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: STOC, pp. 151\u2013158. ACM (1971)","DOI":"10.1145\/800157.805047"},{"key":"27_CR7","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)"},{"key":"27_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-642-03816-7_32","volume-title":"Mathematical Foundations of Computer Science 2009","author":"W. Gelade","year":"2009","unstructured":"Gelade, W., Gyssens, M., Martens, W.: Regular Expressions with Counting: Weak versus Strong Determinism. In: Kr\u00e1lovi\u010d, R., Niwi\u0144ski, D. (eds.) MFCS 2009. LNCS, vol.\u00a05734, pp. 369\u2013381. Springer, Heidelberg (2009), \n                    \n                      http:\/\/lrb.cs.uni-dortmund.de\/~martens\/data\/mfcs09-appendix.pdf"},{"key":"27_CR9","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)"},{"issue":"5","key":"27_CR10","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":"27_CR11","doi-asserted-by":"crossref","unstructured":"Ghelli, G., Colazzo, D., Sartiani, C.: Linear time membership for a class of XML types with interleaving and counting. In: PLAN-X (2008)","DOI":"10.1145\/1458082.1458135"},{"key":"27_CR12","doi-asserted-by":"crossref","unstructured":"Ghelli, G., Colazzo, D., Sartiani, C.: Linear time membership in a class of regular expressions with interleaving and counting. In: Shanahan, J.G., Amer-Yahia, S., Manolescu, I., Zhang, Y., Evans, D.A., Kolcz, A., Choi, K.S., Chowdhury, A. (eds.) CIKM, pp. 389\u2013398. ACM (2008)","DOI":"10.1145\/1458082.1458135"},{"key":"27_CR13","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0304-3975(78)90020-8","volume":"7","author":"S.A. Greibach","year":"1978","unstructured":"Greibach, S.A.: Remarks on blind and partially blind one-way multicounter machines. Theor. Comput. Sci.\u00a07, 311\u2013324 (1978)","journal-title":"Theor. Comput. Sci."},{"key":"27_CR14","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)"},{"key":"27_CR15","unstructured":"Hovland, D.: Feasible Algorithms for Semantics \u2014 Employing Automata and Inference Systems. Ph.D. thesis, Universitetet i Bergen (2010), \n                    \n                      http:\/\/hdl.handle.net\/1956\/4325"},{"key":"27_CR16","unstructured":"ISO 8879. Information processing \u2014 text and office systems \u2014 standard generalized markup language (SGML) (October 1986)"},{"key":"27_CR17","first-page":"163","volume-title":"SPLST","author":"P. Kilpel\u00e4inen","year":"2003","unstructured":"Kilpel\u00e4inen, P., Tuhkanen, R.: Regular expressions with numerical occurrence indicators - preliminary results. In: Kilpel\u00e4inen, P., P\u00e4ivinen, N. (eds.) SPLST, pp. 163\u2013173. University of Kuopio, Department of Computer Science (2003)"},{"key":"27_CR18","doi-asserted-by":"crossref","unstructured":"Kilpel\u00e4inen, P., Tuhkanen, R.: Towards efficient implementation of XML schema content models. In: Munson, E.V., Vion-Dury, J.Y. (eds.) ACM Symposium on Document Engineering, pp. 239\u2013241. ACM (2004)","DOI":"10.1145\/1030397.1030441"},{"issue":"6","key":"27_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. Information and Computation\u00a0205(6), 890\u2013916 (2007)","journal-title":"Information and Computation"},{"issue":"3","key":"27_CR20","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 J.\u00a016(3), 317\u2013342 (2007)","journal-title":"VLDB J."},{"issue":"2","key":"27_CR21","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. Inf. Comput.\u00a0115(2), 293\u2013311 (1994)","journal-title":"Inf. Comput."},{"key":"27_CR22","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential space. In: Proceedings of FOCS, pp. 125\u2013129. IEEE (1972)","DOI":"10.1109\/SWAT.1972.29"},{"key":"27_CR23","doi-asserted-by":"crossref","unstructured":"Ogden, W.F., Riddle, W.E., Rounds, W.C.: Complexity of expressions allowing concurrency. In: POPL, pp. 185\u2013194 (1978)","DOI":"10.1145\/512760.512780"},{"key":"27_CR24","unstructured":"Sperberg-McQueen, C.M.: Notes on finite state automata with counters (2004), \n                    \n                      http:\/\/www.w3.org\/TR\/xml\/"},{"key":"27_CR25","doi-asserted-by":"crossref","unstructured":"Tseitin, G.S.: On the complexity of derivation in propositional calculus. In: Studies in Constructive Mathematics and Mathematical Logic, Part 2, pp. 115\u2013225 (1968)","DOI":"10.1007\/978-1-4899-5327-8_25"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-28332-1_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T08:32:37Z","timestamp":1556440357000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-28332-1_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642283314","9783642283321"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-28332-1_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}