文脈自由言語と超決定性言語の包含判定問題の決定可能性の型理論を用いた証明
スポンサーリンク
概要
- 論文の詳細を見る
言語の包含判定問題とは,与えられた言語 L1 と L2 について L1 ⊆ L2 が成立するか否かを判定する問題であり,理論的な興味の対象であるだけでなく,プログラム検証などへの広い応用を持つ重要な問題である.この問題に関する既知の最も強い結果の 1 つが文脈自由言語と超決定性言語の包含判定の決定可能性である.このオリジナルの証明は,Greibach と Friedman によって与えられている.我々はこの問題に対して,小林らによって提案されている型に基づく言語の包含判定の手法を適用し,決定可能性に対する別証明を与えた.この手法は以下のような利点を持つ.(1) 部分型関係やポンプの補題などのよく知られた概念で理論が展開できる.(2) 型推論を効率的に行う方法は多数提案されており,それらを利用することができる.また,提案する証明は小林らのアイデアを正規言語よりも広いクラスに適用したはじめての例であり,その他の非正規言語クラスへの応用も期待される.
- 2011-03-25
著者
関連論文
- 木星型惑星の構造と形成
- シューメイカー・レビー彗星と木星との衝突シミュレーション(シューメーカー=レビー第9彗星の木星衝突)
- 計算資源使用法検証における計算資源の仕様と実際の使用法との間の適合性検証アルゴリズム
- JVMにおけるロックの整合性検証のための新しい型システム
- 動的に型付けされた言語のためのオンラインな型主導部分評価(特集●プログラミング及びプログラミング言語)
- POPL/PEPM'99会議報告
- POPL/PEPM'99会議報告
- AFMセンサのための圧電薄膜の形成
- P228 T型ラインマイクロホンのノイズ減殺効果
- P369 T型ラインマイクロホンを用いた微気圧振動の観測
- T型ラインマイクロホンを用いた微気圧振動の観測(序報)
- 地球のささやきを聞く--常時地球自由振動の発見
- 41052 住宅内室温分布の要因分析とその評価方法に関する研究 : その1 暖房期における住宅内室温分布推定法の提案(住宅の暖房負荷,環境工学II)
- 41053 住宅内室温分布の要因分析とその評価方法に関する研究 : その2 累積確率を用いた暖房期の室温分布と暖房負荷の評価(住宅の暖房負荷,環境工学II)
- 41054 住宅内室温分布の要因分析とその評価方法に関する研究 : その3 標準住宅モデルを用いた室温分布と空調負荷のシミュレーション(住宅の暖房負荷,環境工学II)
- ポインタのあるプログラミング言語のための資源使用法解析
- 常時自由震動:大気と固体地球のカップリングの重要性
- 並行プログラミング言語へのチャネル使用法宣言の導入
- 042 住宅の室温分布と熱負荷の評価方法に関する研究 : その2 室温分布と空調負荷のシミュレーション(熱・暖冷房,講演研究論文、計画・技術報告)
- 041 住宅の室温分布と熱負荷の評価方法に関する研究 : その1 累積確立を用いた室温分布と熱負荷の評価法(熱・暖冷房,講演研究論文、計画・技術報告)
- 051 住宅室内温度の標準偏差と暖房期・冷房期における空調用エネルギー消費量の関係(熱環境・エネルギー,講演研究論文・計画技術報告)
- 検証済み型推論器生成のためのCoqライブラリ
- 骨組み構造物の振動伝達を抑制する最適設計
- 並列言語の高レベルなデータの通信における型を利用した最適化について
- 木星の内部構造と彗星の衝突
- An Empirical Analysis of the Information Content of the Announcements of Impaired Assets in Japan
- 木構造処理からストリーム処理プログラムへの変換のための部分的バッファリングの挿入
- 41083 住宅の断熱気密性能と暖房期・冷房期における空調用エネルギー消費量の関係(環境工学II,住宅のエネルギー消費)
- 低レベル言語のための情報流解析の型システム(プログラミングおよびプログラミング言語)
- 870 化学物質のエストロゲン活性に及ぼす代謝活性化の影響(環境工学,資源・エネルギー工学,一般講演)
- 酵母法による環境ホルモンの測定
- ポスト壁キャビティ付きスロット八木・宇田アレーを用いた平面マルチセクタアンテナ
- POPL2002/PEPM2002/PADL2002報告(プログラミング及びプログラミング言語)
- インピーダンスマッチング機能付きCMOSオンチップラットレースバラン(無線/画像処理,システムオンシリコン設計技術並びにこれを活用したVLSI)
- インピーダンスマッチング機能付きCMOSオンチップラットレースバラン(無線/画像処理,システムオンシリコン設計技術並びにこれを活用したVLSI)
- 型エラースライシングによるデッドロックの原因特定
- B-1-159 キャビティ壁をスルーホールで構成したプリントスロット八木・宇田アレーアンテナ
- 特集「プログラミング及びプログラミング言語」の編集にあたって(プログラミング及びプログラミング言語)
- 大気海洋の窓としての固体地球--固体地球常時自由振動 (総特集 海半球観測研究の進展)
- 木星自由振動と木星内部構造
- 文脈自由言語と超決定性言語の包含判定問題の決定可能性の型理論を用いた証明
- リージョン推論に基づくメモリ管理の下でのガーベジコレクション
- 彗星衝突による木星振動の励起(「木星に衝突する彗星 : シューメイカー・レビー9」)
- Constraint Satisfaction in Logic Programming, Paseal Van Hentenryck, The MIT Press, 1989 (制約論理プログラミング)
- SELENE-2における月広帯域地震観測
- S22-08P ペネトレータを使った月内部構造探査(一般ポスターセッション2,ポスター発表)
- S22-09 ペネトレータ地震計ネットワークによる月震観測(口頭セッション22:惑星探査,口頭発表)
- S13-12 アポロ月震計データで見る月のクレーター生成率不均質(口頭セッション13:月科学,口頭発表)
- 207 火星の常時自由振動(火星と水星の科学,オーラルセッション5)
- 306 惑星物質試料受け入れ設備(キュレーション設備)の状況 : はやぶさ試料受け入れ運用リハーサルへ向けての準備(オーラルセッション9 固体天体の科学・惑星探査I)
- P208 アポロ月震データの再解析 : バンドパスフィルタ処理によるイベント検出の試み(ポスターセッション2)
- P205 月面重力計を用いたUnlocated Deep Moonquakeの震源決定(ポスターセッション2)
- 116 月震計データから見た月面クレータ生成率不均質(オーラルセッション3 月I)
- E-6 住宅の温熱性能評価に関する研究 : その1 累積確率を用いた室温分布と暖房負荷の評価
- E-7 住宅の温熱性能評価に関する研究 : その2 住宅の室温分布と空調負荷のシミュレーション
- G-67 住宅内温度分布に関する全国調査 : その4 室内外温度差が空調用エネルギー消費量に与える影響