Reports on Mathematical Logic

No. 43


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

Back to Main Menu