グラフマイナー定理に基づく線形時間アルゴリズムの自動生成
スポンサーリンク
概要
- 論文の詳細を見る
近年Robertson-Seymourにより証明されたグラフマイナー定理(Wagnberの予想)により有限グラフ上のminor-closedな性質の検出は多項式時間アルゴリズムが存在することが知られている.しかし,その証明は非構成的であり一般に実際のアルゴリズムを構成するのは難しかった.本稿ではグラフマイナー定理の簡単な場合であるHigmanの補題の構成的証明を用い,未解決問題であった時間概念を含むデータベース上の選言的単項質問処理の線形時間アルゴリズムを自動生成により与えた.
- 一般社団法人情報処理学会の論文
- 1993-05-28
著者
関連論文
- モデル検査技術を利用したプログラム解析器の生成ツール
- イベント順序証明システムの正当性の形式的証明
- 抽象実行 そのフレームワークと実例(その3)
- 抽象実行 そのフレームワークと実例(その2)
- 抽象解釈におけるLazyな抽象領域の生成
- 抽象実行 そのフレームワークと実例(その1)
- 最小不動点計算に基づくプログラムの帰納的性質の導出 (並列処理)
- 広域データフロー解析に基づく関数型プログラムの変則性検出
- さきがけ「機能と構成」研究1 : 効率的で正しいプログラムの自動生成
- ASIA-PEPM 2002/FLOPS 2002参加報告
- 利得の最適連想規則を求める線形時間アルゴリズムの導出
- 最大重み和問題の線形時間アルゴリズムの導出
- ACM PLI 2000会議報告
- ナップサック問題およびその発展問題の統一的解法
- 非線形TRSのE重なり性について
- 書換え系のPerpetual性と一様停止性
- 高階書換え系の単一正規形性
- 逐次性v.s.ストリクト性 : 非線形項書換え系の最適戦略にむけて
- 高階書き換え系の単一正規形性
- 項グラフ書換え系における単純ギャップ停止性
- 91-37 パラメトリシティの証明論の概略
- 理論計算機科学に関する豊橋シンポジウムに参加して
- グラフマイナー定理に基づく線形時間アルゴリズムの自動生成
- 89-29 ストリクトネス解析に基づく関数型プログラムの計算量解析
- 87-21 関数型プログラムの静的解析
- グリッドコンピューティングにおける代理証明書信任リスト(ディペンダブルソフトウェア)
- 「情報処理学会論文誌 : プログラミング」の編集について
- 「情報処理学会論文誌 : プログラミング」の編集について