Inclusion, Disjointness and Choice: The Logic of Linguistic Classification

Bob Carpenter, Carl PollardACL 1991 · DOI

Abstract

Linguistic theories often rely on complex taxonomies to categorize grammatical features, yet these systems frequently lack a unified formal foundation. This paper proposes a rigorous algebraic framework based on lattice theory to model linguistic classification hierarchies. By defining categories through inclusion (ISA) and disjointness (ISNOTA) relations, the authors demonstrate how disparate formalisms like Head-driven Phrase Structure Grammar (HPSG) and systemic choice networks can be reconciled within a single declarative semantics.

Introduction

Linguistic classification is inherently multi-dimensional. A single lexical item might simultaneously be categorized as a "noun," "singular," and "masculine." Traditionally, these overlapping taxonomies have been represented using diverse graphical notations or specialized grammar formalisms. However, the lack of a "stripped-down" logical framework has made it difficult to handle multiple inheritance, ensure consistency across disjoint categories, and distinguish between open and closed-world assumptions (e.g., whether a set of genders is exhaustive or extensible).

Methods: The Algebraic Foundation

The authors employ Lattice Theory to construct their framework, starting with a simple inheritance network. This network is built from basic concepts connected by two primary primitives:

  • ISA (Inclusion): Indicates that one concept is a sub-type of another.
  • ISNOTA (Disjointness): Indicates that two concepts are mutually exclusive.
A basic inheritance network illustrating ISA (arrows) and ISNOTA (crossed line) relations between concepts.

From these primitives, the authors derive Conjunctive Concepts by generating a "meet semilattice." In this structure, each node represents a consistent combination of basic concepts. If a combination involves two concepts linked by an ISNOTA relation, the system identifies the result as inconsistent and filters it out. To handle "either/or" scenarios, this semilattice is embedded into a Distributive Lattice, allowing for the representation of arbitrary disjunctions (e.g., "a noun that is either masculine or feminine").

Key Insights: Unifying Linguistic Formalisms

The most significant contribution of this work is the demonstration that seemingly different linguistic notations are functionally equivalent under this logic. For instance, the "partitions" used in HPSG—where a category is split into exhaustive, mutually exclusive sub-categories—can be perfectly modeled using ISA and ISNOTA primitives.

A systemic choice network for agreement (agr) features, showing choices for number (num), person (per), and gender (gen).

Furthermore, the authors provide a mathematical mapping for Systemic Choice Networks (as seen in Figure 4). They prove that the concept of "choice" in systemic linguistics is logically equivalent to "disjointness" in their framework. This unification allows for automatic inconsistency detection; the system can deduce when a combination of features is logically impossible based solely on the network's structure.

Results and Implications

The paper provides rigorous proofs for several key properties:

  1. Semilattice Formation: The set of conjunctive concepts, when ordered by specificity, forms a valid meet-semilattice.
  2. Closed-World Reasoning: The authors introduce a "closed concept" constraint that identifies a parent category exactly with the disjunction of its known children, effectively barring "hidden" types in a grammar.
  3. Complexity Management: By using distributive lattices, any complex linguistic concept can be factored into a "disjunctive normal form." This makes the logic computationally manageable for unification-based grammars, even as the number of potential combinations grows.

Limitations and Future Directions

While the framework provides a robust "front-end" for classification, it does not yet cover "role-based" or "attribute-based" reasoning (e.g., constraints on the subject of a sentence). The authors suggest that this logic must be integrated into larger systems, such as feature structures, to handle full-scale grammatical constraints. Additionally, while the logic is sound, the exponential growth of disjunctive concepts in massive real-world grammars remains a challenge for future implementation efficiency.

Summary updated

BibTeX
@inproceedings{carpenter1991inclusion,
  author = {Bob Carpenter and Carl Pollard},
  title = {{Inclusion, Disjointness and Choice: The Logic of Linguistic Classification}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1991},
  doi = {10.3115/981344.981346},
}
Figure