自己検証非決定性ならびにラスベガスマルチヘッド有限オートマタ

概要

論文の詳細を見る
本稿では、(シンプル)マルチヘッド有限オートマタに対して、決定性、ラスベガス、自己検証非決定性ならびに非決定性の受理能力を比較する。次の結果が成り立つことを示す。(1)各κ≥2に対し、1方向決定性κヘッド(シンプルκヘッド)有限オートマタは1方向ラスベガスκヘッド(シンプルκヘッド)有限オートマタより受理能力が弱い。(2)1方向自己検証非決定性シンプル2ヘッド有限オートマタによっては受理されるが、どんな1方向決定性シンプルマルチヘッド有限オートマトンによっても受理されない言語が存在する。(3)1方向非決定性2ヘッド(シンプル2ヘッド)有限オートマトによっては受理されるが、どんな1方向自己検証非決定性マルチヘッド(シンプルマルチヘッド)有限オートマトンによっては受理されない言語が存在する。(4)各κ≥1に対し、2方向ラスベガスκヘッド(シンプルκヘッド)有限オートマタは、2方向自己検証決定性κヘッド(シンプルκヘッド)有限オートマタと同じ受理能力を持つ。(5)2方向ラスベガスシンプル2ヘッド有限オートマタは、2方向決定性シンプル2ヘッド有限オートマタより受理能力が強い。
社団法人電子情報通信学会の論文
2000-05-11