The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
This is the talk page for the intersection non-emptiness problem. Here you will find additional resources and information.
This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
This article was reviewed by member(s) of WikiProject Articles for creation. The project works to allow users to contribute quality articles and media files to the encyclopedia and track their progress as they are developed. To participate, please visit the project page for more information.Articles for creationWikipedia:WikiProject Articles for creationTemplate:WikiProject Articles for creationAfC
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.
