Two-Way Automata and Bounded Languages

We prove that, at the cost of a polynomial increase of the number of states, each two-way nondeterministic automaton accepting a letter-bounded language can be simulated by an equivalent machine of the same type, where nondeterministic transitions and inversions of head movement are possible only when the head visits one of the tape end-markers. This result has several consequences. Two of them are related to the open question posed by Sakoda and Sipser concerning the state cost of the conversions of one-way and two-way nondeterministic automata into equivalent two-way deterministic finite automata: in the letter-bounded case, the cost of the latter conversion is bounded by a subexponential function, while that of the former is polynomial in the number of states of the given machine. Other consequences are related to the cost of complementing two-way automata, to make them halting, self-verifying or unambiguous. Connections with the question of the power of the nondeterminism in logarithmic space bounded complexity classes are also stated.