Abstract
The Lambek calculus introduced in Lambek [6] is a strengthening of the type reduction calculus of Ajdukiewicz [1]. We study Associative Lambek Calculus L in Gentzen style axiomatization enriched with a finite set Γ of nonlogical axioms, denoted by L(Γ).It is known that finite axiomatic extensions of Associative Lambek Calculus generate all recursively enumerable languages (see Buszkowski [2]). Then we confine nonlogical axioms to sequents of the form p → q, where p and q are atomic types. For calculus L(Γ) we prove interpolation lemma (modifying the Roorda proof for L [10]) and the binary reduction lemma (using the Pentus method [9] with modification from [3]). In consequence we obtain the weak equivalence of the Context-Free Grammars and grammars based on L(Γ).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ajdukiewicz, A., ‘Die syntaktische Konnexität’, Studia Philosophica 1:27–1, 1935.
Buszkowski, W., ‘Some decision problems in the theory of syntactic categories’, Zeitschrift für mathematische Logik und Grundlagen der Mathematik 539:548–28, 1982. The Pentus Theorem for Lambek Calculus with Simple Nonlogical Axioms 59
Buszkowski, W., ‘Mathematical linguistics and proof theory’, in: J. van Benthem and A. ter Meulen (eds.), Handbook of Logic and Language, Elsevier Science B. V., 683:736, 1997.
Buszkowski, W., ‘Lambek Calculus with Nonlogical Axioms’, in: C. Casadio, P. J. Scott and R.A.G. Seely (eds.), Language and Grammar. Studies in Mathematical Linguistics and Natural Language, CSLI Lecture Notes, to appear.
Hopcroft, J.E. and J.D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading, MA, 1979.
Lambek, J., ‘The mathematics of sentence structure’, The American Mathematical Monthly, 154:170–65, 1958.
Lambek, J., ‘Deductive systems and categories I’, Journal of Mathematical Systems Theory, 287:318–2, 1968
Lambek, J., ‘Type grammars revisited’, in: A. Lecomte, F. Lamarche and G. Perrier (eds.), Logical Aspects of Computational Linguistics, Proc. LACL'97, LNAI 1582, Springer, Berlin, 1:27, 1999.
Pentus, M., ‘Lambek grammars are context-free’, Proc. 8 IEEE Symposium on Logic in Computer Science, Montreal, 429:433, 1993.
Roorda, D., Resource logic: proof-theoretical investigations, Ph.D.Thesis, University of Amsterdam, 1991.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bulińska, M. The Pentus Theorem for Lambek Calculus with Simple Nonlogical Axioms. Stud Logica 81, 43–59 (2005). https://doi.org/10.1007/s11225-005-2801-x
Received:
Issue Date:
DOI: https://doi.org/10.1007/s11225-005-2801-x