##
Reports on Mathematical Logic

###
No. 43

Wojciech BUSZKOWSKI

On the Complexity of Some Substructural Logics
A b s t r a c t. We use a syntactic interpretation of MALL in BCI with $\wedge $,defined in
*W. Buszkowski, Finite Models of Some Substructural Logics, Mathematical Logic
Quarterly 48 (2002), pp.\ 63--72 *, to prove the undecidability of the consequence relations for BCI with $\wedge $ and BCI with
$\vee $, and the NP-completeness of BCI. Similar results are obtained for a variant of the Lambek calculus.

Adam Mickiewicz University in Pozna\'{n}

Rovira i Virgili University in Tarragona

buszko@amu.edu.pl

Back to Main Menu