Docs / Phonology / OptimalityTheory / LinearExtension

Linear extensions of a ranking relation

import Linglib.Phonology.OptimalityTheory.LinearExtension · namespace OptimalityTheory

A partial ranking of the constraints is a relation r on them, and the total rankings compatible with it are its linear extensions. Every partial order has one, by Szpilrajn's theorem, and a permutation of the constraints that preserves r permutes its linear extensions. In a stratified relation the constraints fall into strata ranked one above the other, and a transposition within a freely ranked stratum preserves it.

Implementation notes

A relation is an unbundled r : ι → ι → Prop on the constraints ι with [IsPartialOrder ι r] where needed, never a PartialOrder ι value, since a class-typed binder would become a local instance and capture the ≤ and < notation. This is mathlib's idiom for orders treated as data, as in extend_partialOrder. A permutation g of the constraints is an automorphism of r when g ⁻¹'o r = r, and acts on a ranking σ by σ.trans g.

A stratified relation is used here through its linear extensions, each a total ranking, as Anttila 1997 uses a partial ranking. Tesar & Smolensky 1995 evaluate a stratified hierarchy by pooling the marks of a stratum, a property of evaluation rather than of the relation, which is not formalized here.

References

Linear extensions

L49–54
L60–63
L123–126
L128–131
L146–149

Stratified grammars

In a stratified grammar every constraint of an earlier stratum dominates every constraint of a later one, and an inner order applies within each stratum. With the discrete inner order the linear extensions rank each stratum's constraints freely, as Anttila 1997 ranks a partial order's.

L167–171
L173–176
L178–181
L183–184

A stratified grammar is invariant under the transposition of two constraints of a stratum on which the inner order is discrete.

theorem swap_preimage_stratifiedL186–211
{ι : Type u_1} {s : ℕ} {stratumOf : ι → Fin s} {inner : ι → ι → Prop} {k : Fin s} {d d' : ι} [DecidableEq ι] [Std.Refl inner] (h_triv : ∀ (a b : ι), stratumOf a = k → stratumOf b = k → inner a b → a = b) (hd : stratumOf d = k) (hd' : stratumOf d' = k) :
⇑(Equiv.swap d d') ⁻¹'o stratified stratumOf inner = stratified stratumOf inner

Built from