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\u2013way deterministic log\u2013space bounded Turing machines are strictly less powerful than deterministic log\u2013space bounded Turing machines with one input head inversion and, more generally, than 1\u2013way unambiguous log\u2013space bounded Turing machines, b) nondeterministic Turing machines with an arbitrary constant number of input head inversions can be simulated by 1\u2013way 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\u2013reducible to the problem of computing the determinant of a n \u21e5 n matrix of n\u2013bit integers and hence solvable by a log\u2013space uniform family of boolean circuits of polynomial size and depth O(log2 n)