「XPath充足可能性を判定する多項式時間アルゴリズムの提案と評価」

［情報処理学会論文誌 Vol.57　No.5, pp.1477-1488］
［論文概要］

　XPath 充足可能性判定問題は，問合せの最適化などに応用できる重要な問題であるが，一般にはNP困難であることが知られている．そのため，DTD や XPath 式のクラスを制限することで，多項式時間で充足可能性を判定できるアルゴリズムを提案する研究が行われている．本論文では，多項式時間充足可能性判定アルゴリズムを提案・実装し，その有用性を評価する．実装の結果，一般的なベンチマークに対して数十ミリ秒で判定でき，SAT ソルバを用いた手法に比べて十分に高速であることがわかった．

［推薦理由］

　本論文は、XPathの充足可能性判定を行う多項式時間アルゴリズムを提案するものである。この判定問題は一般的にはNP困難であるが、問題のクラスを現実的な範囲で制限することにより効率化を実現している。また、理論的な議論に加えて、実装と実験によって判定時間を計測し、その効率性を示している。理論と実装の両面から提案手法を評価しており、その有用性は高く評価できる。よって、論文賞に相応しい論文として推薦する。