next up previous
Next: Franck van Breugel - Up: Applied Logic / Logique Previous: Robert Seely - Semantics

Alasdair Urquhart - Complexity problems for substructural logics



ALASDAIR URQUHART, Department of Philosophy, University of Toronto, Toronto, Ontario  M5S 1A1
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.


next up previous
Next: Franck van Breugel - Up: Applied Logic / Logique Previous: Robert Seely - Semantics