@article{oai:ipsj.ixsq.nii.ac.jp:00160381,
 author = {杉村, 憲司 and 石原, 靖哲 and 藤原, 融 and Kenji, Sugimura and Yasunori, Ishihara and Toru, Fujiwara},
 issue = {5},
 journal = {情報処理学会論文誌},
 month = {May},
 note = {XPath充足可能性判定問題は，問合せの最適化などに応用できる重要な問題であるが，一般にはNP困難であることが知られている．そのため，DTDやXPath式のクラスを制限することで，多項式時間で充足可能性を判定できるアルゴリズムを提案する研究が行われている．本論文では，多項式時間充足可能性判定アルゴリズムを提案・実装し，その有用性を評価する．実装の結果，一般的なベンチマークに対して数十ミリ秒で判定でき，SATソルバを用いた手法に比べて十分に高速であることが分かった．, XPath satisfiability is an important problem that is useful for query optimization, but it is known to be NP-hard in general. Therefore, some researches propose polynomial-time algorithms for deciding XPath satisfiability for some restricted classes of DTDs and XPath expressions. In this paper, we propose and implement polynomial-time algorithms for XPath satisfiability, and discuss their usefulness. The satisfiability of a standard benchmark can be decided in several tens of milliseconds; it is much faster than the methods based on SAT solvers.},
 pages = {1477--1488},
 title = {XPath充足可能性を判定する多項式時間アルゴリズムの提案と評価},
 volume = {57},
 year = {2016}
}