A Note on Space Complexity of Nondeterministic Two-Dimensional Turing Machines

Akira ITO  Katsushi INOUE  Itsuo TAKANAMI  Hiroshi TANIGUCHI  

Publication
IEICE TRANSACTIONS (1976-1990)   Vol.E66   No.8   pp.508-509
Publication Date: 1983/08/25
Online ISSN: 
DOI: 
Print ISSN: 0000-0000
Type of Manuscript: LETTER
Category: Automata and Languages
Keyword: 


Full Text: PDF>>
Buy this Article




Summary: 
It has already been known that there exists an infinite hierarchy of the classes of sets of square tapes accepted by deterministic space-bounded two-dimensional Turing machines with spaces below log m. This paper shows that there exists an infinite hierarchy of the classes of sets of square tapes accepted by nondeterministic space-bounded two-dimensional Turing machines with spaces less than or equal to log m.