A two-way deterministic finite automaton with r(n) reversals performs ≤ r (n) input head reversals on every n-long input. Let 2D[r(n)] be all families of problems solvable by such automata of size polynomial in the index of the family. Then the reversal hierarchy 2D[0] ⊆ 2D[1] ⊆ 2D[2] ⊆ ⋯ is strict, but 2D[O(1)] = 2D[o(n)]. Moreover, the inner-reversal hierarchy 2D(0) ⊆ 2D(1) ⊆ 2D(2) ⊆ ⋯ , where now the bound is only for reversals strictly between the input end-markers, is also strict.
Reversal hierarchies for small 2DFAs / C. A. Kapoutsis, G. Pighizzini - In: Mathematical foundations of computer science 2012 : 37th international symposium, MFCS 2012, Bratislava, Slovakia, august 27-31, 2012 : proceedings / [a cura di] B. Rovan, V. Sassone, P. Widmayer. - Berlin : Springer, 2012. - ISBN 9783642325885. - pp. 554-565 (( Intervento presentato al 37. convegno International Symposium on Mathematical Foundations of Computer Science tenutosi a Bratislava nel 2012.
Reversal hierarchies for small 2DFAs
G. PighizziniUltimo
2012
Abstract
A two-way deterministic finite automaton with r(n) reversals performs ≤ r (n) input head reversals on every n-long input. Let 2D[r(n)] be all families of problems solvable by such automata of size polynomial in the index of the family. Then the reversal hierarchy 2D[0] ⊆ 2D[1] ⊆ 2D[2] ⊆ ⋯ is strict, but 2D[O(1)] = 2D[o(n)]. Moreover, the inner-reversal hierarchy 2D(0) ⊆ 2D(1) ⊆ 2D(2) ⊆ ⋯ , where now the bound is only for reversals strictly between the input end-markers, is also strict.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
