📄 Finite State Reasoning for Presupposition Satisfaction

Summary

The paper asks how speakers decide whether a presupposition holds in context. Classic accounts, such as Karttunen's entailment-based view and Beaver & Krahmer's partial logic, assume some process computes what a context entails. That task can be expensive or even undecidable. Examples include factives over the halting problem, optimal checkers moves, and unknown nonce words like garchank. Yet people judge easy cases at once, for example "Taylor is a bird and Sam knows Taylor is a mammal."

Collard proposes that intuitive presupposition checking covers exactly the reasoning that regular sets of possible worlds can express. He extends Rooth's (2017) finite state semantics to a three-valued system (T/F/N). Each sentence compiles to a finite state machine over world strings, and presupposition failure falls out as undefined worlds. He defines operators for factives and for the uniqueness presupposition of the singular definite article, and releases a sample implementation on GitHub.

The result is a formalism that cannot run into undecidable problems. It predicts which presuppositions people evaluate effortlessly and which they leave unresolved.

Key points

• Truth values: the system has three, true, false and neither, following Frege and Belnap's naming. A sentence's denotation separates worlds where it is true, false or undefined.
• Machinery: it builds on Rooth (2017) and the finite state calculus of Mohri & Sproat and Kempe & Karttunen. FOMA (Hulden, 2006) serves as a usable toolkit.
• Uniqueness: the definite article's uniqueness requirement uses worlds with multiple centers or pericenters and a rebinding operation (REBIND / DOREBIND). It is built from TRUEWORLDS, UNDEFINEDWORLDS and VALUE.
• Adjacency prediction: in a one-dimensional world model, something adjacent to a dog and a rabbit cannot also be next to a penguin. A factive presupposing that third neighbour therefore fails, which matches intuitions about theater seating.
• Limits and closure: non-regular sets (e.g. "equal number of cats and dogs") are representable only when world size is bounded. Context-free languages lack closure under intersection, and recursively enumerable languages lack closure under complement. Both closures are needed for reasoning.
• Code: github.com/thorsonlinguistics/finite-state-presupposition.

Interesting ideas

• I1. Treat "easy" inference as whatever a deliberately weak, guaranteed-terminating formalism can compute, and leave everything harder as an unresolved but well-described condition rather than guessing.
• I2. Keep a third value, "neither", whenever a sentence's precondition fails, so felicity problems stay distinct from falsehood.
• I3. Detect clashes between a factive complement and prior discourse through lexical axioms (bird excludes mammal), not just through literal p versus not-p.
• I4. Model uniqueness of "the X" by checking whether some other individual could equally satisfy X in the same world.
• I5. Use small spatial or structural constraints, such as a row allowing at most two neighbours, to derive contradictions with minimal machinery.

For Mova

How these ideas could serve Mova, our small open language model — its files, stages and tests:

• I1 (world): Presupposition and consistency checks in the text world could run under a bounded, decidable reasoner, recording "undetermined" instead of searching indefinitely.
• I2 (answer): Readers answering questions about tales could reply "the question presupposes something false" instead of yes/no when an entity or fact is missing.
• I3 (frames): When prag sees know/regret frames, it could check the complement against WordNet-derived disjointness and flag infelicity or a needed accommodation.
• I4 (world): Coreference and definite resolution could flag a "the X" as failing when the world holds zero or several matching entities.
• I5 (learn): Such hand-checkable constraint cases could serve as negative-control test items to verify that the world builder rejects impossible configurations.