Language Theoretic Properties of Graph Extension Languages : An Investigation of Graph Extension Grammars with Context Matching and Logic

Abstract: Graph extension grammars provide a way to define graph languages. They consist of a regular tree grammar and an algebra. The regular tree grammar generates trees, so-called derivation trees. Those are evaluated by the algebra into a set of graphs. A graph extension grammar allows two kinds of operations: disjoint unions and extension operations. A disjoint union combines two graphs into one. An extension operations extends a given graph by creating new nodes and connecting them to nodes present in the given graph. In this process, context nodes allow references in the form of edges to arbitrary nodes in the argument graph. For matching context nodes with nodes in the argument graph, there are two methods: either they are matched by their label or the target node needs to satisfy a formula. Each method yields one type of graph extension grammar, namely one with context matching and one with logic. We investigate both types of grammars regarding their language theoretic properties. For graph extension grammars with context matching we prove a pumping lemma and a variant of Parikh's theorem. We show that the path languages generated by those grammars are regular, which implies the decidability of the finiteness and emptiness problem. We prove that their language class is not closed under intersection and there are inherently ambiguous languages under some condition. For graph extension grammars we show that they can simulate Turing machines and thus their path languages can be recursively enumerable but not context-sensitive. There is no pumping lemma for those languages and they can grow exponentially or even faster. In addition to considering language theoretic properties, we improve the previously known parsing algorithm and give a characterisation of all derivable graphs.