{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T06:13:44Z","timestamp":1784182424366,"version":"3.55.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540432838","type":"print"},{"value":"9783540458418","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45841-7_42","type":"book-chapter","created":{"date-parts":[[2007,8,12]],"date-time":"2007-08-12T04:11:17Z","timestamp":1186891877000},"page":"513-522","source":"Crossref","is-referenced-by-count":12,"title":["The Membership Problem for Regular Expressions with Intersection Is Complete in LOGCFL"],"prefix":"10.1007","author":[{"given":"Holger","family":"Petersen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2002,2,21]]},"reference":[{"key":"42_CR1","first-page":"255","volume-title":"Handbook of Theoretical Computer Science","author":"A. V. Aho","year":"1990","unstructured":"A. V. Aho. Algorithms for finding patterns in strings. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science: Volume A,Algorithms and Complexity, pages 255\u2013300. MIT Press, Cambridge, MA, 1990."},{"key":"42_CR2","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1137\/0218038","volume":"18","author":"A. Borodin","year":"1989","unstructured":"A. Borodin, S. A. Cook, P. W. Dymond, W. L. Ruzzo, and M. Tompa. Two applications of inductive counting for complementation problems. SIAM Journal on Computing, 18:559\u2013578, 1989.","journal-title":"SIAM Journal on Computing"},{"key":"42_CR3","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. A. Cook","year":"1985","unstructured":"S. A. Cook. A taxonomy of problems with fast parallel algorithms. Information and Control, 64:2\u201322, 1985.","journal-title":"Information and Control"},{"key":"42_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1007\/3-540-10003-2_74","volume-title":"The complexity of the inequivalence problem for regular expressions with intersection","author":"M. F\u00fcrer","year":"1980","unstructured":"M. F\u00fcrer. The complexity of the inequivalence problem for regular expressions with intersection. In J. W. D. Bakker and J. van Leeuwen, editors, Proceedings of the 7th International Colloquium on Automata, Languages and Programming (ICALP\u201980), Noordwijkerhout (Netherlands), number 85 in Lecture Notes in Computer Science, pages 234\u2013245, Berlin-Heidelberg-New York, 1980. Springer."},{"key":"42_CR5","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195085914.001.0001","volume-title":"Limits to Parallel Computation: P-Completeness Theory","author":"R. Greenlaw","year":"1995","unstructured":"R. Greenlaw, H. J. Hoover, and W. L. Ruzzo. Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, New York, Oxford, 1995."},{"key":"42_CR6","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1137\/0202025","volume":"2","author":"S. A. Greibach","year":"1973","unstructured":"S. A. Greibach. The hardest context-free language. SIAM Journal on Computing, 2:304\u2013310, 1973.","journal-title":"SIAM Journal on Computing"},{"key":"42_CR7","unstructured":"S. C. Hirst. A new algorithm solving membership of extended regular expressions. Report 354, Basser Department of Computer Science, The University of Sydney, 1989."},{"key":"42_CR8","unstructured":"J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Mass., 1979."},{"key":"42_CR9","unstructured":"H. B. Hunt III. The equivalence problem for regular expressions with intersection is not polynomial in tape. Report TR 73-161, Department of Computer Science, Cornell University, 1973."},{"key":"42_CR10","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"N. Immerman. Nondeterministic space is closed under complement. SIAM Journal on Computing, 17:935\u2013938, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"42_CR11","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"},{"key":"42_CR12","first-page":"67","volume-title":"Handbook of Theoretical Computer Science","author":"D. S. Johnson","year":"1990","unstructured":"D. S. Johnson. A catalog of complexity classes. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science: Volume A, Algorithms and Complexity, pages 67\u2013161. MIT Press, Cambridge, MA, 1990."},{"key":"42_CR13","doi-asserted-by":"crossref","unstructured":"D. Kozen. Lower bounds for natural proof systems. In Proceedings of the 18th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u2279), Providence (Rhode Island), pages 254\u2013266. IEEE Computer Society Press, 1977.","DOI":"10.1109\/SFCS.1977.16"},{"key":"42_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/3-540-45127-7_16","volume-title":"On the parallel complexity of tree automata","author":"M. Lohrey","year":"2001","unstructured":"M. Lohrey. On the parallel complexity of tree automata. In A. Middeldorp, editor, Proceedings of the 12th International Conference on Rewrite Techniques and Applications (RTA 2001), Utrecht (Netherlands), number 2051 in Lecture Notes in Computer Science, pages 201\u2013215. Springer, 2001."},{"key":"42_CR15","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1145\/128749.128755","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:430\u2013448, 1992.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"42_CR16","unstructured":"H. Petersen. Decision problems for generalized regular expressions. In Proceedings of the 2nd International Workshop on Descriptional Complexity of Automata, Grammars and Related Structures, London (Ontario), pages 22\u201329, 2000."},{"key":"42_CR17","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0020-0190(79)90073-5","volume":"9","author":"J. M. Robson","year":"1979","unstructured":"J. M. Robson. The emptiness of complement problem for semi extended regular expressions requires cn space. Information Processing Letters, 9:220\u2013222, 1979.","journal-title":"Information Processing Letters"},{"key":"42_CR18","doi-asserted-by":"crossref","unstructured":"L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time. In Proceedings of the 5th ACM Symposium on Theory of Computing (STOC\u201973), Austin (Texas), pages 1\u20139, 1973.","DOI":"10.1145\/800125.804029"},{"key":"42_CR19","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1145\/322077.322083","volume":"25","author":"I. H. Sudborough","year":"1978","unstructured":"I. H. Sudborough. On the tape complexity of deterministic context-free languages. Journal of the Association for Computing Machinery, 25:405\u2013414, 1978.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"42_CR20","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R. Szelepcs\u00e9nyi","year":"1988","unstructured":"R. Szelepcs\u00e9nyi. The method of forced enumeration for nondeterministic automata. Acta Informatica, 26:279\u2013284, 1988.","journal-title":"Acta Informatica"},{"key":"42_CR21","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1145\/363347.363387","volume":"11","author":"K. Thompson","year":"1968","unstructured":"K. Thompson. Regular expression search algorithm. Communications of the Association for Computing Machinery, 11:419\u2013422, 1968.","journal-title":"Communications of the Association for Computing Machinery"},{"key":"42_CR22","unstructured":"K. Wagner and G. Wechsung. Computational Complexity. Mathematics and its Applications. D. Reidel Publishing Company, Dordrecht, 1986."},{"key":"42_CR23","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1007\/3-540-44612-5_65","volume-title":"An automata-based recognition algorithm for semi-extended regular expressions","author":"H. Yamamoto","year":"2000","unstructured":"H. Yamamoto. An automata-based recognition algorithm for semi-extended regular expressions. In M. Nielsen and B. Rovan, editors, Proceedings of the 25th Symposium on Mathematical Foundations of Computer Science (MFCS 2000), Bratislava (Slovakia), number 1893 in Lecture Notes in Computer Science, pages 699\u2013708. Springer, 2000."}],"container-title":["Lecture Notes in Computer Science","STACS 2002"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45841-7_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,21]],"date-time":"2021-08-21T12:41:48Z","timestamp":1629549708000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45841-7_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540432838","9783540458418"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-45841-7_42","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2002]]}}}