Model Generation for Natural Language Interpretation and Analysis

1 Motivation
1.1
1.2
The Subject of This Volume
Interpretation, Analysis, Computation
1.2.1
1.2.2
1.2.3
Interpretation
Analysis
Computation
1.3 Acknowledgments

Part I Logics
2 Model Generation

Introduction
Preliminaries
Topics

Models and Decidability
Herbrand Models
Finite Models
Representations
Minimality
Subset Minimality
Domain Minimality
Predicate-Specific Minimality
Enumeration
2.3.10
2.3.11
Model Enumeration with Theorem Provers
Enumeration with Finite Model Generators
2.4 Methods

Analytical Tableaux
Ground Tableaux
Free Variable Tableaux
Positive Unit Hyper-resolution
A Method Complete for Finite Satisfiability

X Table of Contents

The Davis-Putnam Procedure
Calculus and Procedure
Branches as Models
Efficiency
2.5 Related Work

3 Higher-Order Model Generation
3.1 The in Linguistics

Composition of Meaning
Quantification in Natural Language
Quantifiers as Higher-Order Expressions
First-Order Limitations
A Motivation for a New Kind of Logic
3.2 Higher-Order Logic

Syntax
Types
Terms
Semantics
Functional Interpretations
Logical Constants
Defining a Logic
Standard Frames and Generalised Interpretations
Model Generation for Generalised Frames?
Equivalency for Higher-Order Atoms
Function Domains and Quantification
3.3 A Fragment of Higher-Order Logic

Syntax
Semantics
Constant Frames
Interpretations and Denotations
An Logic
Connectives
Quantifiers
Definitions
Equality
3.4 Constructing Models

Determining Models Intelligently
Formulas as Constraints
Solving Constraints
Translating Formulas into Constraints
An Example
Properties of the Translation
Refutation Soundness
Completeness for Satisfiability
Enumerating Models

Table of Contents XI
4 Minimal Model Generation

Preliminaries
Decidability of Local Minimality

Part II Linguistics
5 The Analysis of Definites
5.1 Introduction

The Semantics of Definite Descriptions
Definites and Deduction
How Models Interpret Sentences
Discourse Models
Models for Definites
Uniqueness and Lots of Rabbits
5.2 Some Representations

Simple Cases
Donkeys, Context Sets, and Anaphoric Use
Quantifiers and Donkey Sentences
Context Set Restrictions
The Treatment of Names
Restrictions with Knowledge
Implicit Knowledge and Accommodation
Bridging
Simple Cases Revisited
Non-resolvable Anaphora in DRT
Definites Are Not Anaphora
Non-existence
5.3 What We Have Learned so Far
6 Reciprocity

Introduction
Exploring the Meaning of Each Other

Reciprocals for Larger Groups
Classifying Reciprocal Meaning
Strong Reciprocity
One-Way Weak Reciprocity
Inclusive Alternative Ordering
Intermediate Reciprocity
Intermediate Alternative Reciprocity
Strong Alternative Reciprocity
Parameterisation

The Landscape of Reciprocity
Parameterised Definitions
Interpreting Reciprocals

XII Table of Contents

The Strongest Meaning Hypothesis
A Counter-Example
The SMH Does Not Compute (Yet)
6.3 Inference to Best Reciprocal Meaning

To Strong Meaning through Minimality
Predicate Minimisation
A Logical Encoding of Less Is More
A First Attempt at Computation
First Method: Minimality by Proof
Second Method: Minimality by Bounded Search
Third Method: A Two-Stage Combination
An Example
Conservative Minimality
6.4 Experiments

Pitchers and Pearls
The Boston Pitchers
Pearls
Measles
Marriages
6.5
6.6
Loose Ends
How We Can Understand Each Other
7 Abduction
7.1 What Is Abduction?
7.1.1 A Formal Definition of Abduction
7.2 Models for Anaphora Resolution

Chasing the Criminal
Explaining Resolutions
Discussion
Incremental Inference instead of Generate-and-Test
An Alternative by Conservative Minimality
7.3 Weighted Abduction

Logic Programming and Abduction
Abductive Explanations
Weights and Costs
Applications
Definite Reference
Composite Noun Phrases
Resolving Ambiguity
Discussion
Similarities
Differences and Comparison

Table of Contents XIII
8 Implementation
8.1
8.2
8.3
Introduction
System Architecture
The Syntax
8.3.1
8.3.2
8.3.3
8.3.4
8.3.5
Logical Constants
Formulas
Problem Specifications
A Small Example
Definitions
8.4 The Semantics
8.4.1
8.4.2
8.4.3
8.4.4
8.4.5
8.4.6
Logic Definition Structures
Propagator Procedures
Connectives
Monadic Quantifiers
Diadic Quantifiers
The Translation
8.5 Proof Engines and Controlling Search
8.5.1
8.5.2
Proof Engines
Search
8.6 System Performance

Identifying Single Solutions
KIMBA as a Propositional Theorem Prover
Generating Minimal Models
9 Conclusion

Why Inference Is Worth the Effort
Contributions
Models as Meaning
A Some Example Problems
A.1
A.2
The Job Puzzle
Reciprocals: The Boston Pitchers
References