Unfold-automata and regular-tree acceptance
Lax369799.UnfoldAutomata · concepts/Lax369799/UnfoldAutomata.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
An unfold-automaton has finitely many unary and nullary types. At each internal vertex it chooses a tuple of unary types, one for each outgoing direction; at a leaf it chooses a nullary type. Every branch must satisfy a common regular word condition. Here that condition is represented by a finite deterministic parity word automaton, with a final-state condition for finite words. Parity uses the least priority occurring infinitely often, which must be even.
Acceptance permits a run on any finite system representing the same regular tree, as in Section 6.3; a run on the input presentation alone is not required. Both finite branches ending at leaves and infinite branches are checked.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.Algebras |
| 2 | import Mathlib.Algebra.Ring.Parity |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Unfold-automata and regular-tree acceptance |
| 7 | type: definition |
| 8 | --- |
| 9 | An unfold-automaton has finitely many unary and nullary types. At each |
| 10 | internal vertex it chooses a tuple of unary types, one for each outgoing |
| 11 | direction; at a leaf it chooses a nullary type. Every branch must satisfy |
| 12 | a common regular word condition. Here that condition is represented by a |
| 13 | finite deterministic parity word automaton, with a final-state condition |
| 14 | for finite words. Parity uses the least priority occurring infinitely |
| 15 | often, which must be even. |
| 16 | |
| 17 | Acceptance permits a run on any finite system representing the same |
| 18 | regular tree, as in Section 6.3; a run on the input presentation alone is |
| 19 | not required. Both finite branches ending at leaves and infinite branches |
| 20 | are checked. |
| 21 | -/ |
| 22 | |
| 23 | namespace Lax369799.UnfoldAutomata |
| 24 | open RankedSystems Morphisms Algebras |
| 25 | |
| 26 | structure WordCondition (unary nullary : ℕ) where |
| 27 | states : ℕ |
| 28 | initial : Fin states |
| 29 | step : Fin states → (Fin unary ⊕ Fin nullary) → Fin states |
| 30 | priority : Fin states → ℕ |
| 31 | final : Set (Fin states) |
| 32 | |
| 33 | def WordCondition.run {u z : ℕ} (D : WordCondition u z) (w : ℕ → Fin u) : ℕ → Fin D.states |
| 34 | | 0 => D.initial |
| 35 | | n + 1 => D.step (D.run w n) (.inl (w n)) |
| 36 | |
| 37 | def WordCondition.AcceptsInfinite {u z : ℕ} (D : WordCondition u z) |
| 38 | (w : ℕ → Fin u) : Prop := |
| 39 | ∃ c, Even c ∧ (∀ N, ∃ n, N ≤ n ∧ D.priority (D.run w n) = c) ∧ |
| 40 | ∀ b, b < c → ∃ N, ∀ n, N ≤ n → D.priority (D.run w n) ≠ b |
| 41 | |
| 42 | def WordCondition.AcceptsFinite {u z : ℕ} (D : WordCondition u z) |
| 43 | (w : List (Fin u)) (a : Fin z) : Prop := |
| 44 | D.step (w.foldl (fun q b => D.step q (.inl b)) D.initial) (.inr a) ∈ D.final |
| 45 | |
| 46 | structure UnfoldAutomaton (A : RankedSet) where |
| 47 | unary : ℕ |
| 48 | nullary : ℕ |
| 49 | transition : ∀ n, A (n + 1) → Set (Fin (n + 1) → Fin unary) |
| 50 | leafTransition : A 0 → Set (Fin nullary) |
| 51 | condition : WordCondition unary nullary |
| 52 | |
| 53 | abbrev Rank {A : RankedSet} {n : ℕ} (S : System A n) (v : S.val.Vertex) := |
| 54 | (S.val.graph.label v).1 |
| 55 | |
| 56 | /-- An assignment of branch types, before imposing transition constraints. -/ |
| 57 | structure Labelling {A : RankedSet} (u z : ℕ) (S : System A 0) where |
| 58 | edgeType : ∀ v, Fin (Rank S v) → Fin u |
| 59 | leafType : ∀ v, Rank S v = 0 → Fin z |
| 60 | |
| 61 | structure Run {A : RankedSet} (M : UnfoldAutomaton A) (S : System A 0) where |
| 62 | edgeType : ∀ v, Fin (Rank S v) → Fin M.unary |
| 63 | leafType : ∀ v, Rank S v = 0 → Fin M.nullary |
| 64 | transitions : ∀ v k (h : Rank S v = k + 1), |
| 65 | (fun i => edgeType v (Fin.cast h.symm i)) ∈ |
| 66 | M.transition k (h ▸ (S.val.graph.label v).2) |
| 67 | leaves : ∀ v (h : Rank S v = 0), |
| 68 | leafType v h ∈ M.leafTransition (h ▸ (S.val.graph.label v).2) |
| 69 | |
| 70 | abbrev Run.toLabelling {A : RankedSet} {M : UnfoldAutomaton A} {S : System A 0} |
| 71 | (r : Run M S) : Labelling M.unary M.nullary S := ⟨r.edgeType, r.leafType⟩ |
| 72 | |
| 73 | /-- The automaton imposing only the branch condition. -/ |
| 74 | def unrestricted {A : RankedSet} {u z : ℕ} (D : WordCondition u z) : UnfoldAutomaton A := |
| 75 | ⟨u, z, fun _ _ => Set.univ, fun _ => Set.univ, D⟩ |
| 76 | |
| 77 | def Labelling.asRun {A : RankedSet} {u z : ℕ} {S : System A 0} |
| 78 | (r : Labelling u z S) (D : WordCondition u z) : Run (unrestricted D) S := |
| 79 | ⟨r.edgeType, r.leafType, fun _ _ _ => trivial, fun _ _ => trivial⟩ |
| 80 | |
| 81 | structure FiniteBranch {A : RankedSet} (S : System A 0) (length : ℕ) where |
| 82 | vertex : Fin (length + 1) → S.val.Vertex |
| 83 | direction : ∀ i : Fin length, Fin (Rank S (vertex i.castSucc)) |
| 84 | starts : vertex 0 ∈ S.val.graph.initial |
| 85 | follows : ∀ i, S.val.graph.edge (vertex i.castSucc) (direction i).val (.inl (vertex i.succ)) |
| 86 | ends : Rank S (vertex (Fin.last length)) = 0 |
| 87 | |
| 88 | structure InfiniteBranch {A : RankedSet} (S : System A 0) where |
| 89 | vertex : ℕ → S.val.Vertex |
| 90 | direction : ∀ i, Fin (Rank S (vertex i)) |
| 91 | starts : vertex 0 ∈ S.val.graph.initial |
| 92 | follows : ∀ i, S.val.graph.edge (vertex i) (direction i).val (.inl (vertex (i + 1))) |
| 93 | |
| 94 | def Run.Accepting {A : RankedSet} {M : UnfoldAutomaton A} {S : System A 0} |
| 95 | (r : Run M S) : Prop := |
| 96 | (∀ k (b : FiniteBranch S k), M.condition.AcceptsFinite |
| 97 | (List.ofFn (fun i => r.edgeType (b.vertex i.castSucc) (b.direction i))) |
| 98 | (r.leafType (b.vertex (Fin.last k)) b.ends)) ∧ |
| 99 | (∀ b : InfiniteBranch S, M.condition.AcceptsInfinite |
| 100 | (fun i => r.edgeType (b.vertex i) (b.direction i))) |
| 101 | |
| 102 | def Labelling.Accepting {A : RankedSet} {u z : ℕ} {S : System A 0} |
| 103 | (r : Labelling u z S) (D : WordCondition u z) : Prop := (r.asRun D).Accepting |
| 104 | |
| 105 | def Accepts {A : RankedSet} (M : UnfoldAutomaton A) (S : System A 0) : Prop := |
| 106 | ∃ T : System A 0, UnfoldEquivalent S.val T.val ∧ ∃ r : Run M T, r.Accepting |
| 107 | |
| 108 | def Recognizes {A : RankedSet} (M : UnfoldAutomaton A) (L : Language A) : Prop := |
| 109 | ∀ S, S ∈ L ↔ Accepts M S |
| 110 | |
| 111 | end Lax369799.UnfoldAutomata |
| 112 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments