Mathematical Theory of Recursive Symbol Systems

This paper introduces a new type of graph grammar for representing recursively structured two-dimensional geometric patterns, for the purposes of syntactic pattern recognition. The grammars are noise-tolerant, in the sense that they can accommodate patterns that contain pixel noise, variability in the geometric relations between symbols, missing parts, or ambiguous parts, and that overlap other patterns. Geometric variability is modelled using fleximaps, drawing on concepts from the theory of Lie algebras and tensor calculus. The formalism introduced here is intended to be generalisable to all problem domains in which complex, many-layered structures occur in the presence of noise.