Name
Title | ||
|---|---|---|
Closure properties of the classes of sets recognized by space-bounded two-dimensional probalistic turing machines |
Abstract | ||
|---|---|---|
This paper investigates closure properties of the classes of sets recognized by spacebounded two-dimensional probabilistic Turing machines with error probability less than 12. Let 2-PTM(L(m,n)) be the class of sets recognized by L(m,n) space-bounded two-dimensional probabilistic Turing machines with error probability less than 12, where L(m, n): N^2 - N (N denotes the set of all the positive integers) be a function with two variables m (= the number of rows of input tapes) and n (= the number of columns of input tapes). We first show that (i) for any function @?(m) = o(logm) (resp., @?(m) = o(log m/log log m)) and any monotonic nondecreasing function g(n) which can be constructed by some one-dimensional deterministic Turing machine, 2-PTM(L(m, n)) is not closed under row catenation, row closure, and projection, where L(m, n) = @?(m)+ g(n) (resp., L(m,n) = @?(m) x g(n)), and (ii) for any function g(n) = o(log n) (resp., g(n) = o(logn/loglogn)) and any monotonic nondecreasing function @?(m) which can be constructed by some one-dimensional deterministic Turing machine, 2-PTM(L(m, n)) is not closed under column catenation, column closure, and projection, where L(m,n) = @?(m)+g(n)(resp., L(m, n) = @?(m) x g(n)). We then show that 2-PTM^T(L(m, n)) is closed under union, intersection, and complementation for any L(m, n), where 2-PTM^T(L(m, n)) denotes the class of sets recognized by L(m, n) space-bounded two-dimensional probabilistic Turing machines with error probability less than 12 which always halt in the accepting or rejecting state for all the input tapes. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1016/S0020-0255(98)10084-1 | Inf. Sci. |
Keywords | Field | DocType |
closure property,log log m,one-dimensional deterministic,error probability,space-bounded two-dimensional probalistic,monotonic nondecreasing function g,function g,input tape,log n,log m,space-bounded two-dimensional probabilistic,monotonic nondecreasing function,turing machine | Integer,Binary logarithm,Artificial intelligence,Catenation,Monotonic function,Discrete mathematics,Combinatorics,Closure (mathematics),Turing machine,Non-deterministic Turing machine,Machine learning,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
115 | 1-4 | 0020-0255 |
Citations | PageRank | References |
1 | 0.36 | 13 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tokio Okazaki | 1 | 16 | 3.59 |
| Katsushi Inoue | 2 | 515 | 74.43 |
| Akira Ito | 3 | 10 | 1.60 |
| Yue Wang | 4 | 34 | 9.08 |