Specifying graph languages with type graphs

被引：6
作者：
Corradini, Andrea [1 ]
Koenig, Barbara [2 ]
Nolte, Dennis [2 ]
机构：
[1] Univ Pisa, Dipartimento Informat, Lungarno Pacinotti 43, I-56126 Pisa, Italy
[2] Univ Duisburg Essen, Abt Informat & Angew Kognit Wissensch, Lotharstr 65, D-47057 Duisburg, Germany
来源：
JOURNAL OF LOGICAL AND ALGEBRAIC METHODS IN PROGRAMMING | 2019年 / 104卷
关键词：
SHAPE-ANALYSIS; LOGIC;
D O I：
10.1016/j.jlamp.2019.01.005
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We investigate three formalisms for specifying 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. (C) 2019 Elsevier Inc. All rights reserved.
引用
收藏
页码：176 / 200
页数：25
相关论文
共 32 条
[11]   THE MONADIC 2ND-ORDER LOGIC OF GRAPHS .1. RECOGNIZABLE SETS OF FINITE GRAPHS [J].
COURCELLE, B .
INFORMATION AND COMPUTATION, 1990, 85 (01) :12-75
[12]  
Distefano D, 2006, LECT NOTES COMPUT SC, V3920, P287
[13]  
Ehrig H., 2006, MONO THEOR COMP SCI, DOI 10.1007/3-540-31188-2
[14]  
Ehrig Hartmut, 1979, Graph-Grammars and Their Application to Computer Science and Biology, P1, DOI [10.1007/BFb0025714, DOI 10.1007/BFB0025714]
[15]  
Habel A, 2005, LECT NOTES COMPUT SC, V3393, P293
[16]  
Habel A., 1992, LNCS, V643
[17]  
HECKEL R, 1995, ENTCS, V2
[18]  
Heindel T., 2009, THESIS
[19]   Abstractions from proofs [J].
Henzinger, TA ;
Jhala, R ;
Majumdar, R ;
McMillan, KL .
ACM SIGPLAN NOTICES, 2004, 39 (01) :232-244
[20]  
] J org~, 2015, LIPICS, V36, P160
1234