Reversal-Bounded Acceptors and Intersections of Linear Languages
Ronald V. Book, Maurice Nivat, Michael Stewart Paterson · SIAM Journal on Computing · 1974
A Turing machine whose behavior is restricted so that each read-write head can change its direction only a bounded number of times is reversal-bounded. Here we consider nondeterministic multitape acceptors which are both reversal-bounded and also operate in linear time. Our main result shows that such an acceptor need have only three pushdown stores as auxiliary storage, each pushdown store need make only one reversal, and the acceptor can operate in real time.