講演抄録/キーワード |
講演名 |
2009-09-14 11:15
木オートマトンによる無閉路有向グラフの全域木の認識問題 ○藤芳明生(茨城大) COMP2009-26 |
抄録 |
(和) |
本稿では,木オートマトンによる無閉路有向グラフの全域木の認識問題を考える.無閉路有向グラフが木オートマトンによって受理されることを,その無閉路有向グラフが木オートマトンによって受理される全域木を持つことと定義する.この認識問題が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. |
キーワード |
(和) |
木オートマトン / 全域木 / 無閉路有向グラフ / 直並列グラフ / NP完全 / / / |
(英) |
tree automata / spanning tree / directed acyclic graphs / series-parallel graphs / NP-complete / / / |
文献情報 |
信学技報, vol. 109, no. 195, COMP2009-26, pp. 9-12, 2009年9月. |
資料番号 |
COMP2009-26 |
発行日 |
2009-09-07 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2009-26 |