Abstract
Nonassociative Lambek Calculus (NL) is a syntactic calculus of types introduced by Lambek [8]. The polynomial time decidability of NL was established by de Groote and Lamarche [4]. Buszkowski [3] showed that systems of NL with finitely many assumptions are decidable in polynomial time and generate context-free languages; actually the P-TIME complexity is established for the consequence relation of NL. Adapting the method of Buszkowski [3] we prove an analogous result for Nonassociative Lambek Calculus with unit (NL1). Moreover, we show that any Lambek grammar based on NL1 (with assumptions) can be transformed into an equivalent context-free grammar in polynomial time.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bulińska M.: ‘The Pentus Theorem for Lambek Calculus with Simple Nonlogical Axioms’. Studia Logica 81, 43–59 (2005)
Buszkowski W.: ‘Generative Capacity of Nonassociative Lambek Calculus’. Bulletin of Polish Academy of Sciences. Mathematics 34, 507–516 (1986)
Buszkowski, W. ‘Lambek Calculus with Nonlogical Axioms’, in: Language and Grammar. Studies in Mathematical Linguistics and Natural Language, (C. Casadio, P.J. Scott, R. A. G. Seely, Eds.), CSLI Publications, 77–93, 2005.
de Groote P., Lamarche F.: Clasical Non-Associative Lambek Calculus. Studia Logica 71, 355–388 (2002)
Jäger G.: ‘Residuation, Structural Rules and Context Freeness’. Journal of Logic, Language and Information 13, 47–59 (2002)
Kandulski M.: ‘The equivalence of Nonassociative Lambek Categorial Grammars and Context-Free Grammars’. Zeitschrift für mathematische Logik und Grundlagen der Mathematik 34, 41–52 (1988)
Lambek J.: ‘The mathematics of sentence structure’. The American Mathematical Monthly 65, 154–170 (1958)
Lambek, J., ‘On the calculus of syntactic types’, in: Structure of Language and Its Mathematical Aspects, (R. Jacobson, Ed.), Proc. Symp. Appl. Math., AMS, Providence, 166–178, 1961.
Lambek, J., ‘Type grammars revisited’, in: Logical Aspects of Computational Linguistics, (A. Lecomte, F. Lamarche, G. Perrier, Eds.), LNAI 1582, Springer, Berlin , 1–27, 1999.
Moortgat, M., ‘Categorial Type Logics’, in: (J. van Benthem, A. ter Meulen, Eds.), Handbook of Logic and Language, Elsevier, Amsterdam, The MIT Press, Cambrigde Mass., 93–177, 1997.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bulińska, M. On the Complexity of Nonassociative Lambek Calculus with Unit. Stud Logica 93, 1–14 (2009). https://doi.org/10.1007/s11225-009-9205-2
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11225-009-9205-2