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

Glenn D. Blank

Abstract

Register Vector Grammar (RVG) is a novel finite-state automaton that uses ternary feature vectors to model complex natural language syntax—such as long-distance dependencies and center-embedding—without the computational overhead of context-free grammars. By increasing functional complexity rather than memory resources, RVG achieves linear-time parsing while remaining compact enough to reflect human linguistic constraints.

Introduction

Since Noam Chomsky’s foundational work in the 1950s, the prevailing view in linguistics has been that natural languages require at least context-free power to handle structures like nested embeddings (e.g., "The cat the dog bit ran away"). However, context-free grammars (CFGs) are computationally expensive, often leading to combinatorial explosions in processing time.

Traditional Finite-State Automata (FSAs) offer the advantage of linear-time processing but are typically considered functionally simple, matching symbols by identity and changing them by replacement. To model the full breadth of natural language, a standard FSA would require an enormous, redundant state table. This paper introduces Register Vector Grammar (RVG), developed by Glenn David Blank, which aims to bridge this gap by creating a system as fast as an FSA but as expressive as more complex grammars.

Methodology: Register Vector Grammar

The core innovation of RVG is the transition from simple atomic symbols to ternary feature vectors.

Ternary Vectors and Functional Complexity

Unlike standard FSAs, RVG utilizes a vector of features where each bit can be + (on), - (off), or 2 (mask/don't care). This "match and change" mechanism allows a production to match any value in the current state and leave it unchanged via the mask value. This enables the system to maintain "memory" of long-distance constraints—such as a missing noun phrase in a wh-question—through intervening words without requiring a stack.

The Synindex and Transition Networks

The Synindex serves as a compact production table. Due to the power of masking, a single entry in the Synindex can handle numerous syntactic contexts, making the grammar significantly smaller than a traditional transition network.

Figure 1: Production table and corresponding Transition Network for a simple grammar fragment.

Multi-leveled CSSR

To manage embedding without an infinite stack, RVG employs a multi-leveled Current Syntactic State Register (CSSR). It allocates a fixed number of levels (e.g., three). When the grammar encounters depth beyond these levels, it re-uses registers. This design choice is intended to mimic human cognitive limitations in processing complex nested sentences.

Figure 4: Structure of the multi-leveled Current Syntactic State Register (CSSR) for handling embeddings.

Evaluation and Results

The RVG framework was evaluated using classic linguistic "stress tests" for English syntax, including wh-questions, center-embedding, and cross-serial dependencies.

Key Performance Metrics

  • Efficiency: On a DEC-20 computer, the RVG parser averaged approximately 5 milliseconds per lexeme.
  • Linear Time Complexity: The system is guaranteed to run in linear time relative to input length, avoiding the exponential slowdowns associated with more powerful grammar types.
  • Compactness: The RVG Synindex is remarkably small; for instance, it can reduce multiple productions for adjectives and nouns into a single production per category.
  • Reversibility: The same Synindex can be utilized for both parsing and generation.

Discussion

Blank argues that context-free power is an "idealization" not strictly necessary for realistic natural language processing, given that human center-embedding is shallow and constrained. By making the functions operating on states more complex through ternary logic, RVG maintains finite memory and linear speed. The ternary mask is essential, allowing the grammar to pass constraints across a sentence without a stack by being "oblivious" to certain features while strictly enforcing others.

Limitations and Future Work

Despite its efficiency, RVG has inherent limitations:

  • Finite Depth: It cannot handle infinitely deep recursion, placing it below context-free grammars on the Chomsky hierarchy.
  • Ambiguity: Highly ambiguous sentences can still impact performance, though "bounded parallelism" is a proposed solution.
  • Hardware Potential: Future performance gains could be realized through specialized ternary circuitry.
  • Scaling: While a substantial fragment of English was implemented, scaling to a complete, robust English grammar remains ongoing work.

Summary updated

BibTeX
@inproceedings{blank1985new,
  author = {Glenn D. Blank},
  title = {{A New Kind of Finite-State Automaton: Register Vector Grammar}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1985},
}
Figure