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 lower bounds on the number of states are obtained for languages over an alphabet with at most four letters. Finally, a procedure for deciding obliviousness of an arbitrary 2DFA is given and, moreover, the problem is shown to be PSPACE-complete. © 2014 Elsevier Inc. All rights reserved.

Oblivious two-way finite automata : decidability and complexity / M. Kutrib, A. Malcher, G. Pighizzini. - In: INFORMATION AND COMPUTATION. - ISSN 0890-5401. - 237(2014 Oct), pp. 294-302.

Oblivious two-way finite automata : decidability and complexity

G. Pighizzini
2014

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 lower bounds on the number of states are obtained for languages over an alphabet with at most four letters. Finally, a procedure for deciding obliviousness of an arbitrary 2DFA is given and, moreover, the problem is shown to be PSPACE-complete. © 2014 Elsevier Inc. All rights reserved.
Decidability; Descriptional complexity; Oblivious computations; Two-way finite automata
Settore INF/01 - Informatica
ott-2014
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/237468
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact