Periodic branch test for unfold-automata
Lax369799.UnfoldBranches · concepts/Lax369799/UnfoldBranches.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
On a finite system, checking the parity condition on ultimately periodic branches suffices for all infinite branches. Periodicity records both the vertex and the chosen outgoing direction.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.PeriodicPaths |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Periodic branch test for unfold-automata |
| 6 | type: theorem |
| 7 | --- |
| 8 | On a finite system, checking the parity condition on ultimately periodic |
| 9 | branches suffices for all infinite branches. Periodicity records both the |
| 10 | vertex and the chosen outgoing direction. |
| 11 | -/ |
| 12 | namespace Lax369799.UnfoldBranches |
| 13 | open RankedSystems UnfoldAutomata |
| 14 | |
| 15 | def Periodic {A : RankedSet} {S : System A 0} (b : InfiniteBranch S) : Prop := |
| 16 | PeriodicPaths.UltimatelyPeriodic |
| 17 | (fun n => (⟨b.vertex n, b.direction n⟩ : (v : S.val.Vertex) × Fin (Rank S v))) |
| 18 | |
| 19 | axiom periodic_test {A : RankedSet} (M : UnfoldAutomaton A) (S : System A 0) (r : Run M S) : |
| 20 | (∀ b : InfiniteBranch S, Periodic b → M.condition.AcceptsInfinite |
| 21 | (fun n => r.edgeType (b.vertex n) (b.direction n))) ↔ |
| 22 | (∀ b : InfiniteBranch S, M.condition.AcceptsInfinite |
| 23 | (fun n => r.edgeType (b.vertex n) (b.direction n))) |
| 24 | |
| 25 | end Lax369799.UnfoldBranches |
| 26 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments