Intersection non-emptiness problem
The intersection non-emptiness problem, also known as finite automaton intersection problem{{cite conference
| last = Kozen
| first = D.
| title = Lower bounds for natural proof systems
| pages = 254–266
| publisher = IEEE
| conference = Proc. 18th Symp. on the Foundations of Computer Science
| year = 1977
| url = https://doi.org/10.1109/SFCS.1977.16
| doi = 10.1109/SFCS.1977.16
}} or the non-emptiness of intersection problem, is a PSPACE-complete decision problem from the field of automata theory.
Definitions
A non-emptiness decision problem is defined as follows. Given an automaton as input, the goal is to determine whether or not the automaton's language is non-empty. In other words, the goal is to determine if there exists a string that is accepted by the automaton.
Non-emptiness problems have been studied in the field of automata theory for many years. Several common non-emptiness problems have been shown to be complete for complexity classes ranging from Deterministic Logspace up to PSPACE.{{cite journal
| last = Galil
| first = Zvi
| title = Hierarchies of complete problems
| pages = 77–88
| volume = 6
| issue = 1
| publisher = Springer-Verlag
| journal = Acta Informatica
| year = 1976
| url = https://doi.org/10.1007/BF00263744
| doi = 10.1007/BF00263744
| s2cid = 26562214
}}
The intersection non-emptiness decision problem is concerned with whether the intersection of given languages is non-empty. In particular, the intersection non-emptiness problem is defined as follows. Given a list of deterministic finite automata as input, the goal is to determine whether or not their associated regular languages have a non-empty intersection. In other, the goal is to determine if there exists a string that is accepted by all of the automata in the list.
Algorithm
There is a common exponential time algorithm that solves the intersection non-emptiness problem based on the Cartesian product construction introduced by Michael O. Rabin and Dana Scott.{{cite journal
| last1 = Rabin
| first1 = M. O.
| last2 = Scott
| first2 = D.
| title = Finite Automata and Their Decision Problems
| pages = 114–125
| volume = 2
| issue = 3
| publisher = IBM Corp.
| journal = IBM J. Res. Dev.
| year = 1959
| url = https://doi.org/10.1147/rd.32.0114
| doi = 10.1147/rd.32.0114
}} The idea is that all of the automata together form a product automaton such that a string is accepted by all of the automata if and only if it is accepted by the product automaton. Therefore, a breadth-first search (or depth-first search) within the product automaton's state diagram will determine whether there exists a path from the product start state to one of the product final states. Whether or not such a path exists is equivalent to determining if any string is accepted by all of the automata in the list.
Note: The product automaton does not need to be fully constructed. The automata together provide sufficient information so that transitions can be determined as needed.
Hardness
The intersection non-emptiness problem was shown to be PSPACE-complete in a work by Dexter Kozen in 1977. Since then, many additional hardness results have been shown. Yet, it is still an open problem to determine whether any faster algorithms exist.{{cite web
| url = https://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/
| title = On The Intersection of Finite Automata
| website = rjlipton.wordpress.com
| accessdate = 15 December 2020
}}
References
{{reflist}}