{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,9]],"date-time":"2025-05-09T05:51:23Z","timestamp":1746769883541},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439500"},{"type":"electronic","value":"9783662439517"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43951-7_30","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T08:37:49Z","timestamp":1402475869000},"page":"354-362","source":"Crossref","is-referenced-by-count":8,"title":["Hardness Results for Intersection Non-Emptiness"],"prefix":"10.1007","author":[{"given":"Michael","family":"Wehar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"30_CR1","unstructured":"Blondin, M., Krebs, A., McKenzie, P.: The complexity of intersecting finite automata having few final states. In: Computational Complexity, CC (to appear, 2014)"},{"key":"30_CR2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804106","volume-title":"Computational Complexity: A Conceptual Perspective","author":"O. Goldreich","year":"2008","unstructured":"Goldreich, O.: Computational Complexity: A Conceptual Perspective. Cambridge University Press, New York (2008)"},{"key":"30_CR3","doi-asserted-by":"crossref","unstructured":"Jones, N.D., Lien, Y.E., Laaser, W.T.: New problems complete for nondeterministic log space. Mathematical Systems Theory 10 (1976)","DOI":"10.1007\/BF01683259"},{"key":"30_CR4","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0304-3975(02)00830-7","volume":"302","author":"G. Karakostas","year":"2003","unstructured":"Karakostas, G., Lipton, R.J., Viglas, A.: On the complexity of intersecting finite state automata and NL versus NP. Theoretical Computer Science\u00a0302, 257\u2013274 (2003)","journal-title":"Theoretical Computer Science"},{"key":"30_CR5","doi-asserted-by":"crossref","unstructured":"Kozen, D.: Lower bounds for natural proof systems. In: Proc. 18th Symp. on the Foundations of Computer Science, pp. 254\u2013266 (1977)","DOI":"10.1109\/SFCS.1977.16"},{"key":"30_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1007\/3-540-55808-X_33","volume-title":"Mathematical Foundations of Computer Science 1992","author":"K.-J. Lange","year":"1992","unstructured":"Lange, K.-J., Rossmanith, P.: The emptiness problem for intersections of regular languages. In: Havel, I.M., Koubek, V. (eds.) MFCS 1992. LNCS, vol.\u00a0629, pp. 346\u2013354. Springer, Heidelberg (1992)"},{"key":"30_CR7","doi-asserted-by":"crossref","unstructured":"Lipton, R.J.: On the intersection of finite automata. G\u00f6del\u2019s Lost Letter and P=NP (August 2009)","DOI":"10.1007\/978-1-4419-7155-5_31"},{"key":"30_CR8","unstructured":"Lipton, R.J., Regan, K.W.: The power of guessing. G\u00f6del\u2019s Lost Letter and P=NP (November 2012)"},{"key":"30_CR9","doi-asserted-by":"crossref","unstructured":"Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM Journal (1959)","DOI":"10.1147\/rd.32.0114"},{"key":"30_CR10","doi-asserted-by":"crossref","unstructured":"Rampersad, N., Shallit, J.: Detecting patterns in finite regular and context-free languages. Information Processing Letters\u00a0110 (2010)","DOI":"10.1016\/j.ipl.2009.11.002"},{"key":"30_CR11","unstructured":"Veanes, M.: On computational complexity of basic decision problems of finite tree automata. UPMAIL Technical Report 133 (1997)"},{"key":"30_CR12","unstructured":"Wehar, M.: Intersection emptiness for finite automata. Honors thesis, Carnegie Mellon University (2012)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43951-7_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T02:31:23Z","timestamp":1558924283000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43951-7_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439500","9783662439517"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43951-7_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}