<p>A bit overkill, but:
<a href="http://arxiv.org/abs/cs/9906007">this paper</a> shows (among other nice things) that non-deterministic Hennie transducers realize exactly the class of non-deterministic MSO-definable transductions. The latter have regular domains.</p>

CC BY-SA 3.0
2016-01-26T11:16:53.457Z
2016-01-26T11:16:53.457Z
Boson
<p>Do bounded-visit nondeterministic linear bounded automata recognize only regular languages?</p>

<p>By a nondeterministic linear bounded automaton (nLBA) I mean a single-tape nondeterministic Turing machine where the input comes "padded" with endmarkers on both ends which can never be overwritten, and so that the head can never move out of the input region, "outside" the endmarkers.</p>

<p>The LBA is bounded-visit if there is a number $k$ such that <em>all</em> runs on <em>all</em> inputs terminate and visit every cell of the tape at most $k$ times.</p>

<p>Does such a machine recognize only regular languages? <a href="http://www.sciencedirect.com/science/article/pii/S0019995865903992" rel="nofollow">Hennie's result</a> seems to say this only for deterministic machines, if I'm reading it right. Does the result hold for nondeterministic machines too? If yes, a reference would be appreciated.</p>

<automata-theory><turing-machines><regular-language><space-bounded>
Do bounded-visit nondeterministic linear bounded automata recognize only regular languages?
Prateek
# Do bounded-visit nondeterministic linear bounded automata recognize only regular languages?

(Asked by: username_0 on 2016-01-26)

Do bounded-visit nondeterministic linear bounded automata recognize only regular languages?

By a nondeterministic linear bounded automaton (nLBA) I mean a single-tape nondeterministic Turing machine where the input comes "padded" with endmarkers on both ends which can never be overwritten, and so that the head can never move out of the input region, "outside" the endmarkers.

The LBA is bounded-visit if there is a number $k$ such that *all* runs on *all* inputs terminate and visit every cell of the tape at most $k$ times.

Does such a machine recognize only regular languages? [Hennie's result](http://www.sciencedirect.com/science/article/pii/S0019995865903992) seems to say this only for deterministic machines, if I'm reading it right. Does the result hold for nondeterministic machines too? If yes, a reference would be appreciated.

**Tags:** automata-theory, turing-machines, regular-language, space-bounded


---

## 1 answers

### Answer by username_1 on 2016-01-26. Score: 7 | Accepted answer

A bit overkill, but:
[this paper](http://arxiv.org/abs/cs/9906007) shows (among other nice things) that non-deterministic Hennie transducers realize exactly the class of non-deterministic MSO-definable transductions. The latter have regular domains.


---

