Mathematical Theory of Recursive Symbol Systems

This paper introduces a new type of graph grammar for representing recursively struc tured twodimensional geometric patterns, for the purposes of syntactic pattern recogni tion. The grammars are noisetolerant, in the sense that they can accommodate patterns that contain pixel noise, variability in the geometric relations between symbols, miss ing 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 do mains in which complex, manylayered structures occur in the presence of noise