The intersection non-emptiness problem, also known as finite automaton intersection problem or the non-emptiness of intersection problem, is a

PSPACE-complete In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length ( polynomial space) and if every other problem that can be solved in polynomial space can ...

decision problem from the field of

automata theory Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματο� ...

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

for many years. Several common non-emptiness problems have been shown to be complete for complexity classes ranging from Deterministic Logspace up to

PSPACE In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. Formal definition If we denote by SPACE(''t''(''n'')), the set of all problems that can b ...

. The intersection non-emptiness

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...

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 In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automa ...

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 In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

algorithm that solves the intersection non-emptiness problem based on the

Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\ ...

construction introduced by

Michael O. Rabin Michael Oser Rabin ( he, מִיכָאֵל עוזר רַבִּין; born September 1, 1931) is an Israeli mathematician and computer scientist and a recipient of the Turing Award. Biography Early life and education Rabin was born in 1931 in ...

and

Dana Scott Dana Stewart Scott (born October 11, 1932) is an American logician who is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, C ...

. 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 Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next d ...

(or

depth-first search Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible alo ...

) 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

in a work by

Dexter Kozen Dexter Campbell Kozen (born December 20, 1951) is an American theoretical computer scientist. He is Joseph Newton Pew, Jr. Professor in Engineering at Cornell University. He received his B.A. from Dartmouth College in 1974 and his PhD in compute ...

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.

References

{{reflist * See an incomplete list of related publications

here Here is an adverb that means "in, on, or at this place". It may also refer to: Software * Here Technologies, a mapping company * Here WeGo (formerly Here Maps), a mobile app and map website by Here Television * Here TV (formerly "here!"), a ...

Deterministic Finite Automaton In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automa ...

Emptiness Problem In theoretical computer science and formal language theory, a formal language is empty if its set of valid sentences is the empty set. The emptiness problem is the question of determining whether a language is empty given some representation of it, ...

List of PSPACE-complete Problems Here are some of the more commonly known problems that are PSPACE-complete when expressed as decision problems. This list is in no way comprehensive. Games and puzzles Generalized versions of: * Amazons * Atomix * Checkers * Dyson Teles ...

PSPACE-complete problems Automata (computation)

Definitions

Algorithm

Hardness

References

Related