# zbMATH — the first resource for mathematics

A faithful representation of non-associative Lambek grammars in abstract categorial grammars. (English) Zbl 1197.03032
Summary: This paper solves a natural but still open question: can Abstract Categorial Grammars (ACGs) respresent usual categorial grammars? Despite their name and their claim to be a unifying framework, up to now there was no faithful representation of usual categorial grammars in ACGs. This paper shows that Non-Associative Lambek Grammars as well as their derivations can be defined using ACGs of order two. To conclude, the outcome of such a representation is discussed.

##### MSC:
 03B65 Logic of natural languages 03B40 Combinatory logic and lambda calculus 03B47 Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics) 68Q42 Grammars and rewriting systems
##### Keywords:
lambda calculus; formal language theory; categorial grammar
Grail; Grail
Full Text:
##### References:
 [1] Barendregt H.P. (1984) The Lambda calculus: Its syntax and semantics, Vol. 103. Studies in logic and the foundations of mathematics (revised edition). North-Holland, Amsterdam · Zbl 0551.03007 [2] Buszkowski, W. (1997). Mathematical linguistics and proof theory. In J. van Benthem & A. ter Meulen (Eds.), Handbook of logic and language (pp. 683–736). Amsterdam: Elsevier Science B.V. and Cambridge, MA: The MIT Press. [3] Capelletti, M. (2007). Parsing with structure-preserving categorial grammars. PhD thesis, UIL-OTS, Universiteit Utrecht. [4] de Groote, P. (2001). Towards abstract categorial grammars. In Association for Computational Linguistic (Ed.), Proceedings 39th Annual Meeting and 10th Conference of the European Chapter (pp. 148–155). Morgan Kaufmann Publishers. [5] de Groote P., Pogodalla S. (2004) On the expressive power of abstract categorial grammars: Representing context-free formalisms. Journal of Logic, Language and Information 13(4): 421–438 · Zbl 1062.03024 · doi:10.1007/s10849-004-2114-x [6] Engelfriet J., Maneth S. (2006) The equivalence problem for deterministic MSO tree transducers is decidable. Information Processing Letters 100(5): 206–212 · Zbl 1185.68385 · doi:10.1016/j.ipl.2006.05.015 [7] Girard J. Y., Taylor P., Lafont Y. (1989) Proofs and types. Cambridge University Press, Cambridge · Zbl 0671.68002 [8] Huet, G. (1976). Résolution d’équations dans des langages d’ordre 1,2,...,$$\omega$$. Thèse de doctorat d’état ès sciences mathématiques. Université Paris VII. [9] Kandulski M. (2003) Derived tree languages of nonassociative Lambek categorial grammars with product. Fundamenta Informaticae 55(3–4): 349–362 · Zbl 1039.03012 [10] Lambek, J. (1961). On the calculus of syntactic types. In R. Jakobson (Ed.), Studies of Language and its Mathematical Aspects, Proceedings of the 12th Symposium of Applied Mathematics (pp. 166–178). [11] Moortgat M. (1988) Categorial investigations: Logical & linguistic aspects of the Lambek calculus. Foris Pubns, USA [12] Moot, R. (1999). Grail: An interactive parser for categorial grammars. In R. Delmonte (Ed.), Proceedings of VEXTAL 1999 (pp. 255–261). [13] Morawietz F. (2003) Two-step approaches ot natural language formalisms. Studies in generative grammar. Mouton de Gruyter, Berlin, New York [14] Muskens, R. (2001). Lambda grammars and the syntax-semantics interface. In R. van Rooy & M. Stokhof (Eds.), Proceedings of the Thirteenth Amsterdam Colloquium, Amsterdam (pp. 150–155). [15] Stabler, E. (1997). Derivational minimalism. In C. Retoré (Ed.), Logical Aspects of Computational Linguistics, LACL’96. Volume 1328 of LNCS/LNAI (pp 68–95). Springer. · Zbl 1156.68439 [16] Tiede, H. J. (1999). Deductive systems and grammars: Proofs as grammatical structures. PhD thesis, Indiana University.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.