Name
Abstract | ||
|---|---|---|
This paper shows a sublogarithmic space lower bound for two-dimensional probabilistic Turing machines (2-ptm's) over square tapes with bounded error, and shows, using this space lower bound theorem, that a specific set is not recognized by any o(log n) space-bounded 2- ptm. Furthermore, the paper investigates a relationship between 2-ptm's and two-dimensional Turing machines with both nondeterministic and probabilistic states, which we call "two-dimensional stochastic Turing machines (2-stm's)", and shows that for any loglog n ≤ = L(n) = o(log n), L(n) space-bounded 2-ptm's with bounded error are less powerful than L(n) space-bounded 2-stm's with bounded error which start in nondeterministic mode, and make only one alternation between nondeterministic and probabilistic modes. |
Year | Venue | Keywords |
|---|---|---|
2002 | Developments in Language Theory | probabilistic state,loglog n,space-bounded 2-ptm,probabilistic mode,nondeterministic mode,space-bounded 2-stm,two-dimensional turing machine,bounded error,log n,two-dimensional probabilistic,lower bound,turing machine |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Probabilistic Turing machine,NSPACE,PSPACE,Turing reduction,Linear speedup theorem,Linear bounded automaton,Time hierarchy theorem,Mathematics,PP | Conference | 2450 |
ISSN | ISBN | Citations |
0302-9743 | 3-540-40431-7 | 0 |
PageRank | References | Authors |
0.34 | 10 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuji Sasaki | 1 | 0 | 0.34 |
| Katsushi Inoue | 2 | 515 | 74.43 |
| Akira Ito | 3 | 0 | 0.34 |
| Yue Wang | 4 | 34 | 9.08 |