On the power of local graph expansion grammars with and without additional restrictions

We study graph expansion grammars, a type of graph grammar that has recently been introduced with motivations in natural language processing. Graph expansion generalizes the well-known hyperedge replacement. In contrast to the latter, the former is able to generate graph languages of unbounded treew...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2024-11, Vol.1015, p.114763, Article 114763
Main Authors: Drewes, Frank, Stade, Yannick
Format: Article
Language:English
Subjects:
Computer Science
datalogi
Generative power
Graph expansion grammar
Graph grammar
Hyperedge replacement
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study graph expansion grammars, a type of graph grammar that has recently been introduced with motivations in natural language processing. Graph expansion generalizes the well-known hyperedge replacement. In contrast to the latter, the former is able to generate graph languages of unbounded treewidth, like the set of all graphs. In an earlier paper, the complexity of the membership problem of the generated languages was studied, the main result being a polynomial parsing algorithm for local DAG expansion grammars (there called local DAG expansion grammars), a subclass of graph expansion grammars that generates directed acyclic graphs. Here, we study the generative power of local graph expansion grammars. While they, unrestricted, are able to simulate Turing machines, we identify natural restrictions that give rise to a pumping lemma and ensure that the generated languages have regular path languages as well as a semi-linear Parikh image.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2024.114763