Non-Confluent NLC Graph Grammar Inference by Compressing Disjoint Subgraphs
| dc.creator | Blockeel, Hendrik | |
| dc.creator | Brijder, Robert | |
| dc.date | 2009-01-30 | |
| dc.date.accessioned | 2026-07-07T12:36:30Z | |
| dc.date.available | 2026-07-07T12:36:30Z | |
| dc.description | Grammar inference deals with determining (preferable simple) models/grammars consistent with a set of observations. There is a large body of research on grammar inference within the theory of formal languages. However, there is surprisingly little known on grammar inference for graph grammars. In this paper we take a further step in this direction and work within the framework of node label controlled (NLC) graph grammars. Specifically, we characterize, given a set of disjoint and isomorphic subgraphs of a graph $G$, whether or not there is a NLC graph grammar rule which can generate these subgraphs to obtain $G$. This generalizes previous results by assuming that the set of isomorphic subgraphs is disjoint instead of non-touching. This leads naturally to consider the more involved ``non-confluent'' graph grammar rules. | |
| dc.description | 12 pages, 1 figure | |
| dc.identifier | https://arxiv.org/abs/0901.4876 | |
| dc.identifier | http://arxiv.org/abs/0901.4876 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/218113 | |
| dc.subject | Machine Learning | |
| dc.subject | Discrete Mathematics | |
| dc.title | Non-Confluent NLC Graph Grammar Inference by Compressing Disjoint Subgraphs | |
| dc.type | text |