Some results concerning automata on two-dimensional tapes
- 1 January 1974
- journal article
- research article
- Published by Taylor & Francis in International Journal of Computer Mathematics
- Vol. 4 (1-4) , 269-279
- https://doi.org/10.1080/00207167408803092
Abstract
Hierarchies of automata operating on two-dimensional tapes are investigated. In particular, it is shown that finite automata with n+3 markers (n+2 heads) are strictly more powerful than those with n markers (n heads)Keywords
This publication has 5 references indexed in Scilit:
- Refinements of the nondeterministic time and space hierarchiesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1973
- On two-way multihead automataJournal of Computer and System Sciences, 1973
- On non-determinancy in simple computing devicesActa Informatica, 1972
- Characterizations of Pushdown Machines in Terms of Time-Bounded ComputersJournal of the ACM, 1971
- Automata on a 2-dimensional tapePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1967