Syntactic Analysis by Local Grammars Automata: an Efficient Algorithm

Mehryar MohriarXiv 1994 · arXiv

Introduction: The Challenge of Linguistic Ambiguity

Natural language processing (NLP) is inherently difficult due to the multi-faceted ambiguity of words. A single token like "this" can function as a determiner, a pronoun, or an adverb depending on its context. In computational linguistics, these possibilities are often modeled as a "text automaton"—a graph where every path represents a potential interpretation of a sentence.

Figure 1: A text automaton representing various possible syntactic interpretations of a sentence segment.

The core problem addressed in this research is how to efficiently "prune" this graph. By applying "local grammars"—sets of rules that define valid or forbidden word sequences—we can eliminate paths that violate linguistic constraints, thereby reducing ambiguity.

Methodology: Adapting Aho-Corasick for Automata

The author proposes a two-stage algorithmic framework to solve this pruning problem:

  1. Grammar Construction ($G_3$): The paper adapts the Aho-Corasick string-matching algorithm to the domain of finite-state automata. By introducing a "failure function," the grammar automaton can efficiently handle transitions without an explicit state explosion. If the automaton cannot follow a specific transition, it defaults to a state representing the longest proper suffix of the current path that is also a prefix of a valid grammar sequence.
  2. Text Application ($G_4$): The text automaton ($G_1$) is traversed simultaneously with the grammar automaton. Paths in the text that reach a "forbidden" state in the grammar are discarded.
Figure 4: A local grammar automaton enforcing positive constraints, such as gender and number agreement.

The algorithm is versatile enough to handle both negative constraints (forbidden sequences) and positive constraints (obligatory sequences). For instance, Figure 4 illustrates how an automaton can enforce gender and number agreement between determiners and nouns, a classic example of a positive local grammar rule.

Key Insights and Results

The research highlights that syntactic disambiguation can be treated as a set-intersection problem between two automata. By utilizing failure functions, the author avoids the exponential complexity typically associated with determinizing non-deterministic automata over large alphabets.

Performance Metrics: * Complexity: Building the grammar automaton is linear, $O(|V| + |E|)$, while application to text is roughly quadratic in the worst case but highly efficient in practice. * Empirical Success: In tests, a 290-state grammar applied to an 18,000-state text automaton reduced the output to just 340 states. * Speed: On 1994-era hardware, processing large-scale French linguistic constraints took approximately 10 minutes, a significant achievement for the time.

Limitations and Future Directions

While highly effective for local constraints, the algorithm assumes the grammar automaton is acyclic. It does not currently handle recursive structures or long-distance dependencies that require a global understanding of sentence structure. Future work could involve integrating these efficient matching algorithms into broader pattern-recognition systems where input data is represented as a set of hypotheses rather than a linear string.

Summary updated

Abstract

Local grammars can be represented in a very convenient way by automata. This paper describes and illustrates an efficient algorithm for the application of local grammars put in this form to lemmatized texts.
BibTeX
@misc{mohri1994syntactic,
  author = {Mehryar Mohri},
  title = {{Syntactic Analysis by Local Grammars Automata: an Efficient Algorithm}},
  year = {1994},
  eprint = {cmp-lg/9407002},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/cmp-lg/9407002},
}
Figure