---
title: "A New Kind of Finite-State Automaton: Register Vector Grammar"
authors:
  - "Glenn D. Blank"
doi: ""
url: "https://ijcai.org/proceedings/1985/148"
pdf: "https://ijcai.org/proceedings/1985/0148.pdf"
venue: "Proceedings of the Ninth International Joint Conference on Artificial Intelligence"
year: 1985
pages: "749-754"
track: "Natural Language"
keywords:
---

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

Glenn D. Blank

*Proceedings of the Ninth International Joint Conference on Artificial Intelligence*, pages 749-754.

## 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.