TL;DR
This paper proposes a novel mixed prefix-postfix notation for representing the constituent structures of natural language sentences. This representation aims to be parsable by finite-state devices, even for sentences with some degree of center embedding, by reflecting how humans might process them.
What Problem Does This Paper Address?
Parsing natural language sentences, especially those with nested structures (center embedding), has historically been a challenge for computational models. While context-free grammars can describe these structures, parsing them efficiently often requires more complex mechanisms than simple finite-state automata. The authors observe that human parsing seems to handle sentences with a limited degree of center embedding effectively. They aim to bridge this gap by developing a representation of syntactic structure that is both informative and amenable to finite-state parsing, potentially mirroring human cognitive processes.
Methods
The core of the paper is the development of an "affix grammar" system. This system transforms a standard context-free phrase-structure grammar (CFPSG) into a new grammar that directly generates "affixed strings." These affixed strings represent the constituent structures. The key innovation lies in how these strings are constructed:
- Mixed Prefix-Postfix Notation: Instead of full bracketing, they use prefixes for right-recursive structures and postfixes for left-recursive structures. This is achieved by selectively omitting brackets.
- Finite-State Parsability: The resulting affixed strings are designed to be parsable by finite-state transducers. This is achieved by ensuring that the affixed strings themselves exhibit limited center embedding.
- Principles for Affix Choice: The paper proposes four principles to guide the decision of whether to use a prefix or a postfix for a given grammatical rule. These principles are based on:
- Assigning lexical items to categories.
- Predicting constituent identity from the leftmost daughter (specifier or head).
- Predicting constituent identity from a left sister.
- Using postfixes in all other cases.
These principles are applied to transform a given CFPSG into an affix grammar that generates the structural descriptions.
Datasets
Not discussed in the paper. The paper focuses on theoretical linguistic constructs and grammar transformations rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Finite-State Parsing of Center-Embedded Structures: The central idea is that by carefully designing a representation of syntactic structure, even sentences with center embedding can be parsed by finite-state devices. This challenges the traditional view that center embedding inherently requires pushdown automata.
- Mimicking Human Parsing: The proposed affix notation and the principles for choosing prefixes/postfixes are motivated by the idea of reflecting how humans might parse sentences, making decisions as early as possible based on available information.
- The "Efficient Finite-State Parser Hypothesis": The authors conjecture that natural language structures are such that representations can be assigned by finite-state parsers that identify constituents quickly. This hypothesis suggests a fundamental property of natural languages themselves.
- Transforming Grammars: The paper provides a systematic method for transforming a standard CFPSG into an affix grammar that generates these specialized representations.
Key Results
The paper demonstrates through examples (G1 and G2 grammars) how their affix grammar system can generate affixed strings that represent constituent structures. They show that these affixed strings, while derived from grammars that might produce center-embedded structures, themselves exhibit limited center embedding, making them parsable by finite-state devices. The paper also illustrates how their principles lead to a single, preferred interpretation for ambiguous sentences, aligning with human intuition.
Limitations and Future Work
- Limited Empirical Evaluation: The paper is largely theoretical and does not present quantitative results from parsing actual natural language corpora. The focus is on the theoretical possibility and the design of the representation.
- Conjecture of the Hypothesis: The "Efficient Finite-State Parser Hypothesis" is presented as a conjecture, requiring further empirical validation.
- Future Work: The authors suggest leaving further demonstrations of the system's capabilities as exercises for the reader, implying that more complex linguistic phenomena could be explored. They also hint at the need for further discussion on the proposed system of representation.
Summary updated