For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Note on Space Complexity of Nondeterministic Two-Dimensional Turing Machines
Akira ITO Katsushi INOUE Itsuo TAKANAMI Hiroshi TANIGUCHI
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1983/08/25
Print ISSN: 0000-0000
Type of Manuscript: LETTER
Category: Automata and Languages
Full Text: PDF>>
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.