Equality is the discrete partial order. As a grammar it imposes no ranking, and every ranking is a linear extension of it.
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
The ranking σ is a linear extension of the relation r when it ranks a at least as high
as b whenever r a b.
- σ.IsLinearExtension r = (r ≤ σ.toRel)
Used by Ranking.Enumeration.instDecidableIsLinearExtensionOfFintypeOfDecidableRel, Ranking.Enumeration.IsLinearExtension.dominates, Ranking.Enumeration.IsLinearExtension.le_dominates, Ranking.Enumeration.IsLinearExtension.eq_of_rel_of_rel, Ranking.Enumeration.IsLinearExtension.transGen, Ranking.Enumeration.isLinearExtension_toRel, Ranking.Enumeration.isLinearExtension_trans_iff, Ranking.Enumeration.IsLinearExtension.trans_of_preimage_eq, Ranking.Enumeration.exists_isLinearExtension, Ranking.Enumeration.linearExtensions, Ranking.Enumeration.mem_linearExtensions
Used in Phonology/OptimalityTheory/Grammar, Phonology/OptimalityTheory/PartiallyOrderedConstraints, Phonology/OptimalityTheory/Realization, Phonology/OptimalityTheory/Stratal, Aitha2026
- σ.instDecidableIsLinearExtensionOfFintypeOfDecidableRel r = decidable_of_iff (∀ (a b : ι), r a b → (Equiv.symm σ) a ≤ (Equiv.symm σ) b) ⋯
Built from
A linear extension strictly ranks distinct related constraints.
Built from
A linear extension strictly ranks the distinct pairs of the relation.
Built from
Two relations with a common linear extension order no two distinct constraints in opposite ways.
Built from
A ranking that extends a relation extends its transitive closure, so a diagram may be given by its edges.
Built from
Built from
Composing with a permutation g of the constraints turns the linear extensions of the
pullback of r along g into those of r.
Built from
The linear extensions of a grammar are closed under the permutations of the constraints that preserve it.
Built from
Every grammar has a linear extension, by Szpilrajn's theorem.
Built from
The linear extensions of a grammar: Anttila's tableaux, the total rankings among which the grammar chooses at each evaluation.
- Ranking.Enumeration.linearExtensions r = {σ : Ranking.Enumeration ι n | σ.IsLinearExtension r}
Built from
Used by Ranking.Enumeration.mem_linearExtensions, Ranking.Enumeration.linearExtensions_toRel, Ranking.Enumeration.linearExtensions_eq, Ranking.Enumeration.linearExtensions_nonempty
Used in Phonology/OptimalityTheory/Grammar, Phonology/OptimalityTheory/PartiallyOrderedConstraints, Anttila1997, CoetzeePater2011, Hyman2003
Built from ,
A ranking is the only linear extension of its own order.
Built from
Every ranking is a linear extension of the discrete grammar.
Built from
Built from
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.
The stratified grammar of a stratum assignment and an inner order: the lexicographic order
Prod.Lex pulled back along a ↦ (stratumOf a, a), so that strata compare strictly and inner
applies within a stratum.
- stratified stratumOf inner a b = Prod.Lex (fun (x1 x2 : Fin s) => x1 < x2) inner (stratumOf a, a) (stratumOf b, b)
Used by stratified_iff, instIsPartialOrderStratified, instDecidableRelStratified, swap_preimage_stratified
Used in Phonology/OptimalityTheory/PartiallyOrderedConstraints, Anttila1997, CoetzeePater2011
Built from
Built from
- instDecidableRelStratified x✝¹ x✝ = decidable_of_iff (stratumOf x✝¹ < stratumOf x✝ ∨ stratumOf x✝¹ = stratumOf x✝ ∧ inner x✝¹ x✝) ⋯
Built from
A stratified grammar is invariant under the transposition of two constraints of a stratum on which the inner order is discrete.
Built from