属性文法におけるK訪問性判定問題の指数的下界について
スポンサーリンク
概要
- 論文の詳細を見る
属性文法において(積極的な)意味をもつ最大のクラスは、属性値が循環定義に陥らない非循環属性文法のクラスである。非循環属性文法は純粋k訪問性(後述)という性質をもつことが知られている。特定の自然数kに対し、与えられた非循環属性文法が純粋k訪問性をもつか否かを判定する問題を、k訪問性判定問題という。この問題は決定可能であることは知られていたが、厳密な時間計算量の評価は未解決問題であった。本稿では、k訪問性判定問題を解くのに、入力サイズの指数関数のオーダーの時間計算量が、本質的に必要となることがわかったので報告する。紙数の都合で証明の詳細については述べられないので、興味のある方は[1]を参照されたい。
- 一般社団法人情報処理学会の論文
- 1986-10-01