Substructural Logics and Formal Linguistics: Back and Forth
by
WOJCIECH BUSZKOWSKI
Adam Mickiewicz University in Poznan

There are mutual relations between substructural logics and formal language theory. They are especially transparent in the area of categorial grammars (type-logical grammars) which describe a language by assigning types to lexical atoms (words) and employ a type logic to process syntactic structures in accordance with their semantical interpretation. The logics involved here are different variants of the Lambek calculus, Full Lambek Calculus, BCI and Linear Logics.

This lecture presents several mathematically interesting examples of the interaction. First, we show applications of proof theory of substructural logics (cut elimination, interpolation, normalization) in proofs of weak and strong equivalence of different classes of categorial grammars and phrase structure grammars. We also discuss other topics, e.g. algebraic models, type-theoretic semantics and complexity.

Second, we present some successful attempts in the opposite direction: methods and results of formal language theory are applied to solve model-theoretic and computational problems, concerning substructural logics. We focus on some results for action logic (Full Lambek Calculus with Kleene star), Non-Associative Full Lambek Calculus with distribution, and BCI.

The lecture is based on the results of the author and his collaborators in Poland (M. Kandulski, M. Kolowska-Gawiejnowicz, W. Zielonka, M. Bulinska, M. Farulewski, A. Kislak-Malinowska, E. Palka) and other scholars, e.g. J. van Benthem, J.-Y. Girard, P. de Groote, G. Jaeger, P. Jipsen, M. Kanovich, H. Ono, M. Pentus.

PDF

Date received: May 14, 2007