{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:26:55Z","timestamp":1761611215897,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540440406"},{"type":"electronic","value":"9783540456872"}],"license":[{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45687-2_37","type":"book-chapter","created":{"date-parts":[[2007,10,19]],"date-time":"2007-10-19T08:57:47Z","timestamp":1192784267000},"page":"446-458","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["An Improved Algorithm for the Membership Problem for Extended Regular Expressions"],"prefix":"10.1007","author":[{"given":"Orna","family":"Kupferman","sequence":"first","affiliation":[]},{"given":"Sharon","family":"Zuhovitzky","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,10,4]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"A.V. Aho. Algorithms for finding patterns in strings. Handbook of Theoretical Computer Science, pages 255\u2013300, 1990.","key":"37_CR1","DOI":"10.1016\/B978-0-444-88071-0.50010-2"},{"key":"37_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1007\/3-540-51486-4_67","volume-title":"Proc. 14th International Symp. on Mathematical Foundations of Computer Science","author":"D.H.K.+.8.9._.J. Dassow","year":"1989","unstructured":"[DHK+89]_J. Dassow, J. Hromkovic, J. Karhumaki, B. Rovan, and A. Slobodova. On the power of synchronization in parallel computing. In Proc. 14th International Symp. on Mathematical Foundations of Computer Science, volume 379 of Lecture Notes in Computer Science, pages 196\u2013206. Springer-Verlag, 1989."},{"unstructured":"S. Hirst. A new algorithm solving membership of extended regular expressions. Technical report, Basser Department of Computer Science, The University of Sydney, 1989.","key":"37_CR3"},{"doi-asserted-by":"crossref","unstructured":"J.E. Hopcroft, R. Motwani, and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation (2nd Edition). Addison-Wesley, 2000.","key":"37_CR4","DOI":"10.1145\/568438.568455"},{"key":"37_CR5","series-title":"Lect Notes Comput Sci","first-page":"156","volume-title":"Proc. 13th Colloq. on Automata, Programming, and Languages","author":"J. Hrokovic","year":"1986","unstructured":"J. Hrokovic. Tradeoffs for language recognition on parallel computing models. In Proc. 13th Colloq. on Automata, Programming, and Languages, volume 226 of Lecture Notes in Computer Science, pages 156\u2013166. Springer-Verlag, 1986."},{"unstructured":"J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.","key":"37_CR6"},{"key":"37_CR7","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/S0020-0190(05)80006-7","volume":"40","author":"T. Jiang","year":"1991","unstructured":"T. Jiang and B. Ravikumar. A note on the space complexity of some decision problems for finite automata. Information Processing Letters, 40:25\u201331, 1991.","journal-title":"Information Processing Letters"},{"issue":"1\/2","key":"37_CR8","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/BF01188587","volume":"13","author":"J. R. Knight","year":"1995","unstructured":"James R. Knight and Eugene W. Myers. Super-pattern matching. Algorithmica, 13(1\/2):211\u2013243, 1995.","journal-title":"Algorithmica"},{"unstructured":"O. Kupferman, A. Ta-Shma, and M.Y. Vardi. Counting with automata. Submitted, 2001.","key":"37_CR9"},{"doi-asserted-by":"crossref","unstructured":"A.R. Meyer and L.J. Stockmeyer. Word problems requiring exponential time: Preliminary report. In Proc. 5th ACM Symp. on Theory of Computing, pages 1\u20139, 1973.","key":"37_CR10","DOI":"10.1145\/800125.804029"},{"issue":"4","key":"37_CR11","first-page":"430","volume":"39","author":"G. Myers","year":"1992","unstructured":"G. Myers. A four russians algorithm for regular expression pattern matching. Journal of the Association for Computing Machinery, 39(4):430\u2013448, 1992.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"37_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-45691-0","volume-title":"Proc. 18th Symp. on Theoretical Aspects of Computer Science","author":"H. Petersen","year":"2002","unstructured":"H. Petersen. The membership problem for regular expressions with intersection is complete in LOGCFL. In Proc. 18th Symp. on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science. Springer-Verlag, 2002."},{"key":"37_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"518","DOI":"10.1007\/BFb0017175","volume-title":"Proc. 13th International Symp. on Mathematical Foundations of Computer Science","author":"A. Slobodova","year":"1988","unstructured":"A. Slobodova. On the power of communication in alternating machines. In Proc. 13th International Symp. on Mathematical Foundations of Computer Science, volume 324 of Lecture Notes in Computer Science, pages 518\u2013528, 1988."},{"key":"37_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1007\/3-540-44612-5_65","volume-title":"Proc. 25th International Symp. on Mathematical Foundations of Computer Science","author":"H. Yamamoto","year":"2000","unstructured":"H. Yamamoto. An automata-based recognition algorithm for semi-extended regular expressions. In Proc. 25th International Symp. on Mathematical Foundations of Computer Science, volume 1893 of Lecture Notes in Computer Science, pages 699\u2013708. Springer-Verlag, 2000."},{"key":"37_CR15","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1007\/3-540-44968-X_45","volume-title":"Proc. 6th International Computing and Combinatorics Conference","author":"H. Yamamoto","year":"2000","unstructured":"H. Yamamoto. On the power of input-synchronized alternating finite automata. In Proc. 6th International Computing and Combinatorics Conference, volume 1858 of Lecture Notes in Computer Science, pages 457\u2013466, 2000."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2002"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45687-2_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,8]],"date-time":"2023-02-08T22:04:44Z","timestamp":1675893884000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/3-540-45687-2_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540440406","9783540456872"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-45687-2_37","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]},"assertion":[{"value":"4 October 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}