Intersection non-emptiness problem
 | This article, Intersection non-emptiness problem, has recently been created via the Articles for creation process. Please check to see if the reviewer has accidentally left this template after accepting the draft and take appropriate action as necessary.
Reviewer tools: Inform author |
The intersection non-emptiness 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 filed 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 [1].
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[2]. 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 [3]. Since then, many additional hardness results have been shown. Yet, it is still an open problem to determine whether any faster algorithms exist[4].
References
- ^ Galil, Zvi (1976). "Hierarchies of complete problems". Acta Informatica. 6 (1). Springer-Verlag: 77–88. doi:10.1007/BF00263744.
- ^ Rabin, M. O.; Scott, D. (1959). "Finite Automata and Their Decision Problems". IBM J. Res. Dev. 2 (3). IBM Corp.: 114–125. doi:10.1147/rd.32.0114.
- ^ Kozen, D. (1977). Lower bounds for natural proof systems. Proc. 18th Symp. on the Foundations of Computer Science. IEEE. pp. 254–266. doi:10.1109/SFCS.1977.16.
- ^ "On The Intersection of Finite Automata". rjlipton.wordpress.com. Retrieved 15 December 2020.