Connectionist learning of regular graph grammars

Fletcher

Abstract

This paper presents a new connectionist approach to grammatical inference. Using only positive examples, the algorithm learns regular graph grammars, representing two-dimensional iterative structures drawn on a discrete Cartesian grid. This work is intended as a case study in connectionist symbol processing andgeometric concept formation. A grammar is represented by a self-configuring connectionist network that is analogous to a transition diagram except that it can deal with graph grammars as easily as string grammars. Learning starts with a trivial grammar, expressing nogrammatical knowledge, which is then refined, by a process of successive node splitting and merging, into a grammar adequate to describe the population of input patterns. In conclusion, I argue that the connectionist style of computation is, in some ways, better suited than sequential computation to the task of representing and manipulating recursive structures.

Citation

Fletcher. (2001). Connectionist learning of regular graph grammars. Connection science, 127 - 188. https://doi.org/10.1080/09540090110072327

• Publication Date: Jun 1, 2001
• Journal: Connection Science
• Print ISSN: 0954-0091
• Publisher: Taylor and Francis
• Pages: 127 - 188
• DOI: https://doi.org/10.1080/09540090110072327
• Keywords: grammatical inference; graph grammars; neural networks; parallel parsing; regular grammars; stochastic grammars; symbol processing; unsupervised learning
• Publisher URL: https://doi.org/10.1080/09540090110072327