The Elimination of Grammatical Restrictions in a String Grammar of English

M. Salkoff, N. SagerCOLING 1967

TL;DR

This paper explores the possibility of creating a "restrictionless" string grammar for English, where all grammatical dependencies are encoded within the structure of elementary strings rather than through separate rules. The authors demonstrate that such a grammar can be constructed by transforming an existing restricted string grammar, leading to a more unified and potentially more efficient linguistic representation.

What Problem Does This Paper Address?

Traditional linguistic grammars, including string grammars, often rely on explicit restrictions or rules to capture grammatical dependencies. For instance, in English, subject-verb agreement (e.g., "the boy eats" vs. "the boys eat") requires a rule that links the number of the noun to the form of the verb. This paper investigates whether these dependencies can be entirely internalized within the grammar's fundamental units – elementary strings – thereby eliminating the need for separate restriction rules. The goal is to create a grammar where all elements that are grammatically related appear within the same elementary string, simplifying the overall structure and potentially facilitating computational processing.

Methods

The core method involves transforming an existing, restricted string grammar into a restrictionless one. This transformation is achieved through two main strategies:

  • Re-formulating Linguistic Strings: Grammatical dependencies are addressed by ensuring that grammatically related elements (like subject and verb) are part of the same elementary string. Any sequences that previously existed between these elements are re-categorized as adjuncts of that string. This approach aims to embed dependencies directly into the string structure.
  • Eliminating Restrictions:
    • Type A Restrictions (e.g., related to tense and iterable sequences): These are eliminated by defining new grammar strings that incorporate the previously restricted options. Essentially, if a restriction prevented a specific option from being chosen, a new string is created that contains all options except the restricted one.
  • Type B Restrictions (e.g., sub-category agreement): These are eliminated by replacing general word categories with more specific sub-categories. For example, instead of a general "noun" category, the grammar might use "singular noun" and "plural noun" to implicitly handle agreement. New adjunct strings are also defined to manage specific sub-category behaviors.

The paper also outlines a computer-implemented generalized grammar string definition that uses nested strings and options, with associated tests (restrictions). The process of eliminating restrictions aims to simplify this structure.

Datasets

Not discussed in the paper. The paper focuses on theoretical linguistic grammar construction and does not present empirical evaluation on specific datasets.

Key Insights and Ideas

  • Grammatical Dependencies as Structural Properties: The paper's central idea is that grammatical dependencies, often treated as external rules, can be inherent structural properties of linguistic strings. This shifts the focus from "rules about strings" to "strings that embody rules."
  • Unified Representation: By eliminating restrictions, the grammar becomes more unified. All grammatical relationships are expressed through string composition and adjunction, potentially leading to a cleaner and more conceptually integrated linguistic model.
  • Computational Implications: The authors suggest that a restrictionless grammar could be more amenable to computational analysis. While the elimination of restrictions increases the number of strings, it might simplify the parsing process by removing the need to check separate restriction rules.
  • Equivalence to BNF: The restrictionless string grammar is shown to be equivalent to a Backus-Naur Form (BNF) grammar, suggesting a strong theoretical link between string grammar and context-free grammars.

Key Results

The paper demonstrates that a restrictionless string grammar for English can be constructed by transforming an existing restricted grammar. The authors estimate that this process increases the number of grammar strings by about an order of magnitude (e.g., from ~200 to ~2000 strings in their example). They argue that this increase is manageable and suggests potential for practical applications, such as real-time sentence analysis.

Limitations and Future Work

  • Conjunctional Strings: The initial development of the restrictionless grammar excludes conjunctional strings. The authors estimate that their inclusion would increase the grammar's size by a factor of about 5.
  • Size Increase: While the increase in the number of strings is considered manageable, it is still a significant increase. The paper acknowledges this as a cost of eliminating restrictions.
  • Future Work: The procedure for eliminating restrictions is also presented as an algorithm for introducing further grammatical refinements into the restrictionless grammar. This suggests that the framework is extensible and can accommodate more complex linguistic phenomena. The authors also propose that this restrictionless grammar could be useful in adding English-language features to programming languages written in BNF.

Summary updated

BibTeX
@inproceedings{salkoff1967elimination,
  author = {M. Salkoff and N. Sager},
  title = {{The Elimination of Grammatical Restrictions in a String Grammar of English}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1967},
}
Figure