Name
Abstract | ||
|---|---|---|
This paper investigates non-closure properties of the classes of sets accepted by space-bounded two-dimensional alternating Turing machines and three-way two-dimensional alternating Turing machines. Let 2-ATM(L(m, n)) (resp., TR2-ATM(L(m, n))) be the class of sets accepted by L(m, n) space-bounded two-dimensional alternating Turing machines (resp., L(m, n) space-bounded three-way two-dimensional alternating Turing machines), where L(m, n): N2 → N ∪ {0} (N denotes the set of all the positive integers) is a function with two variables m ( = the number of rows of input tapes) and n (= the number of columns of input tapes). We show that (i) for any function g(n) = o(logn) (resp., g(n) = o(logn/log log n)) and any monotonic non-decreasing function f(m) which can be constructed by some one-dimensional deterministic Turing machine, 2-ATM(L(m,n)) and TR2-ATM(L(m,n)) are not closed under column catenation, column +, and projection, and (ii) for any function f(m) = o(logm) (resp., f(m) = o(logm/log log m)) and any monotonic non-decreasing function g(n)which can be constructed by some one-dimensional deterministic Turing machine, 2-ATM(L(m, n)) and TR2-ATM(L(m, n)) are not closed under row catenation, row +, and projection, where L(m, n) = f(m) + g(n) (resp., L(m, n) = f(m) × g(n)). |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1016/S0020-0255(02)00186-X | Inf. Sci. |
Keywords | Field | DocType |
turing machine,log log n,log log m,one-dimensional deterministic,monotonic non-decreasing function,row catenation,monotonic non-decreasing function g,non-closure property,column catenation,function g,input tape,closure property | Row,Integer,Monotonic function,Discrete mathematics,Combinatorics,Closure (mathematics),Turing machine,Catenation,Non-deterministic Turing machine,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
146 | 1-4 | 0020-0255 |
Citations | PageRank | References |
0 | 0.34 | 10 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tokio Okazaki | 1 | 16 | 3.59 |
| Atsuyuki Inoue | 2 | 3 | 1.16 |
| Katsushi Inoue | 3 | 515 | 74.43 |
| Akira Ito | 4 | 5 | 2.58 |
| Yue Wang | 5 | 34 | 9.08 |