Abstract
Pregroup grammars have a cubic recognition algorithm. Here, we define a correct and complete recognition and parsing algorithm and give sufficient conditions for the algorithm to run in linear time. These conditions are satisfied by a large class of pregroup grammars, including grammars that handle coordinate structures and distant constituents.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Buszkowski, Wojciech, ‘Lambek Grammars based on pregroups’, in P. de Groote et al. (eds.), Logical Aspects of Computational Linguistics, LNAI 2099, Springer, 2001.
Younger David (1967). ‘Recognition and Parsing of Context-Free Languages in Time n3’. Information and Control 10:2
Degeilh, Sylvain, and Anne Preller, ‘Efficiency of Pregroups and the French noun phrase’, Journal of Language, Logic and Information, Springer, Vol. 14, 4:423–444, 2005.
Earley Jay (1970). ‘An efficient context-free parsing algorithm’. Communications of the AMC, Volume 13 2:94–102
Gazdar, Gerald, ‘Unbounded Dependency and Coordinate Structure’, in Walter Salvitch (ed.), The Formal Complexity of Natural Language, Reidel Publishing Company, 1987, pp. 183–226.
Lambek, Joachim, ‘Type Grammar revisited’, in A. Lecomte et al. (eds.), Logical Aspects of Computational Linguistics, Springer LNAI 1582, 1999, pp. 1–27.
Lambek Joachim (2004). ‘A computational algebraic approach to English grammar’. Syntax 7, 2:128–147
Oehrle, Richard, ‘A parsing algorithm for pregroup grammars’, in Proceedings of Categorial Grammars 2004, Montpellier France, 2004, pp. 59–75.
Preller, Anne, and Joachim Lambek, Free compact 2-categories, October 2005, forthcoming in: Mathematical Structures for Computer Sciences, Cambridge University Press
Preller Anne (2007). Toward Discourse Representation Via Pregroup Grammars. JoLLI 16:173–194 doi:10.1007/s10849-006-9033-y
Author information
Authors and Affiliations
Corresponding author
Additional information
Special Issue Categorial Grammars and Pregroups Edited by Wojciech Buszkowski and Anne Preller
Rights and permissions
About this article
Cite this article
Preller, A. Linear Processing with Pregroups. Stud Logica 87, 171–197 (2007). https://doi.org/10.1007/s11225-007-9087-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11225-007-9087-0