サブリニアスペースを持つ2方向(インクドッド)マルチカウンタオートマタの交代性
スポンサーリンク
概要
- 論文の詳細を見る
サブリニアスペース(線型以下の空間複雑度)を持つ交代型マルチカウンタオートマタにおける交代性の階層と1-インクドット交代型マルチカウンタオートマタのある基本的な性質について考察している。初めに,各k≥1に対し,サブリニアスペースを持つ交代型k-カウンタオートマタに関する交代階層性が無限であることを示す。次に,サブリニアスペースに限定された交代型マルチカウンタオートマタで1インクドットの機能を持つ場合と持たない場合の受理能力の関係について考察する。例えば,各k,l≥1に対し,存在状態(全称状態)から始まり,高々l-1回の交代を行う2-方向交代型k-カウンタオートマタの受理能力は,1インクドットを持つ場合の方が真に強力であることを示す。最後に,1-インクドット交代型マルチカウンタオートマタの最初のレベルにおける交代階層性について考察し,例えば,各k≥1に対し,サブリニアスペースを持つ2-方向1-インクドット交代型k-カウンタオートマタで存在状態のみからなるものと全称状態のみからなるものの受理能力は比較不能であることを示す.
- 社団法人電子情報通信学会の論文
- 1995-04-21
著者
関連論文
- 「小学生がつくるロボットコンテスト」を通じた協同教育の実践
- 実践的ソフトウェア工学教育の実施例と評価
- 低い空間複雑度を持つ交代型マルチカウンタオートマタの閉包性
- 本校における迷惑メール対策の運用とその状況
- Webベースの簡単メーリングリスト管理システム
- Some Hierarchy Results of Alternating Automata with Counters and Stack-Counters
- 実時間1方向オールタネイティングマルチスタックカウンタオートマタの階層性
- 5N-1 全称状態のみの交代性コオペレーティング有限オートマトンシステムに関するある性質について(アルゴリズム,学生セッション,ソフトウェア科学・工学,情報処理学会創立50周年記念)
- 線型以下の空間量をもつ 2 方向(インクドット)マルチカウンタオートマタの交代性
- 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部) : アセンブラ,ローダ
- シミュレーションによるデッドロック検出アルゴリズムの評価