情報処理学会 第87回全国大会

2M-07
高さ制約変数を持つ無順序木構造パターンの多項式時間マッチングアルゴリズム
○松下慎太郎,正代隆義(福岡工大)
無順序木は、頂点間の親子関係は存在するが、子頂点間の順序が定義されていない木構造である。無順序木は、化学構造のモデリングやXML文書の解析など、多様な分野で利用されている。本発表では、無順序木データに共通する高さの情報を表現する木構造パターンとして、高さ制約変数付き無順序項木パターンを扱う。高さ制約変数とは、幹長と高さの情報を制約として持つ構造的変数である。この変数は、各変数が持つ二つの制約を同時に満たす任意の無順序木に置き換えることができる。本発表では、高さ制約変数付き無順序項木パターンtと無順序木Tを入力とし、tがTにマッチするか否かを決定する多項式時間アルゴリズムを提案する。