Name
Abstract | ||
|---|---|---|
This paper introduces two-dimensional probabilistic Turing machines (2-ptm's), and investigates several properties of them. We first investigate a relationship between two-dimensional alternating finite automata (2-afa's) and 2-ptm's with error probability less than 1/2 and with sublogarithmic space, and show that there is a set of square tapes accepted by 2-afa, but not recognized by any o(log n) space-bounded 2-ptm with error probability less than a. This partially solves an open problem in Okazaki et al. (Inform. Sci., to appear). We next investigate a space hierarchy of 2-ptm's with error probability less than 1/2 and with sublogarithmic space, and show that if L(n) is space-constructible by a two-dimensional Turing machine, log log n < L(n) less than or equal to log n and L'(n) = o o(L(n)), then, there is a set of square tapes accepted by a strongly L(n) space-bounded two-dimensional deterministic Turing machine, but not recognized by any L'(nj space-bounded 2-ptm with error probability less than 1/2. (C) 1999 Elsevier Science Inc. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1016/S0020-0255(98)10049-X | Inf. Sci. |
Keywords | Field | DocType |
two-dimensional probabilistic,space complexity,finite automata,turing machine,error probability | Artificial intelligence,Time hierarchy theorem,Discrete mathematics,Combinatorics,Probabilistic Turing machine,Universal Turing machine,NSPACE,Super-recursive algorithm,Turing machine,Alternating Turing machine,Non-deterministic Turing machine,Mathematics,Machine learning | Journal |
Volume | Issue | ISSN |
113 | 3-4 | 0020-0255 |
Citations | PageRank | References |
3 | 0.41 | 14 |
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 |