The intersection non-emptiness problem, also known as finite automaton intersection problem or the non-emptiness of intersection problem, is a PSPACE-complete decision problem from the field of automata theory. The problem asks if a list of deterministic finite automata has nonempty intersection.
A non-emptiness decision problem is defined (for a particular type of automaton) as follows: given an automaton as input, the goal is to determine whether or not the automaton's language is non-empty, i.e., 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.
The intersection non-emptiness decision problem is similar, but defined on a list of automata, instead of just one. In particular, for the purposes of this article: given a list of deterministic finite automata as input, determine whether or not their associated regular languages have a non-empty intersection; i.e., determine if there exists a string that is accepted by every automaton in the list.
There is an exponential time algorithm that solves the intersection non-emptiness problem based on the Cartesian product construction introduced by Michael O. Rabin and Dana Scott. The idea is that all of the automata together form a "product automaton" whose states consist of tuples of states in the list of automata; a string is accepted by the product automaton if and only if it is accepted by every automaton in the list. Therefore, a breadth-first search (or depth-first search) within the product automaton's state space 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 every automaton in the list.
For this construction, the product automaton does not need to be explicitly constructed; the automata provide sufficient information so that transitions can be determined as needed.
The intersection non-emptiness problem was shown to be PSPACE-complete by Dexter Kozen in 1977. It is an open problem whether any faster algorithms exist.