Pregroup grammar

Last updated

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.

Contents

Definition of a pregroup

A pregroup is a partially ordered algebra such that is a monoid, satisfying the following relations:

The contraction and expansion relations are sometimes called Ajdukiewicz laws.

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

and are called the left and right adjoints of x, respectively.

The symbols and are also written and respectively. In category theory, pregroups are also known as autonomous categories [1] or (non-symmetric) compact closed categories. [2] More typically, will just be represented by adjacency, i.e. as .

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 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, N0}, and let the following typing relation hold:

A sentence S that has type T is said to be grammatical if . We can prove this by use of a chain of . For example, we can prove that is grammatical by proving that :

by first using contraction on and then again on . 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

PregroupGrammar-Example-JohnMetMary.png

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

PregroupGrammar-Example-TheDogBarkedAtTheCat.png

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 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 , 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:

Some examples of terms are f(x), g(a,h(x,y)), . 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):

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

PregroupGrammar-LeftAdjointReduction.png
PregroupGrammar-RightAdjointReduction.png

For example, applying this to the types and semantics for the sentence (emphasizing the link being reduced)

SemanticCalculation-JohnMetMary.png

For the sentence :

Pregroup-SemanticCalculation-TheDogBarkedAtTheCat.png

See also

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.

<span class="mw-page-title-main">Binomial coefficient</span> Number of subsets of a given size

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 nk ≥ 0 and is written It is the coefficient of the xk 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 Lp 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 Lp 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.

<span class="mw-page-title-main">Differential operator</span> Typically linear operator defined in terms of differentiation of functions

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

  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.