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

Abstract

Register Vector _ Grammar is a new kind of finite-state 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 identity 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 computational complexity of non-finite memory--is well sui ted for modeHing 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 shallCM and constrained, context-free power is not needed. RVG can thus be guaranteed to run in a small linear time, because it is FS, and yet can capture generalizations and constraints that functionally simple FS grammars cannot.