Semantics of the Barwise sentence: insights from expressiveness, complexity and inference

Dariusz Kalociński, Michał Tomasz GodziszewskiLinguistics 2018 · DOI

Abstract

This paper investigates the semantic properties of "Barwise sentences"—complex natural language constructions involving comparative quantifiers. By analyzing these sentences through the lenses of generalized quantifier theory, finite model theory, and computational complexity, we demonstrate a fundamental tension between linguistic informativeness and cognitive tractability. We show that while the most precise "strong" interpretations of these sentences are computationally intractable (NP-complete) and not first-order definable, humans likely utilize "weak" first-order approximations. This suggests that linguistic ambiguity serves as an evolutionary strategy to balance communicative power with cognitive constraints.

Introduction

In his seminal 1979 work, logician Jon Barwise identified a class of natural language constructions that challenge standard semantic frameworks. A classic example is: "The richer the country, the more powerful some of its officials." These sentences describe a relationship between two partially ordered sets—in this case, countries ordered by wealth and their respective officials ordered by power.

The central problem lies in how we interpret the "similarity" between these orders. Does the sentence imply a simple existence of a more powerful official for any richer country (a weak reading), or does it require a structural mapping, such as a homomorphism or embedding, between the entire sets of officials (a strong reading)?

The Challenge of Expressiveness

A key question in formal semantics is whether a construction can be expressed within first-order logic (FO). The authors utilize Hanf-locality and other tools from finite model theory to prove that "strong" readings of Barwise sentences—those requiring structural similarity quantifiers—are not FO-definable over finite models.

This result confirms Barwise’s original intuition: these sentences possess an inherent logical complexity that transcends elementary logic. They function as polyadic generalized quantifiers that capture global properties of models, rather than just local relationships between individuals.

Computational Complexity and the PTIME-Cognition Hypothesis

To understand the cognitive plausibility of these readings, the authors analyze the computational complexity of verifying them. According to the PTIME-Cognition Hypothesis, humans can only efficiently process and verify linguistic constructions that belong to the complexity class P (polynomial time).

The findings reveal a sharp dichotomy:

  1. Weak Readings: These are first-order approximations that are computationally tractable (PTIME).
  2. Strong Readings: Most structural interpretations, such as those requiring injective homomorphisms or embeddings, are NP-complete.
Figure 1: A model illustrating the distinction between strong and weak readings. In this specific configuration, the strong reading is false, while the weak reading remains true.

The NP-completeness of strong readings suggests that they are likely too complex for direct verification in large-scale real-world scenarios. This leads to a paradox: why does language support meanings that are "too hard" to compute?

The Role of Ambiguity and Inference

The authors propose that the apparent ambiguity of Barwise sentences is not a defect but a functional feature. They extend the Strong Meaning Hypothesis (SMH)—which posits that listeners prefer the strongest possible interpretation—into a Ramified SMH. This version suggests that we prefer the strongest meaning that is also cognitively manageable.

Furthermore, the paper highlights the role of indirect verification. Even if a sentence is NP-complete to verify in the general case, humans can use inference patterns to confirm its truth. For instance, if we know a "maximal" official exists in a richer country who is more powerful than any official in a poorer country, the truth of the Barwise sentence follows immediately without the need for a complex combinatorial search.

Conclusion

The study of Barwise sentences reveals a sophisticated interplay between logic and cognition. The conflicting pressures of communication (which favors informative, strong readings) and cognition (which favors efficient, weak readings) result in a stable, albeit ambiguous, linguistic construction. This suggests that the evolution of natural language semantics is deeply constrained by the computational limits of the human mind.

Summary updated

Abstract

In this paper, we study natural language constructions which were first examined by Barwise: The richer the country, the more powerful some of its officials. Guided by Barwise’s observations, we suggest that conceivable interpretations of such constructions express the existence of various similarities between partial orders such as homomorphism or embedding (strong readings). Semantically, we interpret the constructions as polyadic generalized quantifiers restricted to finite models (similarity quantifiers). We extend the results obtained by Barwise by showing that similarity quantifiers are not expressible in elementary logic over finite models. We also investigate whether the proposed readings are sound from the cognitive perspective. We prove that almost all similarity quantifiers are intractable. This leads us to first-order variants (weak readings), which only approximate the strong readings, but are cognitively more plausible. Driven by the question of ambiguity, we recall Barwise’s argumentation in favour of strong readings, enriching it with some arguments of our own. Given that Barwise-like sentences are indeed ambiguous, we use a generalized Strong Meaning Hypothesis to derive predictions for their verification. Finally, we propose a hypothesis according to which conflicting pressures of communication and cognition might give rise to an ambiguous construction, provided that different semantic variants of the construction withstand different pressures involved in its usage.
BibTeX
@inproceedings{kalocinski2018semantics,
  author = {Dariusz Kalociński and Michał Tomasz Godziszewski},
  title = {{Semantics of the Barwise sentence: insights from expressiveness, complexity and inference}},
  booktitle = {Linguistics},
  year = {2018},
  doi = {10.1007/s10988-018-9231-5},
}
Figure