Pregroup grammar

Last updated November 26, 2023

Pregroup grammar (PG) is a grammar formalism intimately related to categorial grammars. Much like categorial grammar (CG), PG is a kind of type logical grammar. Unlike CG, however, PG does not have a distinguished function type. Rather, PG uses inverse types combined with its monoidal operation.

Definition of a pregroup

A pregroup is a partially ordered algebra $(A,1,\cdot ,-^{l},-^{r},\leq )$ such that $(A,1,\cdot )$ is a monoid, satisfying the following relations:

$x^{l}\cdot x\leq 1\qquad x\cdot x^{r}\leq 1$ (contraction)
$1\leq x\cdot x^{l}\qquad 1\leq x^{r}\cdot x$ (expansion)

The contraction and expansion relations are sometimes called Ajdukiewicz laws.

From this, it can be proven that the following equations hold:

$1^{l}=1=1^{r}$
$x^{lr}=x=x^{rl}$
$(x\cdot y)^{l}=y^{l}\cdot x^{l}\qquad (x\cdot y)^{r}=y^{r}\cdot x^{r}$

$x^{l}$ and $x^{r}$ are called the left and right adjoints of x, respectively.

The symbols $\cdot$ and $\leq$ are also written $\otimes$ and $\to$ respectively. In category theory, pregroups are also known as autonomous categories ^[1] or (non-symmetric) compact closed categories.^[2] More typically, $x\cdot y$ will just be represented by adjacency, i.e. as $xy$ .

Definition of a pregroup grammar

