Normalization by Evaluation for the Lambek Calculus

Niccolò Veltri
(Tallinn University of Technology)

The syntactic calculus of Lambek is a deductive system for the multiplicative fragment of intuitionistic non-commutative linear logic. As a fine-grained calculus of resources, it has many applications, mostly in formal computational investigations of natural languages.

This paper introduces a calculus of beta-eta-long normal forms for derivations in the Lambek calculus with multiplicative unit and conjunction among its logical connectives. Reduction to normal form follows the normalization by evaluation (NbE) strategy: (i) evaluate a derivation in a Kripke model of Lambek calculus; (ii) extract normal forms from the obtained semantic values. The implementation of the NbE algorithm requires the presence of a strong monad in the Kripke interpretation of positive formulae, in analogy with the extension of intuitionistic propositional logic with falsity and disjunction. The NbE algorithm can also be instantiated with minor variations to calculi for related substructural logics, such as multiplicative and dual intuitionistic linear logic (MILL and DILL).

In Andrzej Indrzejczak and Michał Zawidzki: Proceedings of the 10th International Conference on Non-Classical Logics. Theory and Applications (NCL 2022), Łódź, Poland, 14-18 March 2022, Electronic Proceedings in Theoretical Computer Science 358, pp. 102–117.
Published: 14th April 2022.

ArXived at: https://dx.doi.org/10.4204/EPTCS.358.8 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org