Pregroup Grammar

Origin. Joachim Lambek (1999, 2008), a later reformulation of his 1958 syntactic calculus. Replaces the residuated (implicational) structure of the Lambek calculus with a pregroup: an ordered monoid with left and right adjoints. A non-commutative, order-based type logic for natural-language syntax.

Models. Grammatical categories as elements of a partially ordered monoid. Each word gets one or more types built from basic types and their left/right adjoints; a string is grammatical when the product of its types reduces (via contractions) to a designated sentence type. Word order is respected through non-commutativity, and the two adjoints encode "expects an argument to the left / right."

Formalism.

Pregroup: A partially ordered monoid (P, ·, 1, ≤) in which each a has a left adjoint aˡ and a right adjoint aʳ with: aˡ · a ≤ 1 ≤ a · aˡ and a · aʳ ≤ 1 ≤ aʳ · a. The contractions aˡa → 1 and aaʳ → 1 are the only reductions needed (expansions 1 → aaˡ etc. are not required for parsing).

Types: Basic types, e.g., n (noun/nominal), s (sentence), π (subject), o (object). Compound types are products of basic types and their iterated adjoints (…aˡˡ, aˡ, a, aʳ, aʳʳ…).

Reduction (parsing): Concatenate the word types; apply contractions xˡx → 1 and xxʳ → 1 (only adjacent, order-preserving). A sentence is well-formed if the whole product reduces to the sentence type s (≤ s).

Example: "John" : π ; "likes" : πʳ s oˡ ; "Mary" : o. π · (πʳ s oˡ) · o → (π πʳ) s (oˡ o) → 1·s·1 = s. Grammatical.

Relation to Lambek calculus: Pregroups are the "adjoint" (non-residuated) counterpart of the Lambek calculus; the two right/left divisions , / become adjoints ʳ, ˡ. Parsing is by cancellation rather than by hypothetical proof search.

Symbols.

Symbol	Unicode	Name	Meaning
·	U+00B7	Middle dot / Monoid product	Concatenation of types
≤	U+2264	Less-than or equal	The partial order; reads as derivability
ˡ	U+02E1	Modifier letter small l	Superscript marking the left adjoint aˡ
ʳ	U+02B3	Modifier letter small r	Superscript marking the right adjoint aʳ
→	U+2192	Rightwards arrow	A reduction step, as in xˡx → 1
π	U+03C0	Greek small pi	Basic type for the subject
1	—	Unit	The empty type, unit of the monoid
P	—	Pregroup	The carrier of the ordered monoid (P, ·, 1, ≤)
n, s, o	—	Basic types	Nominal, sentence, object
DisCoCat	—	Categorical compositional distributional model	Pregroup syntax paired with vector-space meanings

Metatheory. Lambek's switching lemma is the central result: in a free pregroup any derivation can be rearranged so that all contractions precede all expansions, so a reduction to a basic type never needs an expansion at all, and parsing becomes cancellation rather than proof search. Buszkowski (2001) proved that the free pregroup over a partially ordered set is conservative over it — a ≤ b holds in the pregroup exactly when it holds in the poset — and that pregroup grammars generate exactly the ε-free context-free languages, the same class the Lambek calculus generates (Pentus 1993). Complexity separates the two despite the shared capacity: pregroup reduction is polynomial, with cubic parsing algorithms (Moroz 2010), while derivability in the Lambek calculus is NP-complete (Pentus 2006). Structurally a pregroup is a posetal rigid monoidal category, and that is what DisCoCat (Coecke, Sadrzadeh, and Clark 2010) exploits, mapping types functorially to vector spaces. Degeneracy is easy to trigger: a pregroup whose order is equality is a group, and a commutative pregroup is a partially ordered group, so both the partial order and the non-commutativity are doing essential work.

Applies to. Computational syntax and parsing. Type-logical grammar (non-commutative substructural). Compositional distributional semantics (DisCoCat, tensor meanings). Cross-linguistic word-order modeling.

Limitations. Generative capacity is exactly context-free, which is a proved ceiling and not a gap waiting to be filled: the cross-serial dependencies of Swiss German are demonstrably not context-free (Shieber 1985), so they lie outside a pregroup grammar in its base form, as do the discontinuous constituents that motivated the displacement and Lambek–Grishin calculi. The two adjoints are then lost in the intended semantics — finite-dimensional vector spaces form a symmetric compact closed category, so the DisCoCat functor cannot distinguish aˡ from aʳ, and the word-order information that pregroup syntax exists to carry is precisely what the meaning space discards. Lexical assignment is manual and multiplies: a word with several syntactic uses needs a type for each, and learning algorithms for pregroup lexicons succeed only under strong restrictions on the type shapes admitted. And the calculus is syntax alone — grammaticality is a cancellation fact about types with no truth conditions attached, so any semantic application supplies its own interpretation layer and inherits whatever that layer cannot express.