COORDINATE GRAMMARS REVISITED: GENERALIZED ISOMETRIC GRAMMARS

In a “coordinate grammar”, the rewriting rules replace sets of symbols having been given coordinates by sets of symbols whose coordinates are given functions of the coordinates of the original symbols. It was shown in 1972 that coordinate grammars are “too powerful”; even if the rules are all of finite-state types and the functions are all computable by finite transducers, the grammar has the power of a Turing machine. This paper shows that if we require the functions to be shift-invariant and the rules to be of bounded diameter, then such grammars do have a useful hierarchy of types; in fact, when we require that their sentential forms always remain connected, they turn out to be equivalent to “isometric grammars”.