Pregroup grammar is a mathematical model of natural language grammar introduced by Lambek (1999); it is part of the categorial grammar tradition.
A preordered monoid is a tuple where is a preorder and is a monoid such that the multiplication is monotone, i.e.
or equivalently:
for all . A pomonoid is a preordered monoid that is furthermore a poset, i.e.
A pregroup is a pomonoid such that every object has left and right adjoints . Explicitly we have the following four axioms:
In other words, a pregroup is a rigid monoidal category which is thin and skeletal. Note that a commutative pregroup is simply an ordered group. Here are a few variants of pregroups that appear in the literature, see Coecke 2013:
Take the natural numbers and define the set of monotone functions that are furthermore unbounded, i.e. for all there is an with . is a pomonoid with composition as product, identity as unit and iff for all . To show that is a left pregroup, define:
we get:
and
for all , i.e. .
If we replace the natural numbers by the integers then the set of unbounded monotone functions is both a left and a right pregroup where:
For example, if then .
Proposition (Buszkowski 2001): Every pregroup is a pregroup of functions, i.e. a sub-pomonoid of for some poset .
In linguistic applications, one starts with a poset of basic types (e.g. sentence and noun) and then takes the free pregroup generated by . For a basic type , iterated adjoints are called simple types; an arbitrary type may then be given as a sequence of simple types. The following lemma makes the parsing problem for free pregroups decidable — i.e. given a sentence type and the types for a sequence of words , is ?
Switching lemma (Lambek 1999): For any pair of types , if then there is a type such that without expansions and without contractions, i.e. free protogroups recognise the same language as free pregroups.
In Preller, Lambek 2007, Preller and Lambek generalise the free pregroup construction above to free compact 2-categories in order to capture proof relevance. This allows to distinguish between the distinct parsings of ambiguous phrases such as “(men and women) who like maths” vs. “men and (women who like maths)”.
Note that the compact 2-categories of Lambek and Preller differ from compact closed 2-category in that they are not required to be symmetric. A non-symmetric compact closed 2-category with one object is simply a rigid monoidal category.
Given a poset of basic types , the objects of the free rigid monoidal category are the same as that of the free (quasi-)pregroup, the arrows may be described as planar string diagrams. Given two types , we have that if and only if there is an arrow in .
A pregroup grammar is a tuple where and are finite sets called the basic types and the vocabulary respectively, is a relation called the dictionary and is a designated sentence type. We require that is finite, i.e. the set of possible types is finite for each word . The language of is then given by:
i.e. a sequence of words is said to be grammatical whenever there is a dictionary entry for each word such that . One may simplify this by redefining where is the free rigid monoidal category with:
That is, a sequence of words is grammatical whenever there exists a string diagram going from the sequence of words to the sentence type. Note that traditionally the identity wires for words are omitted, hence dictionary entries are depicted as triangles with no input. Contractions are depicted as cups, e.g. from and we get the following diagram:
One may give a semantics to a pregroup grammar by defining a strong monoidal functor , where is the free rigid monoidal category described in section 2. is a suitable rigid monoidal category, e.g. or , depending on the application. Note the similarity with a Lawvere theory as a monoidal functor from a syntactic category to .
We require the image for all words to be the monoidal unit , hence the image for each dictionary entry is given by a state . The meaning for a sentence with grammatical reduction may then be computed from the individual meanings of the words, following Frege's principle of compositionality. This has been developed in Preller 2005 as well as in a series of papers by Bob Coecke and others, see categorical compositional distributional semantics.
Theorem (Buszkowski, Moroz 2008): For each pregroup grammar , there is a context-free grammar such that . Furthermore, may be computed in time polynomial in the size of .
The opposite direction also holds, hence pregroup grammar and context-free grammar are said to be weakly equivalent: the translation preserves only the generated languages, it does not preserve the structure of syntax trees.
Since it is generally accepted that natural languages go beyond context-free languages this result illustrates the lack of expressive power of pregroup grammars whence it becomes necessary to enhance the original grammar model:
One way (Kobele 2005) is to consider product pregroup grammars : these assign to a string a tuple of syntactic types with grammaticality of checked by parallel computation of the grammaticality of in and of in . is then grammatical iff and are i.e. (cf. Kobele&Kracht (2005), prop. 4). This permits to describe e.g. the context-sensitive rules of Swiss German (Lambek (2008)). The checking of syntactic types is still given by computation in a pregroup, namely the product pregroup , but is not free!
Kobele and Kracht (2005) use this together with the above result by Buszkowski and the classical result in formal language theory that any type 0 language is the homomorphic image of the intersection of two (deterministic) context-free languages in order to show that pregroup grammars generate every type 0 language when type checking is done in arbitrary pregroups.
Since it is usually assumed that natural languages do not go beyond mildly context-sensitive languages one sees that (homomorphic images) of products of arbitrary pregroup grammars have excessive power and it becomes necessary to cut back this power. One way to do this is by restricting to be of a type simpler than context-free e.g. a Dyck language? thought of now as a control language supervising the “context-free” computations in . This idea was explored in Kobele (2005).
Another approach to adapt the pregroup grammar formalism to mildly context-sensitive languages was proposed by Genkin et al. (2010) which augment pregroup grammars with buffers.
Joachim Lambek, Type Grammar Revisited, Logical Aspects of Computational Linguistics (1999)
Anne Preller?, Category Theoretical Semantics for Pregroup Grammars, Logical Aspects of Computational Linguistics, 5th International Conference, LACL 2005 (pdf)
Anne Preller?, Joachim Lambek, Free Compact 2-Categories, Mathematical Structures in Computer Science, Cambridge University Press (CUP), 2007 (pdf)
Joachim Lambek, From Word to Sentence: A Computational Algebraic Approach to Grammar, Polimetrica 2008 (pdf)
Wojciech Buszkowski?, Katarzyna Moroz?, Pregroup Grammars and Context-free Grammars, Computational Algebraic Approaches to Natural Language, Polimetrica (2008) (pdf)
Wojciech Buszkowski?. Lambek grammars based on pregroups. Logical Aspects of Computational Linguistics, LNAI 2099: 95–109, 2001.
Bob Coecke, An alternative Gospel of structure: order, composition, processes, Introductory chapter to C. Heunen, M. Sadrzadeh, and E. Grefenstette. Quantum Physics and Linguistics: A Compositional, Diagrammatic Discourse. Oxford University Press, 2013 (arxiv:1307.4038)
Gregory M. Kobele?, Pregroups, Products, and Generative Power , handout Chieti workshop on pregroups May 2005.
Gregory M. Kobele?, Marcus Kracht, On Pregroups, Freedom, and (Virtual) Conceptual Necessity , U. Penn Working Papers in Linguistics 10 no.1 (2005).
Daniel Genkin?, Nissim Francez?, and Michael Kaminski?. Mildly Context-Sensitive Languages via Buffer Augmented Pregroup Grammars, In Essays in Memory of Amir Pnueli, 2010.
Last revised on July 22, 2021 at 12:04:39. See the history of this page for a list of all contributions to it.