Docs / Phonology / OptimalityTheory / Filtration

Filtration

import Linglib.Phonology.OptimalityTheory.Filtration · namespace OptimalityTheory

Optimality-theoretic evaluation is filtration: the candidates are passed through the constraints one at a time, most dominant first, and each constraint keeps the candidates that violate it least. The filtration of a candidate set along a list of constraints is defined for any list, so it evaluates the prefix of a ranking, a ranking of some of the constraints, or a whole ranking alike. Its survivors are the candidates whose violations along the list are lexicographically least, and along a whole ranking they are the optimal candidates. Filtration never empties a non-empty candidate set, a longer list keeps a subset of what its prefix keeps, and the survivors agree on every constraint of the list. A candidate that some ranking selects and that survives a prefix is selected by a completion of the prefix.

References

Declarations

The filtration of the candidates s along a list of constraints, most dominant first: each constraint in turn keeps the candidates that violate it least. v c k is the number of violations of the constraint k by the candidate c.

def filtrationL35–40
{C : Type u_1} {ι : Type u_2} (v : C → ι → ℕ) (s : Finset C) :
List ι → Finset C

Used by filtration_nil, filtration_cons, filtration_append, mem_filtration, filtration_subset, filtration_append_subset, filtration_nonempty, apply_eq_of_mem_filtration, filtration_cons_of_forall_eq, filtration_eq_singleton_iff, notMem_filtration_of_forall_le, mem_filtration_append_filter, Constraint.eval

Used in Phonology/OptimalityTheory/Evaluation, Phonology/OptimalityTheory/Grammar, Aitha2026, UchiharaMendozaRuiz2021, Vago2017

L42
L44–45
L47–52

The survivors of filtration are the candidates whose violations along the list are lexicographically least.

theorem mem_filtrationL54–73
{C : Type u_1} {ι : Type u_2} {v : C → ι → ℕ} {s : Finset C} {l : List ι} {c : C} :
c ∈ filtration v s l ↔ c ∈ s ∧ ∀ d ∈ s, List.map (v c) l ≤ List.map (v d) l

Built from

L75
L77–80
L82–86
L88–95
L97–100
L102–116
L118–133
L135–151

No Dead Man Walking (Merchant & Prince 2022): a candidate that survives filtration along a list l, such as a whole ranking, and also along a list l₁, survives along l₁ followed by the constraints of l that are not in l₁. A possible optimum that passes a prefix is selected by some completion of the prefix.

theorem mem_filtration_append_filterL153–163
{C : Type u_1} {ι : Type u_2} {v : C → ι → ℕ} {s : Finset C} {l l₁ : List ι} {c : C} [DecidableEq ι] (hl : c ∈ filtration v s l) (hl₁ : c ∈ filtration v s l₁) :
c ∈ filtration v s (l₁ ++ List.filter (fun (x : ι) => decide (x ∉ l₁)) l)

Built from

Evaluation along a list of constraints

L171–174
L176
L185
L187–188
L190–193
L195–198
L200–204
L206–210
L212–214
L216–224
L226–238
L240–244
L262–266

Candidates named by labels

L272–275
L277–281
L283–286