Complementation of automata
Jump to navigation
Jump to search
In theoretical computer science and formal language theory, the complementation of an automaton[clarify] 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 recognizing precisely the words that are not in L, i.e., the complement of L.
Several questions on the complementation operation are studied, such as:
- Its computational complexity: what is the complexity, given an automaton, of computing an automaton for the complement language?
- Its state complexity: what is the smallest number of states of an automaton recognizing the complement?
With deterministic finite automata
This section needs expansion. You can help by adding to it. (December 2023) |
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]
With Büchi automata
See also
References
- ^ 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.
This article needs additional or more specific categories. (December 2023) |
Categories:
- Articles with short description
- Short description matches Wikidata
- All Wikipedia articles needing clarification
- Wikipedia articles needing clarification from December 2023
- Articles to be expanded from December 2023
- All articles to be expanded
- Articles using small message boxes
- Automata (computation)
- Articles needing additional categories from December 2023