Group theory and computational linguistics (Q1280052)

The aim of this paper is to define a theory of linguistic description based solely on group structure involving the classical notions of non-commutative free group, conjugacy and group presentations. To do this, the author introduces the concept of \(G\)-grammar, which is a collection of lexical expressions (i.e. products of logical forms), phonological forms and inverses of those. \(G\)-grammars use the group-theoretic notion of conjugacy which allows a uniform description of commutative and non-commutative aspects of language and provides an elegant approach to long-distance dependency and scoping phenomena. The author exhibits a \(G\)-grammar for a fragment of English involving quantification and relative pronouns. An example is given to illustrate the generation process. Using the compatible preorder associated to a \(G\)-grammar, the relators of this \(G\)-grammar can be represented as rewrite rules. Several examples of rewriting derivations are presented and discussed. The author compares the new notion of \(G\)-grammar with existing approaches (CFGs, DCGs, CGs). Advantages of \(G\)-grammars for describing commutative and non-commutative aspects of language are discussed. This original paper ends by proving some strong computability properties of \(G\)-grammars from both parsing and generation points of view.