Monotonicity of algebraic branch conditions
Lax369799.BranchMonotonicity · concepts/Lax369799/BranchMonotonicity.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Unary application and finite branch evaluation are monotone. For a finite unary sort, increasing every letter of an accepted infinite word also preserves acceptance. A common subsequence of factorization cuts compares the accepting linked pairs. These comparisons underlie the rerouting construction of Lemma 108.
Concept map
Evidence
This concept declares 8 statements. Each proof establishes one of them relative to its assumptions.
1 act_mono proven
2 block_append proven
3 block_mono proven
4 condition proven
5 finite_mono proven
6 infinite_mono proven
7 lasso_mono proven
8 product_mono proven
Lean source view on GitHub
| 1 | import Lax369799.SetSystemAlgebras |
| 2 | import Lax369799.AlgebraicOmegaWords |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Monotonicity of algebraic branch conditions |
| 7 | type: theorem |
| 8 | --- |
| 9 | Unary application and finite branch evaluation are monotone. For a finite |
| 10 | unary sort, increasing every letter of an accepted infinite word also |
| 11 | preserves acceptance. A common subsequence of factorization cuts compares |
| 12 | the accepting linked pairs. These comparisons underlie the rerouting |
| 13 | construction of Lemma 108. |
| 14 | -/ |
| 15 | namespace Lax369799.BranchMonotonicity |
| 16 | open RankedSystems (RankedSet) |
| 17 | open FinitePresentations SetSystemAlgebras UnaryComposition UnaryFactorization |
| 18 | |
| 19 | def ConditionMonotone {A : RankedSet} (E : SetAlgebra A) |
| 20 | [Fintype (A 1)] [Fintype (A 0)] |
| 21 | (D : UnfoldAutomata.WordCondition (Fintype.card (A 1)) (Fintype.card (A 0))) : Prop := |
| 22 | (∀ w v a b, List.Forall₂ (fun x y => Below E |
| 23 | ((Fintype.equivFin (A 1)).symm x) ((Fintype.equivFin (A 1)).symm y)) w v → |
| 24 | Below E ((Fintype.equivFin (A 0)).symm a) ((Fintype.equivFin (A 0)).symm b) → |
| 25 | D.AcceptsFinite w a → D.AcceptsFinite v b) ∧ |
| 26 | (∀ w v, (∀ i, Below E ((Fintype.equivFin (A 1)).symm (w i)) |
| 27 | ((Fintype.equivFin (A 1)).symm (v i))) → |
| 28 | D.AcceptsInfinite w → D.AcceptsInfinite v) |
| 29 | |
| 30 | axiom condition {A : RankedSet} (E : SetAlgebra A) [Fintype (A 1)] [Fintype (A 0)] |
| 31 | (F : Set (A 0)) (hF : ∀ a b, a ∈ F → Below E a b → b ∈ F) |
| 32 | (D : UnfoldAutomata.WordCondition (Fintype.card (A 1)) (Fintype.card (A 0))) |
| 33 | (hD : (∀ w a, D.AcceptsFinite w a ↔ |
| 34 | FiniteBranchWords.value E.toAlgebra (w.map (Fintype.equivFin (A 1)).symm) |
| 35 | ((Fintype.equivFin (A 0)).symm a) ∈ F) ∧ |
| 36 | (∀ w, D.AcceptsInfinite w ↔ AlgebraicOmegaWords.Accepts E.toAlgebra F |
| 37 | (fun n => (Fintype.equivFin (A 1)).symm (w n)))) : ConditionMonotone E D |
| 38 | |
| 39 | axiom act_mono {A : RankedSet} (E : SetAlgebra A) {n : ℕ} |
| 40 | {a a' : A 1} {b b' : A n} (ha : Below E a a') (hb : Below E b b') : |
| 41 | Below E (act E.toAlgebra a b) (act E.toAlgebra a' b') |
| 42 | |
| 43 | axiom product_mono {A : RankedSet} (E : SetAlgebra A) |
| 44 | {a a' b b' : A 1} (ha : Below E a a') (hb : Below E b b') : |
| 45 | Below E (product E.toAlgebra a b) (product E.toAlgebra a' b') |
| 46 | |
| 47 | axiom block_mono {A : RankedSet} (E : SetAlgebra A) |
| 48 | (w v : ℕ → A 1) (h : ∀ i, Below E (w i) (v i)) (i j : ℕ) : |
| 49 | Below E (block E.toAlgebra w i j) (block E.toAlgebra v i j) |
| 50 | |
| 51 | axiom finite_mono {A : RankedSet} (E : SetAlgebra A) |
| 52 | {w v : List (A 1)} (h : List.Forall₂ (Below E) w v) |
| 53 | {a b : A 0} (hab : Below E a b) : |
| 54 | Below E (FiniteBranchWords.value E.toAlgebra w a) |
| 55 | (FiniteBranchWords.value E.toAlgebra v b) |
| 56 | |
| 57 | axiom block_append {A : RankedSet} (E : FiniteSyntacticAlgebra.Algebra A) |
| 58 | (w : ℕ → A 1) {i j k : ℕ} (hij : i < j) (hjk : j < k) : |
| 59 | block E w i k = product E (block E w i j) (block E w j k) |
| 60 | |
| 61 | axiom lasso_mono {A : RankedSet} (E : SetAlgebra A) |
| 62 | {a a' e e' : A 1} (ha : Below E a a') (he : Below E e e') : |
| 63 | Below E (E.eval 0 (lasso a e)) (E.eval 0 (lasso a' e')) |
| 64 | |
| 65 | axiom infinite_mono {A : RankedSet} (E : SetAlgebra A) [Finite (A 1)] |
| 66 | (F : Set (A 0)) (hF : ∀ a b, a ∈ F → Below E a b → b ∈ F) |
| 67 | (w v : ℕ → A 1) (h : ∀ i, Below E (w i) (v i)) |
| 68 | (hw : AlgebraicOmegaWords.Accepts E.toAlgebra F w) : |
| 69 | AlgebraicOmegaWords.Accepts E.toAlgebra F v |
| 70 | |
| 71 | end Lax369799.BranchMonotonicity |
| 72 |
Used by
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments