木オートマトンによる無閉路有向グラフの全域木の認識問題

摘要

本稿では，木オートマトンによる無閉路有向グラフの全域木の認識問題を考える．無閉路有向グラフが木オートマトンによって受理されることを，その無閉路有向グラフが木オートマトンによって受理される全域木を持つことと定義する．この認識問題がNP完全であることと，直並列グラフに対しては線形時間の認識アルゴリズムが存在することを示す．%In this article, we define that a DAG is accepted by a tree automaton if the DAG has a spanning tree accepted by the tree automaton. The NP-completeness of the membership problem of DAGs for a tree automaton is shown, and a linear-time recognition algorithm of series-parallel graphs for a tree automaton is presented.