While this submission is a draft, it cannot be used by other submissions.

Unfold-automata and regular-tree acceptance

Lax369799.UnfoldAutomata · concepts/Lax369799/UnfoldAutomata.lean · lax-369799

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural 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
    5 concepts
    100%
    DefinitionThis conceptRelated conceptA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.

    Lean source view on GitHub

    1import Lax369799.Algebras
    2import Mathlib.Algebra.Ring.Parity
    3
    4/-!
    5---
    6title: Unfold-automata and regular-tree acceptance
    7type: definition
    8---
    9An unfold-automaton has finitely many unary and nullary types. At each
    10internal vertex it chooses a tuple of unary types, one for each outgoing
    11direction; at a leaf it chooses a nullary type. Every branch must satisfy
    12a common regular word condition. Here that condition is represented by a
    13finite deterministic parity word automaton, with a final-state condition
    14for finite words. Parity uses the least priority occurring infinitely
    15often, which must be even.
    16
    17Acceptance permits a run on any finite system representing the same
    18regular tree, as in Section 6.3; a run on the input presentation alone is
    19not required. Both finite branches ending at leaves and infinite branches
    20are checked.
    21-/
    22
    23namespace Lax369799.UnfoldAutomata
    24open RankedSystems Morphisms Algebras
    25
    26structure 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
    33def 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
    37def 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
    42def 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
    46structure 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
    53abbrev 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. -/
    57structure 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
    61structure 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
    70abbrev 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. -/
    74def unrestricted {A : RankedSet} {u z : ℕ} (D : WordCondition u z) : UnfoldAutomaton A :=
    75 ⟨u, z, fun _ _ => Set.univ, fun _ => Set.univ, D⟩
    76
    77def 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
    81structure 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
    88structure 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
    94def 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
    102def 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
    105def 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
    108def Recognizes {A : RankedSet} (M : UnfoldAutomaton A) (L : Language A) : Prop :=
    109 ∀ S, S ∈ L ↔ Accepts M S
    110
    111end Lax369799.UnfoldAutomata
    112

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…