Complementation of automata explained

In theoretical computer science and formal language theory, the complementation of an is the problem of computing an automaton that accepts precisely the words rejected by another automaton. Formally, given an automaton A which recognizes a regular language L, we want to compute an automaton that precisely recognizes the words that are not in L, i.e., the complement of L.

Several questions on the complementation operation are studied, such as:

With nondeterministic finite automata

With a nondeterministic finite automaton, the state complexity of the complement automaton may be exponential.[1] Lower bounds are also known in the case of unambiguous automata.[2]

With two-way automata

Complementation has also been studied for two-way automata.[3]

See also

Notes and References

  1. Birget. Jean-Camille. Partial orders on words, minimal elements of regular languages, and state complexity. Theoretical Computer Science. 119. 2. 1993. 267–291. 0304-3975. 10.1016/0304-3975(93)90160-U.
  2. Göös . Mika . Kiefer . Stefan . Yuan . Weiqiang . Lower Bounds for Unambiguous Automata via Communication Complexity . 12 February 2022 . cs.FL . 2109.09155.
  3. Geffert . Viliam . Mereghetti . Carlo . Pighizzini . Giovanni . 2007-08-01 . Complementing two-way finite automata . Information and Computation . 205 . 8 . 1173–1187 . 10.1016/j.ic.2007.01.008 . 0890-5401. free .