Recognition of directed acyclic graphs by spanning tree automata

被引：8

作者：

Fujiyoshi, Akio ^{[1
]}

机构：

[1] Ibaraki Univ, Dept Comp & Informat Sci, Ibaraki 3168511, Japan

来源：

THEORETICAL COMPUTER SCIENCE | 2010年 / 411卷 / 38-39期

关键词：

Tree automaton; Directed acyclic graph; Spanning tree; NP-completeness; Series parallel graph; Generalized series parallel graph; GRAMMAR;

D O I：

10.1016/j.tcs.2010.06.006

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper, we study tree automata for directed acyclic graphs (DAGs). We define the movement of a tree automaton on a DAG so that a DAG is accepted by a tree automaton if and only if the DAG has a spanning tree accepted by the tree automaton. We call this automaton a spanning tree automaton. The NP-completeness of the membership problem of DAGs for spanning tree automata is shown. However, if inputs are restricted to series-parallel graphs or generalized series-parallel graphs, it is shown that the membership problem for spanning tree automata is solvable in linear time. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：3493 / 3506

页数：14

共 13 条

[1] Closure properties and decision problems of dag automata [J].

Anantharaman, S ;

Narendram, P ;

Rusinowitch, M .

INFORMATION PROCESSING LETTERS, 2005, 94 (05) :231-240

[2] A partial k-arboretum of graphs with bounded treewidth [J].

Bodlaender, HL .

THEORETICAL COMPUTER SCIENCE, 1998, 209 (1-2) :1-45

[3]

Chan K.F., 2000, IJDAR, V3, P3

[4]

CHARATONIK W, MPII19992001

[5]

Comon H., 2008, Tree Automata Techniques and Applications

[6]

ETO Y, 2001, P 6 INT C DOC AN REC, P430

[7]

FUJIYOSHI A, 2005, LNCS, V3845, P129

[8]

Fujiyoshi A, 2008, LECT NOTES ARTIF INT, V5144, P415, DOI 10.1007/978-3-540-85110-3_35

[9]

Fujiyoshi A, 2009, LECT NOTES COMPUT SC, V5642, P105, DOI 10.1007/978-3-642-02979-0_14

[10] COMBINATORIAL ALGORITHMS ON A CLASS OF GRAPHS [J].

KORNEYENKO, NM .

DISCRETE APPLIED MATHEMATICS, 1994, 54 (2-3) :215-217

← 1 2 →