Name
Abstract | ||
|---|---|---|
This paper introduces a three-way two-dimensional probabilistic Turing machine (tr2-ptm), and investigates several properties of the machine. The tr2-ptm is a two-dimensional probabilistic Turing machine (2-ptm) whose input head can only move left, right. or down, but not up.Let 2-ptm(s) (resp, tr2-ptm(s)) denote a 2-ptm (resp. tr2-ptm) whose input tape is restricted to square ones, and let 2-PTMs(S(n)) (resp. TR2-PTMs(S(n))) denote the class of sets recognized by S(n) space-bounded 2-ptm(s)'s (resp. tr2-ptm(s)'s) with error probability less than 1/2, where S(n) : N --> N is a function of one variable n (= the side-length of input tapes). Let TR2-PTM(L(m, n)) denote the class of sets recognized by L(m, n) space-bounded tr2-ptm's with error probability less than 2, where L(m, n) : N-2 --> N is a function of two variables m (= the number of rows of input tapes) and n (= the number of columns of input tapes).The main results of this paper are:(1) 2-NFA(s)-TR2-PTMs(S(n)) not equal phi for any S(n) = o(log n), where 2-NFA(s) denotes the class of sets of square tapes accepted by two-dimensional nondeterministic finite automata,(2) TR2-PTMs(S(n)) subset of(plus attached) 2-PTMs(S(n)) for any S(n)= o(log n), and(3) for any function g(n) = o(log n) (resp. g(n) = o(log n/ log log n)) and any monotonic nondecreasing function f(m) which can be constructed by some one-dimensional deterministic Turing machine, TR2-PTM (f(m) + g(n)) (resp. TR2-PTM(f(m) x g(n))) is not closed under column catenation, column closure, and projection.Additionally, we show that two-dimensional nondeterministic finite automata are equivalent to two-dimensional probabilistic finite automata with one-sided error in accepting power. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1142/S0218001400000313 | INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE |
Keywords | Field | DocType |
three-way two-dimensional probabilistic Turing machine, closure property, space-bounded computation | Binary logarithm,Artificial intelligence,Discrete mathematics,Monotonic function,Probabilistic Turing machine,Combinatorics,Nondeterministic finite automaton,Closure (mathematics),Binary function,Turing machine,Non-deterministic Turing machine,Machine learning,Mathematics | Journal |
Volume | Issue | ISSN |
14 | 4 | 0218-0014 |
Citations | PageRank | References |
0 | 0.34 | 12 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tokio Okazaki | 1 | 16 | 3.59 |
| Katsushi Inoue | 2 | 515 | 74.43 |
| Akira Ito | 3 | 5 | 2.58 |
| Yue Wang | 4 | 34 | 9.08 |