新着情報［情報工学専攻］正代研究室 一般社団法人情報処理学会 第87回全国大会において「学生奨励賞」受賞

「高さ制約変数を持つ無順序木構造パターンの多項式時間マッチングアルゴリズム」
無順序木とは、頂点間に親子関係は存在しますが、兄弟関係は存在しない根付き木のことです。無順序項木パターンとは、無順序木構造をしたデータのパターンを表現するための構造的変数（以降、単に変数と呼びます）を含むデータ構造です。本論文で扱う変数は、グラフ理論における超辺を、変数名を持つ超辺に拡張したもので、超辺置換により任意の無順序木と置き換えることが可能です。超辺を含む頂点数は次元と呼ばれますが、変数ではそれをポート数と呼びます。本論文ではポート数2の変数のみを扱います。
高さ制約変数とは、幹長と高さの情報を制約として持つ変数です。この変数は、各変数が持つ二つの制約を同時に満たす任意の無順序木に置き換えることができます。本論文では、高さ制約変数付き無順序項木パターン𝑡と無順序木𝑇を入力とし、𝑡が𝑇にマッチするか否かを入力サイズの多項式時間で計算するアルゴリズムを提案しました。