Complementation of automata

In theoretical computer science and formal language theory, complementation is a computational problem that applies to automata. An automaton is an abstract machine that verifies a property on its inputs, and either accepts it (if the property is verified) or rejects it (if the property is not verified). The complement of an automaton is another automaton that accepts precisely what the other one rejects, and vice-versa. More precisely, an automaton A defines a formal language L formed of the inputs that A accepts, and complementation is the problem of computing a "complement" 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 in automata theory research, such as:

Expressiveness: Do complement automata always exist? The answer depends on the automaton formalism used to represent the input automaton A and the complement automaton. For instance, if A is a finite automaton, then a complement automaton for A as a finite automaton always exists, because the regular languages are closed under complementation. In contrast, there are pushdown automata that do not have a complement pushdown automaton.^[1]
Decidability: Is there an algorithm that takes as input an automaton A and perfoms automaton complementation (i.e., builds the complement automaton), or can the task be undecidable? Again, the answer to this question depends on the automaton class used to represent the input and output of the complementation problem.^{[example needed]}
Computational complexity: If complement automata exist, and if computing them is decidable, then we can ask what is the computational complexity of the complementation operation: given an automaton, how efficiently can we compute a complement automaton, e.g., in time complexity?
State complexity: When complement automata exist, what is the smallest number of states that they require, as a function of the number of states of the input automaton?

With deterministic finite automata

With nondeterministic finite automata

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

With two-way automata

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

With Büchi automata

References

^ John E. Hopcroft and Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Reading/MA: Addison-Wesley. ISBN 0-201-02988-X. p.134-135, Theorem 6.4
^ Birget, Jean-Camille (1993). "Partial orders on words, minimal elements of regular languages, and state complexity". Theoretical Computer Science. 119 (2): 267–291. doi:10.1016/0304-3975(93)90160-U. ISSN 0304-3975.
^ Göös, Mika; Kiefer, Stefan; Yuan, Weiqiang (12 February 2022). "Lower Bounds for Unambiguous Automata via Communication Complexity". arXiv:2109.09155 [cs.FL].
^ Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (2007-08-01). "Complementing two-way finite automata". Information and Computation. 205 (8): 1173–1187. doi:10.1016/j.ic.2007.01.008. ISSN 0890-5401.

[1] John E. Hopcroft and Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Reading/MA: Addison-Wesley. ISBN 0-201-02988-X. p.134-135, Theorem 6.4

[Birget1993b-2] Birget, Jean-Camille (1993). "Partial orders on words, minimal elements of regular languages, and state complexity". Theoretical Computer Science. 119 (2): 267–291. doi:10.1016/0304-3975(93)90160-U. ISSN 0304-3975.

[GoosKieferYuan2022-3] Göös, Mika; Kiefer, Stefan; Yuan, Weiqiang (12 February 2022). "Lower Bounds for Unambiguous Automata via Communication Complexity". arXiv:2109.09155 [cs.FL].

[4] Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (2007-08-01). "Complementing two-way finite automata". Information and Computation. 205 (8): 1173–1187. doi:10.1016/j.ic.2007.01.008. ISSN 0890-5401.

[1]

[2]

[3]

[4]