Abstract
We show how to encode context-free string grammars, linear context-free tree grammars, and linear context-free rewriting systems as Abstract Categorial Grammars. These three encodings share the same constructs, the only difference being the interpretation of the composition of the production rules. It is interpreted as a first-order operation in the case of context-free string grammars, as a second-order operation in the case of linear context-free tree grammars, and as a third-order operation in the case of linear context-free rewriting systems. This suggest the possibility of defining an Abstract Categorial Hierarchy.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abrusci, M., Fouqueré, C., and Vauzeilles, J., 1999, “Tree-adjoining grammars in a fragment of the Lambek calculus,” Computational Linguistics 25, 209–236.
Barendregt, H., 1984, The Lambda Calculus, its Syntax and Semantics, North-Holland, revised edition.
Carpenter, B., 1996, Type-Logical Semantics, Cambridge, MA and London, U.K.: MIT Press.
de Groote, P., 2001, “Towards Abstract Categorial Grammars,” pp. 148–155 in Association for Computational Linguistics, 39th Annual Meeting and 10th Conference of the European Chapter, Proceedings of the Conference.
de Groote, P., 2002, “Tree-adjoining grammars as Abstract Categorial Grammars,” in pp. 145–150 TAG+6, Proceedings of the Sixth International Workshop on Tree Adjoining Grammars and Related Frameworks.
Girard, J.-Y., 1987, “Linear logic,” Theoretical Computer Science 50, 1–102.
Joshi, A.K. and Kulick, S., 1997, “Partial proof trees as building blocks for a categorial grammar,” Linguistic & Philosophy 20, 637–667.
Joshi, A.K. and Schabes, Y., 1997, “Tree-adjoining grammars,” in Handbook of Formal Languages, Vol. 3, G.R. and A. Salomaa, ed., Springer, Chapter 2.
Mönnich, U., 1997, “Adjunction as substitution,” pp. 169–178. in G.-J. Kruiff, G. Morrill, and D. Oehrle (eds.) Formal Grammar.
Moortgat, M., 1997, “Categorial type logics,” in Handbook of Logic and Language, J. van Benthem and A. ter Meulen, eds., Elsevier, Chapter 2.
Morrill, G., 1994, Type Logical Grammar: Categorial Logic of Signs, Dordrecht: Kluwer Academic Publishers.
Oehrle, R.T., 1994, “Term-labeled categorial type systems,” Linguistic & Philosophy 17, 633–678.
Pollard, C., 1984, “Generalized phrase structure grammars, head grammars, and natural language,” Ph.D. Thesis, Stanford University, CA.
Ranta, A., 2002, “Grammatical Framework,” Journal of Functional Programming 14, 145–189.
Seki, H., Matsumura, T., Fujii, M., and Kasami T., 1991, “On multiple context-free grammars,” Theoretical Computer Science 223, 87–120.
Vijay-Shanker, K., Weir, D. J., and Joshi, A. K. 1987, ‘Characterizing structural descriptions produced by various grammatical formalisms,’ pp. 104–111 in Proceedings of the 25th ACL, Stanford, CA.
Weir, D.J., 1988, “Characterizing mildly context-sensitive grammar formalisms,” Ph.D. Thesis, University of Pennsylvania.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
de Groote, P., Pogodalla, S. On the Expressive Power of Abstract Categorial Grammars: Representing Context-Free Formalisms. J Logic Lang Inf 13, 421–438 (2004). https://doi.org/10.1007/s10849-004-2114-x
Issue Date:
DOI: https://doi.org/10.1007/s10849-004-2114-x