# A Complexity-Theoretic Study of some Fragments of English

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

- 14:00 9th March 2012 ( week 8, Hilary Term 2012 )Lecture Theatre B (LTB)

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.