線型以下の空間量をもつ 2 方向(インクドット)マルチカウンタオートマタの交代性
スポンサーリンク
概要
- 論文の詳細を見る
本論文では, 線型以下の空間量をもつ交代性マルチカウンタオートマタに関する交代の階層性, 及び線型以下の空間量をもつ2方向1インクドット交代性マルチカウンタオートマタに関する基本的ないくつかの性質について考察している。初めに, 線型以下の空間量に制限された交代性マルチカウンタオートマタは, 無限の交代階層性を有することを示す。次に, 線型以下の空間量の交代性マルチカウンタオートマタにおいて, 1インクドットをもつ場合とそうでない場合との受理能力の関係について考察する。例えば, 各l≥1 (l≥1 (l≐̸3))に対し, 任意の入力上の任意の計算路において, 全称状態(存在状態)から始まり, 高々l-1回の交代を行う2方向交代性マルチカウンタオートマタに関しては, 1インクドットをもつ場合の方が, もたない場合よりも真に受理能力が高いことなどを証明する。
- 山口大学の論文
著者
-
義永 常宏
徳山工業高等専門学校
-
井上 克司
山口大学
-
徐 建良
Nec Software Ltd.
-
井上 克司
Department of Computer Science and Systems Engineering, Faculty of Engineering, Yamaguchi University
-
義永 常宏
Department of Computer Science and Electronics Engineering, Tokuyama College of Technology
-
義永 常宏
徳山工業高等専門学校情報電子工学科
関連論文
- 「小学生がつくるロボットコンテスト」を通じた協同教育の実践
- 実践的ソフトウェア工学教育の実施例と評価
- 交代リバウンドチューリング機械
- 低い空間複雑度を持つ交代型マルチカウンタオートマタの閉包性
- 対数以下の空間量をもつ交代プッシュダウンオートマタについて
- 本校における迷惑メール対策の運用とその状況
- Webベースの簡単メーリングリスト管理システム
- Some Hierarchy Results of Alternating Automata with Counters and Stack-Counters
- A Hierarchy Result of Cooperating Systems of Two-Way Counter Machines
- 実時間1方向オールタネイティングマルチスタックカウンタオートマタの階層性
- A note on one-way multicounter machines and cooperating systems of one-way finite automata
- A Relationship between nondeterministic Turing machines and 1-inkdot Turing machines with small space
- 5N-1 全称状態のみの交代性コオペレーティング有限オートマトンシステムに関するある性質について(アルゴリズム,学生セッション,ソフトウェア科学・工学,情報処理学会創立50周年記念)
- 線型以下の空間量をもつ 2 方向(インクドット)マルチカウンタオートマタの交代性
- 対数以下の空間量を持つ交代プッシュダウンオートマタに関するいくつかの考察
- 対数以下の空間量を持つ2方向(1-インクドット)オルタネーティングプッシュダウンオートマタの交代性
- Multi-Inkdot Alternating Multi-Counter Automate with Sublinear Space and Constant Leaf-Size
- LU分解と一般逆行列
- サブリニアスペースを持つ2方向(インクドッド)マルチカウンタオートマタの交代性
- Alternation for Two-Way(Inkdot) Multi-Counter Automata with Sublinear Space
- 低い空間複雑度をもつオールタネイティングマルチカウンタオートマタに関するある性質
- 時刻印を用いた分散型デッドロック検出アルゴリズムとその評価
- トークン授受方式による分散デッドロック検出アルゴリズム
- 時刻印を用いた分散デッドロック検出アルゴリズム
- 分散トランザクションシミュレーションシステムのUNIX上での実現
- レベル情報を用いたデッドロック検出アルゴリズムのシミュレーションによる評価
- 連続型と周期型の両方に適用可能なレベル情報を用いたデッドロック検出アルゴリズムとその評価
- 図書館データベースシステムの開発
- 周期的実行によるレベル情報を用いたデッドロック検出アルゴリズム
- Two-Way Alternating Counter Automata with Only Universal States.
- 図書館データベースの論理設計
- UCSD PASCALによるCAP-X処理系の作成(第2部) : COMP-Xシミュレータ
- UCSD PASCALによるCAP-X処理系の作成(第1部) : アセンブラ,ローダ
- シミュレーションによるデッドロック検出アルゴリズムの評価