Connectionist learning of regular graph grammars

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 Carte sian grid. This work is intended as a case study in connectionist symbol pr ocessing and geometric concept formation. A grammar is represented by a sel f-configuring connectionist network that is analogous to a transition diagr am except that it can deal with graph grammars as easily as string grammars . Learning starts with a trivial grammar, expressing no grammatical knowled ge, which is then refined, by a process of successive node splitting and me rging, 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 repre senting and manipulating recursive structures.