A Complexity-Theoretic Study of some Fragments of English

Prof. Ian Pratt-Hartmann ( School of Computer Science, University of Manchester )

By a fragment of a natural language we mean a subset of that language equipped with a semantics that translates its sentences into some formal system such as first-order logic. The familiar concepts of satisfiability and entailment can be defined for any such fragment in a natural way. The question then arises, for any given fragment of a natural language, as to the computational complexity of determining satisfiability and entailment within that fragment.  We present a series of fragments of English whose satisfiability problems range in complexity from NLOGSPACE-complete to r.e.-complete, showing how different combinations of grammatical constructions conspire to yield  the observed complexity. We also discuss some proof-theoretical reflexes of these complexity results, in terms of the existence (or non-existence) of syllogism-like systems of inference rules for the fragments in question.  Thus, this talk constitutes a study in how to investigate the computational and logical properties of grammatical constructions in natural language.