Talk:Intersection non-emptiness problem

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

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


Relevant Publications[edit]

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

Conference and Journal Articles[edit]

  • 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).
  • 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 .
  • 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.
  • 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,
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.


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

Blogs or Short Articles[edit]

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