Abstract
We consider pregroup grammars with letter promotions of the form \(p^{(m)} \Longrightarrow q^{(n)}, p \Longrightarrow 1, 1 \Longrightarrow q\). We prove a variant of Lambek’s normalization theorem [5] for the calculus of pregroups enriched with such promotions and present a polynomial parsing algorithm for the corresponding pregroup grammars. The algorithm extends that from [8], elaborated for pregroup grammars without letter promotions. The normalization theorem, restricted to letter promotions without 1, was proved in [3,4] while the present version was stated in [4] without proof and used to show that the word problem for letter promotions with unit is polynomial. Our results are contained in the unpublished PhD thesis [9].
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Buszkowski, W.: Lambek Grammars Based on Pregroups. In: de Groote, P., Morrill, G., Retoré, C. (eds.) LACL 2001. LNCS (LNAI), vol. 2099, pp. 95–109. Springer, Heidelberg (2001)
Buszkowski, W., Moroz, K.: Pregroup grammars and context-free grammars. In: Casadio, C., Lambek, J. (eds.) Computational Algebraic Approaches to Natural Language, Polimetrica, pp. 1–21 (2008)
Buszkowski, W., Lin, Z.: Pregroup Grammars with Letter Promotions. In: Dediu, A.-H., Fernau, H., Martín-Vide, C. (eds.) LATA 2010. LNCS, vol. 6031, pp. 130–141. Springer, Heidelberg (2010)
Buszkowski, W., Lin, Z., Moroz, K.: Pregroup Grammars with Letter Promotions: Complexity and Context-Freeness. Journal of Computer and System Sciences 78(6), 1899–1909 (2012)
Lambek, J.: Type Grammars Revisited. In: Lecomte, A., Perrier, G., Lamarche, F. (eds.) LACL 1997. LNCS (LNAI), vol. 1582, pp. 1–27. Springer, Heidelberg (1999)
Lambek, J.: From Word to Sentence: a computational algebraic approach to grammar. Polimetrica (2008)
Mater, A.H., Fix, J.D.: Finite Presentations of Pregroups and the Identity Problem. In: Proceedings of FG-MoL 2005, pp. 63–72. CSLI (electronic) (2005)
Moroz, K.: A Savateev-style parsing algorithm for pregroup grammars. In: de Groote, P., Egg, M., Kallmeyer, L. (eds.) FG 2009. LNCS, vol. 5591, pp. 133–149. Springer, Heidelberg (2011)
Moroz, K.: Algorithmic questions for pregroup grammars, PhD thesis, Adam Mickiewicz University, Poznań (2010)
Pentus, M.: Lambek calculus is NP-complete. Theoretical Computer Science 357, 186–201 (2006)
Savateev, Y.: Unidirectional Lambek Grammars in Polynomial Time. Theory of Computing Systems 46, 662–672 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Moroz, K. (2013). Parsing Pregroup Grammars with Letter Promotions in Polynomial Time. In: Morrill, G., Nederhof, MJ. (eds) Formal Grammar. FG FG 2013 2012. Lecture Notes in Computer Science, vol 8036. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39998-5_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-39998-5_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39997-8
Online ISBN: 978-3-642-39998-5
eBook Packages: Computer ScienceComputer Science (R0)