単純決定性プッシュダウンオートマトンおよびその部分クラスにおける等価性・包含性判定アルゴリズムと時間計算量評価

この論文をさがす

著者

    • 若月, 光夫, 1965- ワカツキ, ミツオ

書誌事項

タイトル

単純決定性プッシュダウンオートマトンおよびその部分クラスにおける等価性・包含性判定アルゴリズムと時間計算量評価

著者名

若月, 光夫, 1965-

著者別名

ワカツキ, ミツオ

学位授与大学

電気通信大学

取得学位

博士 (工学)

学位授与番号

甲第28号

学位授与年月日

1993-03-23

注記・抄録

博士論文

目次

  1. ABSTRACT / (0006.jp2)
  2. 目次 / p1 (0007.jp2)
  3. 1 序論 / p1 (0009.jp2)
  4. 1.1 研究の背景 / p1 (0009.jp2)
  5. 1.2 本論文の概要 / p5 (0013.jp2)
  6. 2 準備 / p8 (0016.jp2)
  7. 2.1 諸定義および記法 / p8 (0016.jp2)
  8. 2.2 前提 / p11 (0019.jp2)
  9. 3 単純DPDAの等価性判定を行う直接的分岐アルゴリズム / p13 (0021.jp2)
  10. 3.1 等価性判定アルゴリズム#1 / p14 (0022.jp2)
  11. 3.2 アルゴリズム#1の有限終端性および正当性 / p24 (0032.jp2)
  12. 3.3 アルゴリズム#1の定量的評価 / p31 (0039.jp2)
  13. 4 単純DPDAの等価性判定の改良分岐アルゴリズムとその最大時間計算量 / p35 (0043.jp2)
  14. 4.1 スタック同値類 / p35 (0043.jp2)
  15. 4.2 改良分岐アルゴリズム#2 / p37 (0045.jp2)
  16. 4.3 アルゴリズム#2の有限終端性および正当性 / p44 (0052.jp2)
  17. 4.4 アルゴリズム#2の定量的評価 / p49 (0057.jp2)
  18. 5 単純DPDAの等価性を決定する最短入力記号列長の上界 / p52 (0060.jp2)
  19. 5.1 単純DPDAの等価性判別上界 / p53 (0061.jp2)
  20. 6 極単純DPDAの包含性判定を行う高速アルゴリズム / p62 (0070.jp2)
  21. 6.1 前提および基本的性質 / p62 (0070.jp2)
  22. 6.2 包含性判定アルゴリズム / p66 (0074.jp2)
  23. 6.3 アルゴリズムの有限終端性および正当性 / p75 (0083.jp2)
  24. 6.4 アルゴリズムの定量的評価 / p83 (0091.jp2)
  25. 7 結論 / p96 (0104.jp2)
  26. 謝辞 / p98 (0106.jp2)
  27. 参考文献 / p99 (0107.jp2)
  28. 関連論文の印刷公表の方法および時期 / p104 (0112.jp2)
1アクセス

各種コード

  • NII論文ID(NAID)
    500000094921
  • NII著者ID(NRID)
    • 8000000953020
  • DOI(NDL)
  • NDL書誌ID
    • 000000259235
  • データ提供元
    • NDL-OPAC
    • NDLデジタルコレクション
ページトップへ