Alasdair Urquhart - Complexity problems for substructural logics

Substructural logics are typically obtained by restricting the structural rules of contraction and weakening in propositional logic. They include logics (such as relevance logics) that were originally investigated for philosophical reasons, and logics such as linear logic that were inspired by ideas from category theory and computer science.

A surprising feature of these logics is that the simple omission of the structural rules leads in many cases to a drastic increase in complexity. For example, propositional linear logic is undecidable. In other cases, such as linear logic with weakening, the propositional logic is decidable, but of a high intrinsic complexity. In this talk, I shall report on some recent results on the complexity of decidable substructural propositional logics, and explain some of the open questions in the area.