Talk:Intersection non-emptiness problem

This is the talk page for the intersection non-emptiness problem. Here you will find additional resources and information.

Relevant Publications

This is an incomplete list of publications on the topic of Intersection Non-Emptiness and related problems.

Conference and Journal Articles

• Dexter Kozen. Lower bounds for natural proof systems. In Proc. 18th Symp. Found. Comput. Sci., pages 254-266. IEEE, October 1977.

• Kasai, T., Iwata, S. Gradually intractable problems and nondeterministic log-space lower bounds. Math. Systems Theory 18, 153–170 (1985). https://doi.org/10.1007/BF01699467

• Saks, M. and R. Statman. "An intersection problem for finite automata." Discret. Appl. Math. 21 (1988): 245-255.

• Lange KJ., Rossmanith P. (1992) The emptiness problem for intersections of regular languages. In: Havel I.M., Koubek V. (eds) Mathematical Foundations of Computer Science 1992. MFCS 1992. Lecture Notes in Computer Science, vol 629. Springer, Berlin, Heidelberg . https://doi.org/10.1007/3-540-55808-X_33

• Margus Veanes. On computational complexity of basic decision problems of finite tree automata. UPMAIL Technical Report 133, 1997.

• Todd Wareham H. (2001) The Parameterized Complexity of Intersection and Composition Operations on Sets of Finite-State Automata. In: Yu S., Păun A. (eds) Implementation and Application of Automata. CIAA 2000. Lecture Notes in Computer Science, vol 2088. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44674-5_26

• G. Karakostas, R. J. Lipton, and A. Viglas. On the complexity of intersecting finite state automata and NL versus NP. Theoretical Computer Science, 302: 257–274, 2003. https://doi.org/10.1016/S0304-3975(02)00830-7

• Marco Cesati, The Turing way to parameterized complexity, Journal of Computer and System Sciences, Volume 67, Issue 4, 2003, Pages 654-685, ISSN 0022-0000, https://doi.org/10.1016/S0022-0000(03)00073-4

• Narad Rampersad, Jeffrey Shallit, Detecting patterns in finite regular and context-free languages, Information Processing Letters, Volume 110, Issue 3, 2010, Pages 108-112, ISSN 0020-0190, https://doi.org/10.1016/j.ipl.2009.11.002

• Wehar M. (2014) Hardness Results for Intersection Non-Emptiness. In: Esparza J., Fraigniaud P., Husfeldt T., Koutsoupias E. (eds) Automata, Languages, and Programming. ICALP 2014. Lecture Notes in Computer Science, vol 8573. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-43951-7_30

• Swernofsky J., Wehar M. (2015) On the Complexity of Intersecting Regular, Context-Free, and Tree Languages. In: Halldórsson M., Iwama K., Kobayashi N., Speckmann B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science, vol 9135. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47666-6_33

• Blondin, M., Krebs, A. & McKenzie, P. The complexity of intersecting finite automata having few final states. comput. complex. 25, 775–814 (2016). https://doi.org/10.1007/s00037-014-0089-9

• Fernau, H.; Krebs, A. Problems on Finite Automata and the Exponential Time Hypothesis. Algorithms 2017, 10, 24. https://doi.org/10.3390/a10010024

• Fleischer, Lukas, and Manfred Kufleitner. "The Intersection Problem for Finite Monoids." 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.

• de Oliveira Oliveira M., Wehar M. (2018) Intersection Non-emptiness and Hardness Within Polynomial Time. In: Hoshi M., Seki S. (eds) Developments in Language Theory. DLT 2018. Lecture Notes in Computer Science, vol 11088. Springer, Cham. https://doi.org/10.1007/978-3-319-98654-8_23

• de Oliveira Oliveira M., Wehar M. (2020) On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection. In: Jonoska N., Savchuk D. (eds) Developments in Language Theory. DLT 2020. Lecture Notes in Computer Science, vol 12086. Springer, Cham. https://doi.org/10.1007/978-3-030-48516-0_6

• Fleischer, Lukas. "The Intersection Problem for Finite Semigroups." International Journal of Foundations of Computer Science 31.06 (2020): 827-842.

• Arrighi, E., Fernau, H., Hoffmann, S., Holzer, M., Jecker, I., Oliveira Oliveira, M., & Wolf, P. (2021). On the Complexity of Intersection Non-emptiness for Star-Free Language Classes. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) (pp. 34:1–34:15). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

Theses

• Michael Blondin. Complexité du problème d'intersection d'automates. B.Sc. honour thesis, Université de Montréal, 2009. http://info.usherbrooke.ca/mblondin/papers/bsc.pdf

• Michael Blondin. Complexité raffinée du problème d'intersection d'automates. M.Sc. thesis, Université de Montréal, 2012. http://info.usherbrooke.ca/mblondin/papers/msc.pdf

• Michael Wehar. Intersection emptiness for finite automata. Honors thesis, Carnegie Mellon University, 2012.

• Michael Wehar. On the complexity of intersection non-emptiness problems. PhD thesis, University at Buffalo, 2016. http://michaelwehar.com/documents/mwehar_dissertation.pdf

• Petra Wolf. Decidability of the Regular Intersection Emptiness Problem. Master thesis, University of Tübingen, 2018. https://www.wolfp.net/_files/ugd/c4121c_7cc6277f7c0a474c86041e9905be9e5a.pdf

• Pim Veraar. Intersection non-emptiness for restricted classes of Deterministic Finite Automata. Bachelor thesis, Utrecht University, 2021. https://studenttheses.uu.nl/bitstream/handle/20.500.12932/1394/ThesisReviewedPimVeraar6409458.pdf

• Petra Wolf. Generalized Synchronization and Intersection Non-Emptiness of Finite-State Automata. PhD thesis, University of Trier, 2021. https://www.wolfp.net/_files/ugd/c4121c_9ba9125273ef4690804ec29d7c7fb6cb.pdf

Blogs or Short Articles

• R. J. Lipton. On the intersection of finite automata. Gödel's Lost Letter and P=NP, August 2009. https://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/

• R. J. Lipton and K. W. Regan. The power of guessing. Gödel's Lost Letter and P=NP, November 2012. https://rjlipton.wordpress.com/2012/11/08/the-power-of-guessing/

• K. W. Regan. Level by level. Gödel's Lost Letterand P=NP, January 2017. https://rjlipton.wordpress.com/2017/01/18/level-by-level/

• M. Wehar (article editor: Daniel Lokshtanov). On the complexity of intersection non-emptiness problems. Parameterized Complexity News. November 2017.