| Graph grammars have been studied for applications in computer science as they have higher dimensionality over traditional one-dimensional string grammars. A problem related to the higher dimensionality is the complexity in creating grammar rules that are used in the parsing process--particularly when they are context-sensitive. The high relative cost in time and effort over string grammars to craft effective graph grammar rules has limited much of their acceptance in computing. However, through the use of an induction process to analyze sample graph structures, an automated production of viable graph grammar rules may shorten the final design time of a target grammar. In addition, structural insight into the graph system may be provided by induced graph grammar rules. As a data analysis tool, the induction process can be used on a wide spectrum of graph data. The induced production rules suggest relationships (or patterns) that may otherwise be difficult to find. Furthermore, induced context-sensitive productions expose intra-relational information. This dissertation introduces a context-sensitive graph grammar induction process for overlapping instances of a subgraph under examination, proposes applications for using machine generated graph grammar rules, and considers some implications of the induction-parsing loop for machine learning. |
