A New Kind of Finite-State Automaton: Register Vector Grammar

Abstract

Register Vector Grammar is a new kind of f in i te -s ta te automaton that is sensitive to context—without, of course, being contextsensitive in the sense of Chomsky hierarchy. Traditional automata are functionally simple: symbols match by identi ty and change by replacement. RVG is functionally complex: ternary feature vectors (e.g. +-±--++) match and change by masking ( + matches but does not change any value). Functional complexity—as opposed to the computat ional complexity of non-finite memory—is well suited for modelling multiple and discontinuous constraints. RVG is thus very good at handling the permutations and dependencies of syntax (wh-questions are explored as example). Because center-embedding in natural languages is in fact very shallow and constrained, context-free power is not needed. RVG can thus be guaranteed to run in a small l inear time, because it is FS, and yet can capture generalizations and constraints that functionally simple FS grammars cannot.