Bounded profiles refine finite contextual equivalence
Lax369799.BoundedProfileRefinement · concepts/Lax369799/BoundedProfileRefinement.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Initial and root profiles with variable-map fibres bounded by one more than the size of the unary observing sort determine every closed contextual acceptance test. Consequently the contextual quotient of finite presentations is rankwise finite for every regular-tree recognizable language.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.FiniteProfiles |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Bounded profiles refine finite contextual equivalence |
| 6 | type: theorem |
| 7 | --- |
| 8 | Initial and root profiles with variable-map fibres bounded by one more than |
| 9 | the size of the unary observing sort determine every closed contextual |
| 10 | acceptance test. Consequently the contextual quotient of finite presentations |
| 11 | is rankwise finite for every regular-tree recognizable language. |
| 12 | -/ |
| 13 | namespace Lax369799.BoundedProfileRefinement |
| 14 | open RankedSystems Algebras FinitePresentations FiniteProfiles |
| 15 | |
| 16 | axiom refines {A B : RankedSet} (E : Algebra B) (hE : UnfoldInvariant E) |
| 17 | [Finite (B 1)] (η : RankedMap A B) (F : Set (B 0)) (L : Language A) |
| 18 | (hL : Recognizes E η F L) {n : ℕ} (S T : FiniteSystem A n) |
| 19 | (h : BoundedProfileEquivalent (Nat.card (B 1) + 1) |
| 20 | (fun k R => E.eval k (relabelSystem η R)) S T) : |
| 21 | FiniteContextualOrder.Equivalent (FiniteAcceptance.Accepting L) S T |
| 22 | |
| 23 | axiom finite_carrier {A : RankedSet} (L : Language A) (hL : RegularTreeRecognizable L) : |
| 24 | RankwiseFinite (FiniteContextualOrder.Carrier (FiniteAcceptance.Accepting L)) |
| 25 | |
| 26 | axiom finite_carrier_recognizable {A : RankedSet} (L : Language A) |
| 27 | (hL : UnfoldInvariantLanguage L) (hrec : Recognizable L) : |
| 28 | RankwiseFinite (FiniteContextualOrder.Carrier (FiniteAcceptance.Accepting L)) |
| 29 | |
| 30 | end Lax369799.BoundedProfileRefinement |
| 31 |
Builds on
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