1
|
OKAZAKI TOKIO, INOUE KATSUSHI, ITO AKIRA, WANG YUE. SPACE HIERARCHIES OF TWO-DIMENSIONAL ALTERNATING TURING MACHINES, PUSHDOWN AUTOMATA AND COUNTER AUTOMATA. INT J PATTERN RECOGN 2011. [DOI: 10.1142/s0218001499000306] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/18/2022]
Abstract
This paper investigates the space hierarchies of the language classes for two-dimensional Turing machines (2-TM's), two-dimensional pushdown automata (2-PDA's) and two-dimensional counter automata (2-CA's) with small space. We show that (1) if L(n) is space constructible by a 2-TM, L(n) ≤ log n and L′(n) = o(L(n)), then strong 2-DSPACE(L(n)) – weak 2-ASPACE(L′(n)) ≠ ∅, (2) if L(n) is space constructible by a 2-PDA, L(n) ≤ log n and L′(n) = o(L(n)), then strong 2-DPDA(L(n)) – weak 2-ASPACE(L′(n)) ≠ ∅, and (3) if L(n) is space-constructible by a 2-CA, L(n) ≤ n and L′(n) = o(L(n)), then strong 2-DCA(L(n)) – weak 2-ACA(L′(n)) ≠ ∅, (4) where strong 2-DSPACE(L(n)) (strong 2-DPDA(L(n)), strong 2-DCA(L(n))) denotes the class of sets accepted by strongly L(n) space-bounded deterministic 2-TM's (2-PDA's, 2-CA's), and weak 2-ASPACE(L′(n)) (weak 2-ACA(L′(n))) denotes the class of sets accepted by weakly L′(n) space-bounded alternating 2-TM's (2-CA's). We also investigate the closure property of space-bounded alternating 2-PDA's and 2-CA's under complementation, and show that (1) if L(n) = o( log log n), then the class of sets accepted by L(n) space-bounded alternating 2-PDA's is not closed under complementation, and (2) if L(n) is space-constructible by a 2-CA, L(n) ≤ n and [Formula: see text], then the class of sets accepted by L′(n) space-bounded alternating 2-CA's is not closed under complementation.
Collapse
Affiliation(s)
- TOKIO OKAZAKI
- Department of Electronics and Computer Science, Faculty of Science and Engineering, Science University of Tokyo in Yamaguchi, Onoda-shi, 756-0884, Japan
| | - KATSUSHI INOUE
- Department of Computer Science and Systems Engineering, Faculty of Engineering, Yamaguchi University, Ube-shi, 755 , Japan
| | - AKIRA ITO
- Department of Computer Science and Systems Engineering, Faculty of Engineering, Yamaguchi University, Ube-shi, 755 , Japan
| | - YUE WANG
- Department of Computer Science and Systems Engineering, Faculty of Engineering, Yamaguchi University, Ube-shi, 755 , Japan
| |
Collapse
|
2
|
|