@article{GEFFERT20071173,
    Abstract = {We study the relationship between the sizes of two-way finite automata accepting a language and its complement. In the deterministic case, for a given automaton (2dfa) with n states, we build an automaton accepting the complement with at most 4n states, independently of the size of the input alphabet. Actually, we show a stronger result, by presenting an equivalent 4n-state 2dfa that always halts. For the nondeterministic case, using a variant of inductive counting, we show that the complement of a unary language, accepted by an n-state two-way automaton (2nfa), can be accepted by an O(n8)-state 2nfa. Here we also make 2nfa's halting. This allows the simulation of unary 2nfa's by probabilistic Las Vegas two-way automata with O(n8) states.},
    Author = {Geffert, Viliam and Mereghetti, Carlo and Pighizzini, Giovanni},
    File = {Complementing two-way finite automata - 82144434.pdf},
    ISSN = {0890-5401},
    Journal = {Information and Computation},
    Keywords = {Finite state automata, Formal languages, Descriptional complexity},
    Number = {8},
    Pages = {1173-1187},
    Title = {Complementing two-way finite automata},
    URL = {https://www.sciencedirect.com/science/article/pii/S0890540107000053},
    Volume = {205},
    Year = {2007},
    bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0890540107000053},
    bdsk-url-2 = {https://doi.org/10.1016/j.ic.2007.01.008},
    date-added = {2023-01-26 11:23:20 +0100},
    date-modified = {2023-01-26 11:23:20 +0100},
    doi = {10.1016/j.ic.2007.01.008}
}

@article{GEFFERT20071173, Abstract = {We study the relationship between the sizes of two-way finite automata accepting a language and its complement. In the deterministic case, for a given automaton (2dfa) with n states, we build an automaton accepting the complement with at most 4n states, independently of the size of the input alphabet. Actually, we show a stronger result, by presenting an equivalent 4n-state 2dfa that always halts. For the nondeterministic case, using a variant of inductive counting, we show that the complement of a unary language, accepted by an n-state two-way automaton (2nfa), can be accepted by an O(n8)-state 2nfa. Here we also make 2nfa's halting. This allows the simulation of unary 2nfa's by probabilistic Las Vegas two-way automata with O(n8) states.}, Author = {Geffert, Viliam and Mereghetti, Carlo and Pighizzini, Giovanni}, File = {Complementing two-way finite automata - 82144434.pdf}, ISSN = {0890-5401}, Journal = {Information and Computation}, Keywords = {Finite state automata, Formal languages, Descriptional complexity}, Number = {8}, Pages = {1173-1187}, Title = {Complementing two-way finite automata}, URL = {https://www.sciencedirect.com/science/article/pii/S0890540107000053}, Volume = {205}, Year = {2007}, bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0890540107000053}, bdsk-url-2 = {https://doi.org/10.1016/j.ic.2007.01.008}, date-added = {2023-01-26 11:23:20 +0100}, date-modified = {2023-01-26 11:23:20 +0100}, doi = {10.1016/j.ic.2007.01.008} }