{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T03:17:45Z","timestamp":1773717465409,"version":"3.50.1"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030485153","type":"print"},{"value":"9783030485160","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","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":[[2020]]},"DOI":"10.1007\/978-3-030-48516-0_6","type":"book-chapter","created":{"date-parts":[[2020,5,25]],"date-time":"2020-05-25T23:04:30Z","timestamp":1590447870000},"page":"69-82","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection"],"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":[[2020,5,26]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Hansen, T.D., Williams, V.V., Williams, R.: Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. In: Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC 2016), pp. 375\u2013388. ACM (2016)","DOI":"10.1145\/2897518.2897653"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Abboud, A., Williams, V.V.: Popular conjectures imply strong lower bounds for dynamic problems. In: Proceedings of the 55th Annual Symposium on Foundations of Computer Science (FOCS 2014), pp. 434\u2013443. IEEE (2014)","DOI":"10.1109\/FOCS.2014.53"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Backurs, A., Indyk, P.: Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In: Proceedigs of the 47th Annual ACM Symposium on Theory of Computing (STOC 2015), pp. 51\u201358. ACM (2015)","DOI":"10.1145\/2746539.2746612"},{"key":"6_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-662-43948-7_14","volume-title":"Automata, Languages, and Programming","author":"E Ben-Sasson","year":"2014","unstructured":"Ben-Sasson, E., Viola, E.: Short PCPs with projection queries. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 163\u2013173. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43948-7_14"},{"issue":"4","key":"6_CR5","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1137\/0206054","volume":"6","author":"A Borodin","year":"1977","unstructured":"Borodin, A.: On relating time and space to size and depth. SIAM J. Comput. 6(4), 733\u2013744 (1977)","journal-title":"SIAM J. Comput."},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Buss, S.R.: Algorithms for boolean formula evaluation and for tree contraction. In: Arithmetic, Proof Theory and Computational Complexity, pp. 96\u2013115. Oxford University Press (1993)","DOI":"10.1093\/oso\/9780198536901.003.0005"},{"key":"6_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-11269-0_6","volume-title":"Parameterized and Exact Computation","author":"C Calabro","year":"2009","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: The complexity of satisfiability of small depth circuits. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 75\u201385. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-11269-0_6"},{"issue":"2","key":"6_CR8","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/j.ic.2005.05.001","volume":"201","author":"J Chen","year":"2005","unstructured":"Chen, J., et al.: Tight lower bounds for certain parameterized NP-hard problems. Inf. Comput. 201(2), 216\u2013231 (2005)","journal-title":"Inf. Comput."},{"key":"6_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"975","DOI":"10.1007\/11533719_98","volume-title":"Computing and Combinatorics","author":"J Chen","year":"2005","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: W-Hardness under linear FPT-reductions: structural properties and further applications. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 975\u2013984. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11533719_98"},{"issue":"8","key":"6_CR10","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci. 72(8), 1346\u20131367 (2006)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"6_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2635812","volume":"10","author":"H Dell","year":"2014","unstructured":"Dell, H., Husfeldt, T., Marx, D., Taslaman, N., Wahl\u00e9n, M.: Exponential time complexity of the permanent and the Tutte polynomial. ACM Trans. Algorithms (TALG) 10(4), 1\u201332 (2014)","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"1","key":"6_CR12","doi-asserted-by":"publisher","first-page":"24","DOI":"10.3390\/a10010024","volume":"10","author":"H Fernau","year":"2017","unstructured":"Fernau, H., Krebs, A.: Problems on finite automata and the exponential time hypothesis. Algorithms 10(1), 24 (2017)","journal-title":"Algorithms"},{"issue":"1","key":"6_CR13","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M Furst","year":"1984","unstructured":"Furst, M., Saxe, J.B., Sipser, M.: Parity, circuits, and the polynomial-time hierarchy. Math. Syst. Theory 17(1), 13\u201327 (1984)","journal-title":"Math. Syst. Theory"},{"key":"6_CR14","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$-SAT. J. Comput. Syst. Sci. 62, 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR15","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63, 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"6_CR16","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":"6_CR17","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. Theory 18(1), 153\u2013170 (1985). https:\/\/doi.org\/10.1007\/BF01699467","journal-title":"Math. Syst. Theory"},{"key":"6_CR18","doi-asserted-by":"crossref","unstructured":"Kozen, D.: Lower bounds for natural proof systems. In: Proceedings of the 8th Annual Symposium on Foundations of Computer Science (FOCS 1977), vol. 77, pp. 254\u2013266 (1977)","DOI":"10.1109\/SFCS.1977.16"},{"key":"6_CR19","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). https:\/\/doi.org\/10.1007\/3-540-55808-X_33"},{"key":"6_CR20","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Slightly superexponential parameterized problems. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), pp. 760\u2013776 (2011)","DOI":"10.1137\/1.9781611973082.60"},{"issue":"4","key":"6_CR21","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1145\/322033.322037","volume":"24","author":"N Lynch","year":"1977","unstructured":"Lynch, N.: Log space recognition and translation of parenthesis languages. J. ACM 24(4), 583\u2013590 (1977)","journal-title":"J. ACM"},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"Marx, D.: On the optimality of planar and geometric approximation schemes. In: Proceedings of the 48th Annual Symposium on Foundations of Computer Science (FOCS 2007), pp. 338\u2013348. IEEE (2007)","DOI":"10.1109\/FOCS.2007.26"},{"key":"6_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/978-3-319-98654-8_23","volume-title":"Developments in Language Theory","author":"M de Oliveira Oliveira","year":"2018","unstructured":"de Oliveira Oliveira, M., Wehar, M.: Intersection non-emptiness and hardness within polynomial time. In: Hoshi, M., Seki, S. (eds.) DLT 2018. LNCS, vol. 11088, pp. 282\u2013290. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-98654-8_23"},{"key":"6_CR24","doi-asserted-by":"crossref","unstructured":"P\u0103tra\u015fcu, M., Williams, R.: On the possibility of faster SAT algorithms. In: Proceedings of the 21st Annual Symposium on Discrete Algorithms (SODA 2010), pp. 1065\u20131075. SIAM (2010)","DOI":"10.1137\/1.9781611973075.86"},{"issue":"1","key":"6_CR25","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/S0022-0000(77)80042-1","volume":"14","author":"JI Seiferas","year":"1977","unstructured":"Seiferas, J.I.: Relating refined space complexity classes. J. Comput. Syst. Sci. 14(1), 100\u2013129 (1977)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR26","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). https:\/\/doi.org\/10.1007\/3-540-44674-5_26"},{"key":"6_CR27","doi-asserted-by":"crossref","unstructured":"Wang, J.R., Williams, R.R.: Exact algorithms and strong exponential time hypothesis. In: Encyclopedia of Algorithms, pp. 657\u2013661 (2016)","DOI":"10.1007\/978-1-4939-2864-4_519"},{"key":"6_CR28","unstructured":"Wehar, M.: Intersection emptiness for finite automata. Honors thesis, Carnegie Mellon University (2012)"},{"key":"6_CR29","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). https:\/\/doi.org\/10.1007\/978-3-662-43951-7_30"},{"key":"6_CR30","unstructured":"Wehar, M.: On the complexity of intersection non-emptiness problems. Ph.D. thesis, University at Buffalo (2016)"},{"key":"6_CR31","doi-asserted-by":"crossref","unstructured":"Williams, R.: Non-uniform ACC circuit lower bounds. In: IEEE 26th Annual Conference on Computational Complexity (CCC 2011), pp. 115\u2013125, June 2011","DOI":"10.1109\/CCC.2011.36"},{"issue":"3","key":"6_CR32","doi-asserted-by":"publisher","first-page":"1218","DOI":"10.1137\/10080703X","volume":"42","author":"R Williams","year":"2013","unstructured":"Williams, R.: Improving exhaustive search implies superpolynomial lower bounds. SIAM J. Comput. 42(3), 1218\u20131244 (2013)","journal-title":"SIAM J. Comput."},{"key":"6_CR33","unstructured":"Williams, V.V.: Hardness of easy problems: basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In: Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), LIPICs, vol. 43, pp. 17\u201329 (2015)"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-48516-0_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,6]],"date-time":"2024-08-06T09:55:34Z","timestamp":1722938134000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-48516-0_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030485153","9783030485160"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-48516-0_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"26 May 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"DLT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Developments in Language Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Tampa, FL","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 May 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 May 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dlt2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/knot.math.usf.edu\/dlt2020\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"38","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"24","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"63% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.7","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"1.48","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Conference cancelled due to the COVID-19 pandemic","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}