On space bounded Turing machines with a constant number of input head inversions

In this work we study classes of languages accepted by finitely ambiguous space bounded automata which are allowed to have an arbitrary constant number of input head inversions. In particular we show that: a) 1–way deterministic log–space bounded Turing machines are strictly less powerful than deterministic log–space bounded Turing machines with one input head inversion and, more generally, than 1–way unambiguous log–space bounded Turing machines, b) nondeterministic Turing machines with an arbitrary constant number of input head inversions can be simulated by 1–way nondeterministic Turing machines having the same space complexity and the same ambiguity degree. As a consequence of (b), we obtain that the census and ranking problems for the languages accepted in logarithmic space by finitely ambiguous Turing machines with an arbitrary constant number of input head inversions are NC1–reducible to the problem of computing the determinant of a n ⇥ n matrix of n–bit integers and hence solvable by a log–space uniform family of boolean circuits of polynomial size and depth O(log2 n).