On the Complexity of Nonassociative LambekCalculus with Unit

摘要

Nonassociative Lambek Calculus (NL) is a syntactic calculus of types in-troduced by Lambek [8]. The polynomial time decidability of NL was established by deGroote and Lamarche [4]. Buszkowski [3] showed that systems of NL with finitely many as-sumptions are decidable in polynomial time and generate context-free languages; actuallythe P-TIME complexity is established for the consequence relation of NL. Adapting themethod of Buszkowski [3] we prove an analogous result for Nonassociative Lambek Calcu-lus with unit (NL1). Moreover, we show that any Lambek grammar based on NL1 (withassumptions) can be transformed into an equivalent context-free grammar in polynomialtime.