Name
Title | ||
|---|---|---|
Sublogarithmic Space-Bounded Multi-Inkdot Alternating Turing Machines with Only Existential (Universal) States |
Abstract | ||
|---|---|---|
This paper investigates the accepting powers of two-way alternating Turing machines (2ATM's) with only existential (universal) states which have inkdots and sublogarithmic space. It is shown that for sublogarithmic space-bounded computations, (i) multi-inkdot 2ATM's with only existential states and the ones with only universal states are incomparable, (ii) k-inkdot 2ATM's are better than k-inkdot 2ATM's with only existential (universal) states, k ≥ 0, and (iii) the class of sets accepted by multi-inkdot 2ATM's with only existential (universal) states is not closed under complementation. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1093/ietfec/e89-a.5.1417 | IEICE Transactions |
Keywords | Field | DocType |
turing machine,existential state,sublogarithmic space-bounded multi-inkdot alternating,turing machines,sublogarithmic space,universal state,sublogarithmic space-bounded computation | Discrete mathematics,Universal Turing machine,NSPACE,Super-recursive algorithm,Turing reduction,Turing machine,Description number,Alternating Turing machine,Time hierarchy theorem,Mathematics | Journal |
Volume | Issue | ISSN |
E89-A | 5 | 0916-8508 |
Citations | PageRank | References |
1 | 0.37 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tsunehiro Yoshinaga | 1 | 6 | 6.98 |
| Jianliang Xu | 2 | 2743 | 168.17 |
| Katsushi Inoue | 3 | 515 | 74.43 |