Specifying Graph Languages with Type Graphs

被引：6

作者：

Corradini, Andrea ^{[1
]}

Koenig, Barbara ^{[2
]}

Nolte, Dennis ^{[2
]}

机构：

[1] Univ Pisa, Pisa, Italy

[2] Univ Duisburg Essen, Duisburg, Germany

来源：

GRAPH TRANSFORMATION, ICGT 2017 | 2017年 / 10373卷

关键词：

SHAPE-ANALYSIS; LOGIC; CONSTRAINTS;

D O I：

10.1007/978-3-319-61470-0_5

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We investigate three formalisms to specify graph languages, i.e. sets of graphs, based on type graphs. First, we are interested in (pure) type graphs, where the corresponding language consists of all graphs that can be mapped homomorphically to a given type graph. In this context, we also study languages specified by restriction graphs and their relation to type graphs. Second, we extend this basic approach to a type graph logic and, third, to type graphs with annotations. We present decidability results and closure properties for each of the formalisms.

引用

页码：73 / 89

页数：17

共 24 条

[1]

Abdulla Parosh Aziz, 2013, Automated Technology for Verification and Analysis. 11th International Symposium, ATVA 2013. Proceedings: LNCS 8172, P224, DOI 10.1007/978-3-319-02444-8_17

[2]

Blume Christoph, 2012, Graph Transformations. Proceedings 6th International Conference, ICGT 2012, P264, DOI 10.1007/978-3-642-33654-6_18

[3] Treewidth, pathwidth and cospan decompositions with applications to graph-accepting tree automata [J].

Blume, Christoph ;

Bruggink, H. J. Sander ;

Friedrich, Martin ;

Koenig, Barbara .

JOURNAL OF VISUAL LANGUAGES AND COMPUTING, 2013, 24 (03) :192-206

[4]

Bruggink HJS, 2008, LECT NOTES COMPUT SC, V5214, P336, DOI 10.1007/978-3-540-87405-8_23

[5] Counterexample-guided abstraction refinement for symbolic model checking [J].

Clarke, E ;

Grumberg, O ;

Jha, S ;

Lu, Y ;

Veith, H .

JOURNAL OF THE ACM, 2003, 50 (05) :752-794

[6]

Corradini A., 1996, Fundamenta Informaticae, V26, P241

[7]

Corradini A., 2017, ARXIV170405263

[8]

Courcelle B, 2012, ENCYCLOP MATH APPL, V138, P1, DOI 10.1017/CBO9780511977619

[9] THE MONADIC 2ND-ORDER LOGIC OF GRAPHS .1. RECOGNIZABLE SETS OF FINITE GRAPHS [J].

COURCELLE, B .

INFORMATION AND COMPUTATION, 1990, 85 (01) :12-75

[10]

Distefano D, 2006, LECT NOTES COMPUT SC, V3920, P287

← 1 2 3 →