Intersection non-emptiness problem

The intersection non-emptiness problem, also known as finite automaton intersection problem[1] 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.[2]

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.[3] 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.[1] 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
  1. 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.
  2. Galil, Zvi (1976). "Hierarchies of complete problems". Acta Informatica. Springer-Verlag. 6 (1): 77–88. doi:10.1007/BF00263744. S2CID 26562214.
  3. Rabin, M. O.; Scott, D. (1959). "Finite Automata and Their Decision Problems". IBM J. Res. Dev. IBM Corp. 2 (3): 114–125. doi:10.1147/rd.32.0114.
  4. "On The Intersection of Finite Automata". rjlipton.wordpress.com. Retrieved 15 December 2020.

* See an incomplete list of related publications here.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.