We study the relationship between the sizes of two-way finite automata accepting a language and its complement. In the deterministic case, by adapting Sipser's method, 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 the 2nfa halting. This allows the simulation of unary 2nfa's by probabilistic Las Vegas two-way automata with O(n8) states.
Complementing two-way finite automata / V. Geffert, C. Mereghetti, G. Pighizzini - In: Developments in language theory / [a cura di] C. De Felice, A. Restivo. - Berlin : Springer, 2005. - ISBN 9783540265467. - pp. 260-271 (( Intervento presentato al 9. convegno International Conference Developments in Language Theory tenutosi a Palermo nel 2005.
Titolo: | Complementing two-way finite automata |
Autori: | MEREGHETTI, CARLO (Secondo) PIGHIZZINI, GIOVANNI (Ultimo) |
Parole Chiave: | Automata and formal languages; Descriptional complexity |
Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
Data di pubblicazione: | 2005 |
Enti collegati al convegno: | European Association for Theoretical Computer Science |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1007/11505877_23 |
Tipologia: | Book Part (author) |
Appare nelle tipologie: | 03 - Contributo in volume |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
pubblicato.pdf | Publisher's version/PDF | Administrator Richiedi una copia |