{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,9]],"date-time":"2025-05-09T05:52:27Z","timestamp":1746769947589,"version":"3.40.3"},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319986531"},{"type":"electronic","value":"9783319986548"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-98654-8_23","type":"book-chapter","created":{"date-parts":[[2018,8,4]],"date-time":"2018-08-04T19:43:57Z","timestamp":1533411837000},"page":"282-290","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Intersection Non-emptiness and Hardness Within Polynomial Time"],"prefix":"10.1007","author":[{"given":"Mateus","family":"de Oliveira Oliveira","sequence":"first","affiliation":[]},{"given":"Michael","family":"Wehar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,5]]},"reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Williams, V.V.: Popular conjectures imply strong lower bounds for dynamic problems. In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), pp. 434\u2013443. IEEE (2014)","DOI":"10.1109\/FOCS.2014.53"},{"key":"23_CR2","doi-asserted-by":"crossref","unstructured":"Backurs, A., Indyk, P.: Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC 2015, New York, NY, USA, pp. 51\u201358. ACM (2015)","DOI":"10.1145\/2746539.2746612"},{"key":"23_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/978-3-319-40946-7_8","volume-title":"Implementation and Application of Automata","author":"H Fernau","year":"2016","unstructured":"Fernau, H., Krebs, A.: Problems on finite automata and the exponential time hypothesis. In: Han, Y.-S., Salomaa, K. (eds.) CIAA 2016. LNCS, vol. 9705, pp. 89\u2013100. Springer, Cham (2016). \n                    https:\/\/doi.org\/10.1007\/978-3-319-40946-7_8"},{"issue":"3","key":"23_CR4","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0925-7721(95)00022-2","volume":"5","author":"A Gajentaan","year":"1995","unstructured":"Gajentaan, A., Overmars, M.H.: On a class of \n                    \n                      \n                    \n                    $$O(n^2)$$\n                   problems in computational geometry. Comput. Geom. 5(3), 165\u2013185 (1995)","journal-title":"Comput. Geom."},{"issue":"2","key":"23_CR5","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1006\/jcom.1998.0476","volume":"14","author":"X Huang","year":"1998","unstructured":"Huang, X., Pan, V.Y.: Fast rectangular matrix multiplication and applications. J. Complex. 14(2), 257\u2013299 (1998)","journal-title":"J. Complex."},{"issue":"1","key":"23_CR6","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. Theor. Comput. Sci. 302(1), 257\u2013274 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"23_CR7","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/BF01699467","volume":"18","author":"T Kasai","year":"1985","unstructured":"Kasai, T., Iwata, S.: Gradually intractable problems and nondeterministic log-space lower bounds. Math. Syst. Theor. 18(1), 153\u2013170 (1985)","journal-title":"Math. Syst. Theor."},{"key":"23_CR8","first-page":"254","volume":"77","author":"D Kozen","year":"1977","unstructured":"Kozen, D.: Lower bounds for natural proof systems. FOCS 77, 254\u2013266 (1977)","journal-title":"FOCS"},{"key":"23_CR9","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. 629, pp. 346\u2013354. Springer, Heidelberg (1992). \n                    https:\/\/doi.org\/10.1007\/3-540-55808-X_33"},{"key":"23_CR10","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"MO Rabin","year":"1959","unstructured":"Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev. 3, 114\u2013125 (1959)","journal-title":"IBM J. Res. Dev."},{"key":"23_CR11","unstructured":"Schneider, S.: Fine-grained connections between exponential and polynomial time. Ph.D. thesis, University of California, San Diego (2017)"},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time: preliminary report. In: Proceedings of the 5th Annual ACM Symposium on Theory of Computing, 30 April \u2013 2 May 1973, Austin, Texas, USA, pp. 1\u20139 (1973)","DOI":"10.1145\/800125.804029"},{"key":"23_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/3-540-44674-5_26","volume-title":"Implementation and Application of Automata","author":"H Todd Wareham","year":"2001","unstructured":"Todd Wareham, H.: The parameterized complexity of intersection and composition operations on sets of finite-state automata. In: Yu, S., P\u0103un, A. (eds.) CIAA 2000. LNCS, vol. 2088, pp. 302\u2013310. Springer, Heidelberg (2001). \n                    https:\/\/doi.org\/10.1007\/3-540-44674-5_26"},{"key":"23_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/978-3-662-43951-7_30","volume-title":"Automata, Languages, and Programming","author":"M Wehar","year":"2014","unstructured":"Wehar, M.: Hardness results for intersection non-emptiness. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8573, pp. 354\u2013362. Springer, Heidelberg (2014). \n                    https:\/\/doi.org\/10.1007\/978-3-662-43951-7_30"},{"key":"23_CR15","unstructured":"Wehar, M.: On the complexity of intersection non-emptiness problems. Ph.D. thesis, University at Buffalo (2016)"},{"issue":"2","key":"23_CR16","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.tcs.2005.09.023","volume":"348","author":"R Williams","year":"2005","unstructured":"Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348(2), 357\u2013365 (2005). Automata, Languages and Programming: Algorithms and Complexity (ICALP-A 2004)","journal-title":"Theor. Comput. Sci."},{"key":"23_CR17","doi-asserted-by":"crossref","unstructured":"Williams, V.V.: Multiplying matrices faster than coppersmith-winograd. In: Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC 2012, pp. 887\u2013898. ACM, New York (2012)","DOI":"10.1145\/2213977.2214056"},{"key":"23_CR18","unstructured":"Williams, V.V.: Hardness of easy problems: basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In: Husfeldt, T., Kanj, I. (eds.) 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), Volume 43 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 17\u201329. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl (2015)"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-98654-8_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,9,2]],"date-time":"2018-09-02T19:13:49Z","timestamp":1535915629000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-98654-8_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319986531","9783319986548"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-98654-8_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]}}}