単純決定性プッシュダウンオートマトンおよびその部分クラスにおける等価性・包含性判定アルゴリズムと時間計算量評価
この論文にアクセスする
この論文をさがす
著者
書誌事項
- タイトル
-
単純決定性プッシュダウンオートマトンおよびその部分クラスにおける等価性・包含性判定アルゴリズムと時間計算量評価
- 著者名
-
若月, 光夫, 1965-
- 著者別名
-
ワカツキ, ミツオ
- 学位授与大学
-
電気通信大学
- 取得学位
-
博士 (工学)
- 学位授与番号
-
甲第28号
- 学位授与年月日
-
1993-03-23
注記・抄録
博士論文
目次
- ABSTRACT / (0006.jp2)
- 目次 / p1 (0007.jp2)
- 1 序論 / p1 (0009.jp2)
- 1.1 研究の背景 / p1 (0009.jp2)
- 1.2 本論文の概要 / p5 (0013.jp2)
- 2 準備 / p8 (0016.jp2)
- 2.1 諸定義および記法 / p8 (0016.jp2)
- 2.2 前提 / p11 (0019.jp2)
- 3 単純DPDAの等価性判定を行う直接的分岐アルゴリズム / p13 (0021.jp2)
- 3.1 等価性判定アルゴリズム#1 / p14 (0022.jp2)
- 3.2 アルゴリズム#1の有限終端性および正当性 / p24 (0032.jp2)
- 3.3 アルゴリズム#1の定量的評価 / p31 (0039.jp2)
- 4 単純DPDAの等価性判定の改良分岐アルゴリズムとその最大時間計算量 / p35 (0043.jp2)
- 4.1 スタック同値類 / p35 (0043.jp2)
- 4.2 改良分岐アルゴリズム#2 / p37 (0045.jp2)
- 4.3 アルゴリズム#2の有限終端性および正当性 / p44 (0052.jp2)
- 4.4 アルゴリズム#2の定量的評価 / p49 (0057.jp2)
- 5 単純DPDAの等価性を決定する最短入力記号列長の上界 / p52 (0060.jp2)
- 5.1 単純DPDAの等価性判別上界 / p53 (0061.jp2)
- 6 極単純DPDAの包含性判定を行う高速アルゴリズム / p62 (0070.jp2)
- 6.1 前提および基本的性質 / p62 (0070.jp2)
- 6.2 包含性判定アルゴリズム / p66 (0074.jp2)
- 6.3 アルゴリズムの有限終端性および正当性 / p75 (0083.jp2)
- 6.4 アルゴリズムの定量的評価 / p83 (0091.jp2)
- 7 結論 / p96 (0104.jp2)
- 謝辞 / p98 (0106.jp2)
- 参考文献 / p99 (0107.jp2)
- 関連論文の印刷公表の方法および時期 / p104 (0112.jp2)