{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T21:09:59Z","timestamp":1757452199264},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540100034"},{"type":"electronic","value":"9783540393467"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1980]]},"DOI":"10.1007\/3-540-10003-2_74","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:59:39Z","timestamp":1330189179000},"page":"234-245","source":"Crossref","is-referenced-by-count":16,"title":["The complexity of the inequivalence problem for regular expressions with intersection"],"prefix":"10.1007","author":[{"given":"Martin","family":"F\u00fcrer","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,24]]},"reference":[{"key":"21_CR1","unstructured":"Aho, A.V., J.E. Hopcroft and J.D. Ullman, \"The Design and Analysis of Computer Algorithms\", Addison-Wesley, Reading, Mass., 1974."},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"Chandra, A.K. and L.J. Stockmeyer, \"Alternation\", Proc. 17th Annual IEEE Symposium on Foundations of Comp. Sci., 98\u2013108, 1976.","DOI":"10.1109\/SFCS.1976.4"},{"key":"21_CR3","unstructured":"F\u00fcrer, M., \"Non-elementary lower bounds in automata theory\", (in German), Diss. ETH 6122 (Ph.D. Thesis), Z\u00fcrich, 1978."},{"key":"21_CR4","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1145\/322003.322015","volume":"24","author":"J. E. Hopcroft","year":"1977","unstructured":"Hopcroft, J.E., W.J. Paul and L.G. Valiant, \"On Time Versus Space\", Journal of the Association for Computing Machinery 24, 332\u2013337, 1977.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"21_CR5","unstructured":"Hunt III, H.B., \"The equivalence problem for regular expressions with intersection is not polynomial in tape\", Tech. Report TR 73-161, Dept. of Computer Science, Cornell University, 1973."},{"key":"21_CR6","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/S0022-0000(76)80038-4","volume":"12","author":"H. B. Hunt III","year":"1976","unstructured":"Hunt III, H.B., D.J. Rosenkrantz and T.G. Szymanski, \"On the Equivalence, Containment, and Covering Problems for the Regular and Context-Free Languages\", J. of Computer and System Sciences 12, 222\u2013268, 1976.","journal-title":"J. of Computer and System Sciences"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"Kozen, D., \"On parallelism in Turing machines\", Proc. 17th Annual IEEE Symposium on Foundations of Comp. Sci., 89\u201397, 1976.","DOI":"10.1109\/SFCS.1976.20"},{"key":"21_CR8","doi-asserted-by":"crossref","unstructured":"Meyer, A.R. and L.J. Stockmeyer, \"The equivalence problem for regular expressions with squaring requires exponential space\", Proc. 13th Annual IEEE Symposium on Switching and Automata Theory, 125\u2013129, 1972.","DOI":"10.1109\/SWAT.1972.29"},{"key":"21_CR9","doi-asserted-by":"crossref","unstructured":"Rangel, J.L. \"The Equivalence Problem for Regular Expressions over One Letter is Elementary\", 15th Annual Symposium on Switching and Automata Theory, 24\u201327, 1974.","DOI":"10.1109\/SWAT.1974.27"},{"key":"21_CR10","doi-asserted-by":"crossref","unstructured":"Sieferas, J.I., M.J. Fischer and A.R. Meyer, \"Refinements of the Nondeterministic Time and Space Hierarchies\", Proc. 14th Annual IEEE Symposium on Switching and Automata Theory, 130\u2013137, 1973.","DOI":"10.1109\/SWAT.1973.25"},{"key":"21_CR11","unstructured":"Stockmeyer, L.J., \"The complexity of decision problems in automata theory and logic\". Report TR-133, M.I.T., Project MAC, Cambridge, Mass., 1974."},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L.J. and A.R. Meyer, \"Word Problems Requiring Exponential Time: Preliminary Report\", Proc. 5th Annual ACM Symposium on the Theory of Computing, 1\u20139, 1973.","DOI":"10.1145\/800125.804029"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-10003-2_74.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T20:33:10Z","timestamp":1619555590000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-10003-2_74"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1980]]},"ISBN":["9783540100034","9783540393467"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-10003-2_74","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1980]]}}}