Tree-Verifiable Graph Grammars - IMAG
Conference Papers Year : 2024

Tree-Verifiable Graph Grammars

Radu Iosif

Abstract

Hyperedge-Replacement grammars (HR) have been introduced by Courcelle in order to extend the notion of context-free sets from words and trees to graphs of bounded tree-width. While for words and trees the syntactic restrictions that guarantee that the associated languages of words resp. trees are regular - and hence, MSO-definable - are known, the situation is far more complicated for graphs. Here, Courcelle proposed the notion of regular graph grammars, a syntactic restriction of HR grammars that guarantees the definability of the associated languages of graphs in Counting Monadic Second Order Logic (CMSO). However, these grammars are not complete in the sense that not every CMSO-definable set of graphs of bounded tree-width can be generated by a regular graph grammar. In this paper, we introduce a new syntactic restriction of HR grammars, called tree-verifiable graph grammars, and a new notion of bounded tree-width, called embeddable bounded tree-width, where the later restricts the trees of a tree-decomposition to be a subgraph of the analyzed graph. The main property of tree-verifiable graph grammars is that their associated languages are CMSO-definable and that they have bounded embeddable tree-width. We show further that they strictly generalize the regular graph grammars of Courcelle. Finally, we establish a completeness result, showing that every language of graphs that is CMSO-definable and of bounded embeddable tree-width can be generated by a tree-verifiable graph grammar.
Fichier principal
Vignette du fichier
LPAR_2024_pages_165-180.pdf (599.33 Ko) Télécharger le fichier
Origin Publisher files allowed on an open archive

Dates and versions

hal-04763023 , version 1 (06-11-2024)

Identifiers

Cite

Mark Chimes, Radu Iosif, Florian Zuleger. Tree-Verifiable Graph Grammars. Proceedings of 25th Conference on Logic for Programming, Artificial Intelligence and Reasoning, May 2024, Mauritius, Mauritius. pp.165-148, ⟨10.29007/8l13⟩. ⟨hal-04763023⟩
0 View
0 Download

Altmetric

Share

More