An Algorithm for Detecting Sentence Validity

Charles DeGennaro, Andrew McDonald, Ashley Suchy
63 8

Abstract


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.


Keywords


Algorithm, Language processing, Pregroup grammar

Full Text:

PDF

References


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

DeGennaro, C. (2023). GitHub code. https://github.com/ItBeCharlie/SentenceValidity.

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.




DOI: https://doi.org/10.46328/ijonest.208

Refbacks

  • There are currently no refbacks.


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

Abstracting/Indexing


 

 


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