One-way sensing simple multihead finite automata with bounds on the number of times of use of sensing function in accepting computations are studied. It is shown that the languages accepted by one-way sensing simple multihead finite automata with constant sensing function bound satisfy the semilinear property, and that for one-way sensing simple multihead finite automata, m+1 times of the use of sensing function are better than m.

Let SeH{0}(k) [NSeH{0}(k)] denote the class of languages over a one-letter alphabet accepted by two-way sensing deterministic [nondeterministic] k-head finite automata. This paper shows that (i) SeH{0}(2)SeH{0}(3), and (ii) NSeH{0}(2) NSeH{0}(3). This gives an affirmative answer to an open problem in Ref. [3].

This paper introduces a new class of machines called multihead marker finite automata, and investigates how the number of markers affects its accepting power. Let HM{0}(i, j)(NHM{0}(i, j))denote the class of languages over a one-letter alphabet accepted by two-way deterministic (nondeterminstic) i-head finite automata with j markers. We show that HM{0} (i, j) HM{0}(i, j1) and NHM{0}(i, j) NHM{0}(i, j+1) for each i2, j0.