|
Lambek Calculus with a Unit and One Division / Kuznetsov S.D. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2011. № 4. P. 55-57 [Moscow Univ. Math. Bulletin. Vol. 66, N 4, 2011.]. In this paper we present a substitution that reduces the derivability in the Lambek calculus with a unit and one division to the derivability in the Lambek calculus with one division permitting empty antecedents. Using this substitution, we establish the existence of an algorithm checking the derivability in the Lambek calculus with a unit and one division in polynomial time.
Key words: Lambek calculus, algorithmic complexity.
|