Sublinear Space-Bounded One-Way Self-Verifying Nondeterministic Turing Machines
スポンサーリンク
概要
- 論文の詳細を見る
We investigate the accepting power of one-way self-verifying nondeterministic Turing machines with sublinear space. A self-verifying nondeterministic Turing machine has four types of states : working, accepting, rejecting, and neutral ("I don't know") ones. There is no possible move from any rejecting, accepting and neutral states. The machine is not allowed to make mistakes. We show that there exists a language accepted by a log n space-bounded one-way self-verifying nondeterministic Turing machine, but not accepted by any o(n) space-bounded deterministic Turing machine, and also show that there exists a language accepted by a log n space-bounded one-way nondeterministic Turing machine, but not accepted by any o(n) space-bounded self-verifying nondeterministic Turing machine.
- 2005-12-01
著者
-
YOSHINAGA Tsunehiro
Department of Computer Science and Electrics Engineering, Tokuyama College of Technology
-
XU Jianliang
Ocean University of China
-
INOUE Katushi
Yamaguchi University
-
Inoue Katsushi
Yamaguchi Univ.
-
Yoshinaga Tsunehiro
Department Of Computer Science And Electrics Engineering
-
Xu Jianliang
Ocean Univ. China Qingdao Chn
関連論文
- A Space Lower-Bound Technique for Three-Dimensional Alternating Turing Machines
- Sublinear Space-Bounded One-Way Self-Verifying Nondeterministic Turing Machines
- 空間量が対数以下に制限された存在(全称)状態のみからなる1-インクドット交代チューリングマシンの閉包性について
- Non-closure Properties of 1-Inkdot Nondeterministic Turing Machines and Alternating Turing Machines with Only Universal States Using Small Space
- A Note on Alternating Multi-Counter Automata with Small Space
- Alternating Finite Automata with Counters and Stack-Counters Operating in Realtime
- Hierarchical Properties of Realtime One-Way Alternating Multi-Stack-Counter Automata (Special Section on Discrete Mathematics and Its Applications)
- A Note on Realtime One-Way Alternating and Deterministic Multi-Counter Automata(Special Issue on Selected Papers from LA Symposium)
- Las Vegas, Self-Verifying Nondeterministic and Deterministic One-Way Multi-Counter Automata with Bounded Time
- D-1-1 Three-Dimensional Probabilistic Finite Automata
- Sublogarithmic Space-Bounded Multi-Inkdot Alternating Turing Machines with Only Existential (Universal) States(Discrete Mathematics and Its Applications)
- Polynomial Time-Bounded Alternating Multi-Counter Automata
- Some Observations on One-way Alternating Pushdown Automata with Sublinear Space(Discrete Mathematics and Its Applications)
- On 1-Inkdot Alternating Pushdown Automata with Sublogarithmic Space(Theory of Automata, Formal Language Theory)
- Sublinear Space-Bounded Multi-Inkdot Alternating Multi-Counter Automata with Only Universal States
- D-1-3 Non-Closure Properties of Cooperating Systems of One-Way Alternating Finite Automata with Only Universal States