We investigate the descriptional complexity and decidability of obliviousness for two-way finite automata. In particular, we consider the simulation of two-way deterministic finite automata (2DFAs) by oblivious 2DFAs, the simulation of oblivious 2DFAs by sweeping 2DFAs and one-way nondeterministic finite automata (1NFAs) as well as the simulation of sweeping 2DFAs by 1NFAs. In all cases exponential upper and lower bounds on the number of states are obtained for languages over an alphabet with at most four latters. Moreover, it is shown that obliviousness is decidable for 2DFAs.
Oblivious two-way finite automata: decidability and complexity / M. Kutrib, A. Malcher, G. Pighizzini - In: Latin 2012 : theoretical informatics / [a cura di] D. Fernández-Baca. - New York : Springer, 2012. - ISBN 9783642293436. - pp. 518-529 (( Intervento presentato al 10. convegno Latin American Symposium tenutosi a Arequipa nel 2012.
Oblivious two-way finite automata: decidability and complexity
G. PighizziniUltimo
2012
Abstract
We investigate the descriptional complexity and decidability of obliviousness for two-way finite automata. In particular, we consider the simulation of two-way deterministic finite automata (2DFAs) by oblivious 2DFAs, the simulation of oblivious 2DFAs by sweeping 2DFAs and one-way nondeterministic finite automata (1NFAs) as well as the simulation of sweeping 2DFAs by 1NFAs. In all cases exponential upper and lower bounds on the number of states are obtained for languages over an alphabet with at most four latters. Moreover, it is shown that obliviousness is decidable for 2DFAs.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
