Name
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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.ic.2014.04.001 | latin american symposium on theoretical informatics |
Keywords | DocType | Volume |
oblivious two-way finite automaton,decidability,oblivious computations,two-way deterministic finite automaton,two-way finite automaton,one-way nondeterministic finite automaton,lower bound,two-way finite automata,descriptional complexity | Conference | 237, |
ISSN | Citations | PageRank |
0890-5401 | 1 | 0.35 |
References | Authors | |
30 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Martin Kutrib | 1 | 778 | 89.77 |
| Andreas Malcher | 2 | 204 | 39.40 |
| Giovanni Pighizzini | 3 | 434 | 41.18 |