An Algorithm for Detecting Sentence Validity

Charles DeGennaro, Andrew McDonald, Ashley Suchy
63 8


In this paper, we introduce an algorithm for determining the grammatical validity of a sentence. We take a similar approach as in (Preller, 2007) and (Lambek, Type Grammar Revisited, 1999) (Lambek, From word to sentence: a computational algebraic approach to grammar, 2008) by encoding the English words based on word type which we call components. A sentence can be described both algebraically and geometrically. Our algorithm generates the geometric portion called underlinks from the generalized reductions of the algebraic portion. Underlinks uniquely determine the reduction of the components leading to the empty string. This is the mathematical basis for determining if a sentence is valid. We also provide a proof for the algorithm’s time complexity of O(n2) along with a Python implementation. This paper is part of a bigger project based on (Coecke, Mehrnoosh, & Clarky, 2010) where we explore the combination of a sentence’s grammar and meaning. This is done by combining two compact closed categories; pregroups represent the grammar of a sentence, and finite dimensional vector spaces describe the meaning of a sentence. Together one compact closed category is created, representing both aspects of the sentence.


Algorithm, Language processing, Pregroup grammar

Full Text:



Coecke, B., Mehrnoosh, S., & Clarky, S. (2010). Mathematical Foundations for a Compositional Distributional Model of Meaning. CoRR.

DeGennaro, C. (2023). GitHub code.

Lambek, J. (2008). From word to sentence: a computational algebraic approach to grammar.

Preller, A. (2007). Toward Discourse Representation via Pregroup Grammars. Journal of Logic, Langauge, and Information, 173-194.



  • There are currently no refbacks.

Copyright (c) 2024 International Journal on Engineering, Science and Technology




International Journal on Engineering, Science and Technology (IJonEST)-ISSN: 2642-4088


Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.