A pregroup grammar consists of a lexicon of words (and possibly morphemes) L, a set of atomic types T which freely generates a pregroup, and a relation ${\displaystyle$ that relates words to types. In simple pregroup grammars, typing is a function that maps words to only one type each.

Examples

Some simple, intuitive examples using English as the language to model demonstrate the core principles behind pregroups and their use in linguistic domains.

Let L = {John, Mary, the, dog, cat, met, barked, at}, let T = {N, S, N₀}, and let the following typing relation hold:

{\textit {John}}:N\qquad {\textit {Mary}}:N\qquad {\textit {the}}:N\cdot N_{0}^{l}\qquad {\textit {dog}}:N_{0}\qquad {\textit {cat}}:N_{0}

{\textit {met}}:N^{r}\cdot S\cdot N^{l}\qquad {\textit {barked}}:N^{r}\cdot S\qquad {\textit {at}}:S^{r}\cdot N^{rr}\cdot N^{r}\cdot S\cdot N^{l}

A sentence S that has type T is said to be grammatical if $T\leq S$ . We can prove this by use of a chain of $\leq$ . For example, we can prove that ${\textit {John}}\ {\textit {met}}\ {\textit {Mary}}:N\cdot N^{r}\cdot S\cdot N^{l}\cdot N$ is grammatical by proving that $N\cdot N^{r}\cdot S\cdot N^{l}\cdot N\leq S$ :

N\cdot N^{r}\cdot S\cdot N^{l}\cdot N~\leq ~S\cdot N^{l}\cdot N~\leq ~S

by first using contraction on $N\cdot N^{r}$ and then again on $N^{l}\cdot N$ . A more convenient notation exists, however, that indicates contractions by connecting them with a drawn link between the contracting types (provided that the links are nested, i.e. don't cross). Words are also typically placed above their types to make the proof more intuitive. The same proof in this notation is simply

A more complex example proves that the dog barked at the cat is grammatical:

Historical notes

Pregroup grammars were introduced by Joachim Lambek in 1993 as a development of his syntactic calculus, replacing the quotients by adjoints.^[3] Such adjoints had already been used earlier by Harris but without iterated adjoints and expansion rules. Adding such adjoints was interesting to handle more complex linguistic cases, where the fact that $a^{ll}\neq a$ is needed. It was also motivated by a more algebraic viewpoint: the definition of a pregroup is a weakening of that of a group, introducing a distinction between the left and right inverses and replacing the equality by an order. This weakening was needed because using types from a free group would not work: an adjective would get the type $N\cdot N^{-1}=1$ , hence it could be inserted at any position in the sentence.^[4]

Pregroup grammars have then been defined and studied for various languages (or fragments of them) including English,^[5] Italian,^[6] French,^[7] Persian ^[8] and Sanskrit.^[9] Languages with a relatively free word order such as Sanskrit required to introduce commutation relations to the pregroup, using precyclicity.

Semantics of pregroup grammars

Because of the lack of function types in PG, the usual method of giving a semantics via the λ-calculus or via function denotations is not available in any obvious way. Instead, two different methods exist, one purely formal method that corresponds to the λ-calculus, and one denotational method analogous to (a fragment of) the tensor mathematics of quantum mechanics.

Purely formal semantics

The purely formal semantics for PG consists of a logical language defined according to the following rules:

Given a set of atomic terms T = {a, b, ...} and atomic function symbols F = {f_m, g_n, ...} (where subscripts are meta-notational indicating arity), and variables x, y, ..., all constants, variables, and well-formed function applications are basic terms (a function application is well-formed when the function symbol is applied to the appropriate number of arguments, which can be drawn from the atomic terms, variables, or can be other basic terms)
Any basic term is a term
Given any variable x, [x] is a term
Given any terms m and n, $m\cdot n$ is a term

Some examples of terms are f(x), g(a,h(x,y)), $g(x,b)\cdot [x]$ . A variable x is free in a term t if [x] does not appear in t, and a term with no free variables is a closed term. Terms can be typed with pregroup types in the obvious manner.

The usual conventions regarding α conversion apply.

For a given language, we give an assignment I that maps typed words to typed closed terms in a way that respects the pregroup structure of the types. For the English fragment given above we might therefore have the following assignment (with the obvious, implicit set of atomic terms and function symbols):

{\begin{aligned}I({\textit {John}}:N)&=j:E\\I({\textit {Mary}}:N)&=m:E\\I(the:N\cdot N_{0}^{l})&=\iota (p)\cdot [p]:E\cdot E_{0}^{l}\\I(dog:N_{0})&=dog:E_{0}\\I(cat:N_{0})&=cat:E_{0}\\I(met:N^{r}\cdot S\cdot N^{l})&=[x]\cdot met(x,y)\cdot [y]:E^{r}\cdot T\cdot E^{l}\\I(barked:N^{r}\cdot S)&=[x]\cdot barked(x):E^{r}\cdot T\\I(at:S^{r}\cdot N^{rr}\cdot N^{r}\cdot S\cdot N^{l})&=[x]\cdot y\cdot [y]\cdot at(x,z)\cdot [z]:T^{r}\cdot E^{rr}\cdot E^{r}\cdot T\cdot E^{l}\end{aligned}}

where E is the type of entities in the domain, and T is the type of truth values.

Together with this core definition of the semantics of PG, we also have a reduction rules that are employed in parallel with the type reductions. Placing the syntactic types at the top and semantics below, we have

For example, applying this to the types and semantics for the sentence ${\textit {John}}\ {\textit {met}}\ {\textit {Mary}}:N\cdot (N^{r}\cdot S\cdot N^{l})\cdot N$ (emphasizing the link being reduced)

For the sentence ${\textit {the}}\ {\textit {dog}}\ {\textit {barked}}\ {\textit {at}}\ {\textit {the}}\ {\textit {cat}}:(N\cdot N_{0}^{l})\cdot N_{0}\cdot (N^{r}\cdot S)\cdot (S^{r}\cdot N^{rr}\cdot N^{r}\cdot S\cdot N^{l})\cdot (N\cdot N_{0}^{l})\cdot N_{0}$ :

Related Research Articles

In mathematics, more specifically in functional analysis, a Banach space is a complete normed vector space. Thus, a Banach space is a vector space with a metric that allows the computation of vector length and distance between vectors and is complete in the sense that a Cauchy sequence of vectors always converges to a well-defined limit that is within the space.

In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers $n \geq k \geq 0$ and is written $It is the coefficient of the x k term in the polynomial expansion of the binomial power (1 + x) n; this coefficient can be computed by the multiplicative formula$

The Riesz representation theorem, sometimes called the Riesz–Fréchet representation theorem after Frigyes Riesz and Maurice René Fréchet, establishes an important connection between a Hilbert space and its continuous dual space. If the underlying field is the real numbers, the two are isometrically isomorphic; if the underlying field is the complex numbers, the two are isometrically anti-isomorphic. The (anti-) isomorphism is a particular natural isomorphism.

In mathematics, the $L p$ spaces are function spaces defined using a natural generalization of the $p$ -norm for finite-dimensional vector spaces. They are sometimes called Lebesgue spaces, named after Henri Lebesgue, although according to the Bourbaki group they were first introduced by Frigyes Riesz.

In mathematics, a self-adjoint operator on an infinite-dimensional complex vector space V with inner product $is a linear map A that is its own adjoint. If V is finite-dimensional with a given orthonormal basis, this is equivalent to the condition that the matrix of A is a Hermitian matrix, i.e., equal to its conjugate transpose A * . By the finite-dimensional spectral theorem, V has an orthonormal basis such that the matrix of A relative to this basis is a diagonal matrix with entries in the real numbers. This article deals with applying generalizations of this concept to operators on Hilbert spaces of arbitrary dimension.$

In mathematical analysis, Hölder's inequality, named after Otto Hölder, is a fundamental inequality between integrals and an indispensable tool for the study of $L p$ spaces.

In vector calculus, Green's theorem relates a line integral around a simple closed curve $C$ to a double integral over the plane region $D$ bounded by $C$ . It is the two-dimensional special case of Stokes' theorem.

In mathematics, a differential operator is an operator defined as a function of the differentiation operator. It is helpful, as a matter of notation first, to consider differentiation as an abstract operation that accepts a function and returns another function.

<span class="mw-page-title-main">Adjoint representation</span> Mathematical term

In mathematics, the adjoint representation of a Lie group G is a way of representing the elements of the group as linear transformations of the group's Lie algebra, considered as a vector space. For example, if G is $, the Lie group of real n -by- n invertible matrices, then the adjoint representation is the group homomorphism that sends an invertible n -by- n matrix to an endomorphism of the vector space of all linear transformations of defined by: .$

In mathematics, a function space is a set of functions between two fixed sets. Often, the domain and/or codomain will have additional structure which is inherited by the function space. For example, the set of functions from any set X into a vector space has a natural vector space structure given by pointwise addition and scalar multiplication. In other scenarios, the function space might inherit a topological or metric structure, hence the name function space.

Categorial grammar is a family of formalisms in natural language syntax that share the central assumption that syntactic constituents combine as functions and arguments. Categorial grammar posits a close relationship between the syntax and semantic composition, since it typically treats syntactic categories as corresponding to semantic types. Categorial grammars were developed in the 1930s by Kazimierz Ajdukiewicz and in the 1950s by Yehoshua Bar-Hillel and Joachim Lambek. It saw a surge of interest in the 1970s following the work of Richard Montague, whose Montague grammar assumed a similar view of syntax. It continues to be a major paradigm, particularly within formal semantics.

The spectrum of a linear operator $that operates on a Banach space is a fundamental concept of functional analysis. The spectrum consists of all scalars such that the operator does not have a bounded inverse on . The spectrum has a standard decomposition into three parts:$

In linear algebra, the transpose of a linear map between two vector spaces, defined over the same field, is an induced map between the dual spaces of the two vector spaces. The transpose or algebraic adjoint of a linear map is often used to study the original linear map. This concept is generalised by adjoint functors.

In category theory, a branch of mathematics, compact closed categories are a general context for treating dual objects. The idea of a dual object generalizes the more familiar concept of the dual of a finite-dimensional vector space. So, the motivating example of a compact closed category is FdVect, the category having finite-dimensional vector spaces as objects and linear maps as morphisms, with tensor product as the monoidal structure. Another example is Rel, the category having sets as objects and relations as morphisms, with Cartesian monoidal structure.

In mathematics, in the field of functional analysis, the Cotlar–Stein almost orthogonality lemma is named after mathematicians Mischa Cotlar and Elias Stein. It may be used to obtain information on the operator norm on an operator, acting from one Hilbert space into another when the operator can be decomposed into almost orthogonal pieces. The original version of this lemma (for self-adjoint and mutually commuting operators) was proved by Mischa Cotlar in 1955 and allowed him to conclude that the Hilbert transform is a continuous linear operator in $without using the Fourier transform. A more general version was proved by Elias Stein.$

In mathematics — specifically, in stochastic analysis — the infinitesimal generator of a Feller process is a Fourier multiplier operator that encodes a great deal of information about the process.

In mathematics and physics, the Magnus expansion, named after Wilhelm Magnus (1907–1990), provides an exponential representation of the solution of a first-order homogeneous linear differential equation for a linear operator. In particular, it furnishes the fundamental matrix of a system of linear ordinary differential equations of order $n$ with varying coefficients. The exponent is aggregated as an infinite series, whose terms involve multiple integrals and nested commutators.

Minimalist grammars are a class of formal grammars that aim to provide a more rigorous, usually proof-theoretic, formalization of Chomskyan Minimalist program than is normally provided in the mainstream Minimalist literature. A variety of particular formalizations exist, most of them developed by Edward Stabler, Alain Lecomte, Christian Retoré, or combinations thereof.

For certain applications in linear algebra, it is useful to know properties of the probability distribution of the largest eigenvalue of a finite sum of random matrices. Suppose $is a finite sequence of random matrices. Analogous to the well-known Chernoff bound for sums of scalars, a bound on the following is sought for a given parameter t :$

Pokhozhaev's identity is an integral relation satisfied by stationary localized solutions to a nonlinear Schrödinger equation or nonlinear Klein–Gordon equation. It was obtained by S.I. Pokhozhaev and is similar to the virial theorem. This relation is also known as G.H. Derrick's theorem. Similar identities can be derived for other equations of mathematical physics.

References

Lambek, Joachim (2008). "Pregroup grammars and Chomsky's earliest examples" (PDF). Journal of Logic, Language and Information. 17 (2): 141–160. doi:10.1007/s10849-007-9053-2. S2CID 30256603.
Preller, Anna (2007). "Semantic pregroup grammars handle long distance dependencies in French" (PDF). Manuscript.
Claudia Casadio (2004), Pregroup Grammar. Theory and Applications

↑ Selinger, Peter (2011). "A survey of graphical languages for monoidal categories". New Structures for Physics. Lecture Notes in Physics. Vol. 813. Springer. pp. 289–233. arXiv: 0908.3347 . Bibcode:2009arXiv0908.3347S.
↑ Preller, Anne; Mehrnoosh Sadrzadeh (2011). "Semantic Vector Models and Functional Models for Pregroup Grammars" (PDF). Journal of Logic, Language and Information. 20 (4): 419–443. doi:10.1007/s10849-011-9132-2. S2CID 207175357.
↑ Lambek, Joachim (1999). "Type Grammar revisited". In Alain Lecomte (ed.). Logical Aspects of Computational Linguistics. LNAI. Vol. 1582. Heidelberg: Springer. pp. 1–27.
↑ Lambek, Joachim (2008). "Pregroup Grammars and Chomsky's Earliest Examples" (PDF). Journal of Logic, Language and Information. 17 (2): 141–160. doi:10.1007/s10849-007-9053-2. S2CID 30256603.
↑ Lambek 2008
↑ Casadio, Claudia; Joachim Lambek (2001). "An algebraic analysis of clitic pronouns in Italian". Logical Aspects of Computational Linguistics. Springer. pp. 110–124. ISBN 3540422730.
↑ Preller, Anne; Violaine Prince; et al. (2008). "Pregroup grammars with linear parsing of the French verb phrase" (PDF). CL2008: 53–84.
↑ Sadrzadeh, Mehrnoosh (2008). "Pregroup analysis of Persian sentences". Computational Algebraic Approaches to Natural Language, Polimetrica, Milano, Italy: 121–144. CiteSeerX 10.1.1.163.5505 .
↑ Casadio, Claudia; Mehrnoosh Sadrzadeh (2014). "Word Order Alternation in Sanskrit via Precyclicity in Pregroup Grammars". In Franck van Breugel; Elham Kashefi; Catuscia Palamidessi; Jan Rutten (eds.). Horizons of the Mind. A Tribute to Prakash Panangaden. Lecture Notes in Computer Science. Vol. 8464. Springer International Publishing. pp. 229–249. ISBN 978-3-319-06879-4.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Selinger, Peter (2011). "A survey of graphical languages for monoidal categories". New Structures for Physics. Lecture Notes in Physics. Vol. 813. Springer. pp. 289–233. arXiv: 0908.3347 . Bibcode:2009arXiv0908.3347S.

[2] Preller, Anne; Mehrnoosh Sadrzadeh (2011). "Semantic Vector Models and Functional Models for Pregroup Grammars" (PDF). Journal of Logic, Language and Information. 20 (4): 419–443. doi:10.1007/s10849-011-9132-2. S2CID 207175357.

[3] Lambek, Joachim (1999). "Type Grammar revisited". In Alain Lecomte (ed.). Logical Aspects of Computational Linguistics. LNAI. Vol. 1582. Heidelberg: Springer. pp. 1–27.

[4] Lambek, Joachim (2008). "Pregroup Grammars and Chomsky's Earliest Examples" (PDF). Journal of Logic, Language and Information. 17 (2): 141–160. doi:10.1007/s10849-007-9053-2. S2CID 30256603.

[5] Lambek 2008

[6] Casadio, Claudia; Joachim Lambek (2001). "An algebraic analysis of clitic pronouns in Italian". Logical Aspects of Computational Linguistics. Springer. pp. 110–124. ISBN 3540422730.

[7] Preller, Anne; Violaine Prince; et al. (2008). "Pregroup grammars with linear parsing of the French verb phrase" (PDF). CL2008: 53–84.

[8] Sadrzadeh, Mehrnoosh (2008). "Pregroup analysis of Persian sentences". Computational Algebraic Approaches to Natural Language, Polimetrica, Milano, Italy: 121–144. CiteSeerX 10.1.1.163.5505 .

[9] Casadio, Claudia; Mehrnoosh Sadrzadeh (2014). "Word Order Alternation in Sanskrit via Precyclicity in Pregroup Grammars". In Franck van Breugel; Elham Kashefi; Catuscia Palamidessi; Jan Rutten (eds.). Horizons of the Mind. A Tribute to Prakash Panangaden. Lecture Notes in Computer Science. Vol. 8464. Springer International Publishing. pp. 229–249. ISBN 978-3-319-06879-4.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]