スタック反転数限定PDAのSpace Complexity
スポンサーリンク
概要
- 論文の詳細を見る
与えられた入力に対してpushdown automatonがスタックincreasing modeからスタックdecreasing modeへ移行する時をturnと呼ぶ。非決定性(決定性)pushdown automatonにおいて長さnの任意の入力を高々f (n) turnで受理できる言語のクラスをPDA-TURN (f(n)) (DPDA-TURN(f(n)))で表す。本論文では[4]で示されてたDPDA-TURN (f(n))⫃DSPACE(f(n)logn)を改良し、DPDA-TURN (f(n))⫃DSPACE(logf(n)logn)及びこの結果の非決定性版PDA-TURN(f(n))⫃NSPACE(logf(n)logn)を示した。このことよりPDA-TURN(O(1))⫃NL、つまり.[4]で示されたmetalinear context-free languageがNLに含まれることが導かれ、これは[6]の主結果の一般化に相当する。
- 社団法人電子情報通信学会の論文
- 1999-12-10
著者
関連論文
- 児童・生徒の情報の科学的な興味を目的としたBebras国際コンテスト参加報告
- 情報オリンピック : 科学技術創造立国日本を担う人材の発掘育成とその課題
- Alternating CFG 再び : 新旧種とその特徴付け (計算機科学基礎理論の新展開)
- Shrinking alternating two-pushdown automata (計算機科学基礎理論の新展開 研究集会報告集)
- Alternating CFG の拡張について(計算機科学の理論とその応用)
- 部分グラフ連結化問題による計算量の階層
- スタック反転数限定PDAのSpace Complexity
- 4.情報オリンピック : 国際科学オリンピックおよびプログラミングコンテストの紹介(未来のコンピュータ好きを育てる)
- スタック反転数限定PDAのSpace Complexity
- J.E.Hopcroft, J.D. Ullman 著, "Introduction to Automata Theory, Languages, and Computation", Addison-Wesley, A5変形版, X+418, \6,670, 1979
- 重み付きグラフの最大マッチングを求める並列近似アルゴリズム
- A TENTATIVE APPROACH TO 2-DIMENSIONAL THEORY OF DNA COMPUTATION
- 最適な最短経路アルゴリズムを持つグラフについて
- Some additional remarks on grammatical characterizations of alternating PDAs (理論計算機科学の深化--新たな計算世界観を求めて RIMS研究集会報告集)
- CFG/PDA の alternation 付与方法ほかについて(計算理論とアルゴリズムの新展開)
- Variants of alternating grammars