Computational power of one-way multihead finite automata

1. Chrobak M., Hierarchies of one-way multihead automata languages, Theoretical Comp. Sci. 48 (1986) 153–181, also in Proc. ICALP'85, Lecture Notes in Comp. Sci. 194 (Springer, Berlin, 1985) 101–110.

   Article  Google Scholar 

2. Ibarra O.H. and Kim C.E., On 3-head versus 2-head finite automata, Acta Informatica 4 (1975) 173–200.

   Article  Google Scholar 

3. Kutyłowski M., One-way multihead finite automata, to appear in Theoretical Comp. Sci.

   Google Scholar 

4. Kutyłowski M., One-way multihead finite automata and 2-bounded languages, submitted for publication.

   Google Scholar 

5. Kutyłowski M., Remarks on sorting and one-way multihead finite automata, to appear in Mathematical Systems Science.

   Google Scholar 

6. Kutyłowski M., Stack versus sensitivity for one-way automata, submitted for publication.

   Google Scholar 

7. Rosenberg A.L., On multihead finite automata, IBM J. Res. Develop. 10 (1966) 388–394.

   Google Scholar 

8. Yao A.C. and Rivest R.L., K+1 heads are better than K, J. ACM 25 (1978) 337–340.

   Article  Google Scholar 

Download references