Skip to main content
SpringerLink
Log in

Linear Processing with Pregroups

  • Published:
Studia Logica Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Buszkowski, Wojciech, ‘Lambek Grammars based on pregroups’, in P. de Groote et al. (eds.), Logical Aspects of Computational Linguistics, LNAI 2099, Springer, 2001.

  2. Younger David (1967). ‘Recognition and Parsing of Context-Free Languages in Time n3’. Information and Control 10:2

    Article  Google Scholar 

  3. 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.

  4. Earley Jay (1970). ‘An efficient context-free parsing algorithm’. Communications of the AMC, Volume 13 2:94–102

    Google Scholar 

  5. Gazdar, Gerald, ‘Unbounded Dependency and Coordinate Structure’, in Walter Salvitch (ed.), The Formal Complexity of Natural Language, Reidel Publishing Company, 1987, pp. 183–226.

  6. Lambek, Joachim, ‘Type Grammar revisited’, in A. Lecomte et al. (eds.), Logical Aspects of Computational Linguistics, Springer LNAI 1582, 1999, pp. 1–27.

  7. Lambek Joachim (2004). ‘A computational algebraic approach to English grammar’. Syntax 7, 2:128–147

    Article  Google Scholar 

  8. Oehrle, Richard, ‘A parsing algorithm for pregroup grammars’, in Proceedings of Categorial Grammars 2004, Montpellier France, 2004, pp. 59–75.

  9. Preller, Anne, and Joachim Lambek, Free compact 2-categories, October 2005, forthcoming in: Mathematical Structures for Computer Sciences, Cambridge University Press

  10. Preller Anne (2007). Toward Discourse Representation Via Pregroup Grammars. JoLLI 16:173–194 doi:10.1007/s10849-006-9033-y

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LIRMM, CNRS, 161, rue Ada, Montpellier, France

    Anne Preller

Authors
  1. Anne Preller
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Anne Preller.

Additional information

Special Issue Categorial Grammars and Pregroups Edited by Wojciech Buszkowski and Anne Preller

Rights and permissions

Reprints 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

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11225-007-9087-0

Keywords

Search

Navigation