Finite-state evaluation of terminating branch words
Lax369799.FiniteBranchWords · concepts/Lax369799/FiniteBranchWords.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
A finite unary word followed by a nullary value is evaluated by iterated unary application. A deterministic word automaton stores the action of the prefix on the nullary sort. Its state set is finite whenever that sort is finite. Infinite words require a separate acceptance condition.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.FiniteSyntacticAlgebra |
| 2 | import Mathlib.Computability.DFA |
| 3 | import Mathlib.Data.Fintype.Option |
| 4 | import Mathlib.Data.Fintype.Pi |
| 5 | import Mathlib.Data.Fintype.Sum |
| 6 | |
| 7 | /-! |
| 8 | --- |
| 9 | title: Finite-state evaluation of terminating branch words |
| 10 | type: theorem |
| 11 | --- |
| 12 | A finite unary word followed by a nullary value is evaluated by iterated |
| 13 | unary application. A deterministic word automaton stores the action of |
| 14 | the prefix on the nullary sort. Its state set is finite whenever that |
| 15 | sort is finite. Infinite words require a separate acceptance condition. |
| 16 | -/ |
| 17 | namespace Lax369799.FiniteBranchWords |
| 18 | open RankedSystems (RankedSet) |
| 19 | open FinitePresentations FiniteSyntacticAlgebra |
| 20 | |
| 21 | def application {A : RankedSet} (b : A 1) (a : A 0) : FiniteSystem A 0 where |
| 22 | size := 2 |
| 23 | graph := { |
| 24 | label := Fin.cases ⟨1, b⟩ (fun _ => ⟨0, a⟩) |
| 25 | initial := {0} |
| 26 | root := ∅ |
| 27 | edge := fun v d t => v = 0 ∧ d = 0 ∧ t = .inl 1 |
| 28 | direction_valid := by rintro v d t ⟨rfl, rfl, _⟩; exact Nat.zero_lt_one } |
| 29 | |
| 30 | def act {A : RankedSet} (E : Algebra A) (b : A 1) (a : A 0) : A 0 := |
| 31 | E.eval 0 (application b a) |
| 32 | |
| 33 | def value {A : RankedSet} (E : Algebra A) (w : List (A 1)) (a : A 0) : A 0 := |
| 34 | w.foldr (act E) a |
| 35 | |
| 36 | noncomputable def chain {A : RankedSet} : List (A 1) → A 0 → FiniteSystem A 0 |
| 37 | | [], a => atomic a |
| 38 | | b :: w, a => flatten (application (atomic b) (chain w a)) |
| 39 | |
| 40 | axiom chain_evaluation {A : RankedSet} (E : Algebra A) (w : List (A 1)) (a : A 0) : |
| 41 | E.eval 0 (chain w a) = value E w a |
| 42 | |
| 43 | abbrev State (Z : Type) := Option ((Z → Z) ⊕ Z) |
| 44 | |
| 45 | def machine {U Z : Type} (f : U → Z → Z) (F : Set Z) : DFA (U ⊕ Z) (State Z) where |
| 46 | start := some (.inl id) |
| 47 | step := fun s c => match s, c with |
| 48 | | some (.inl g), .inl b => some (.inl (g ∘ f b)) |
| 49 | | some (.inl g), .inr a => some (.inr (g a)) |
| 50 | | _, _ => none |
| 51 | accept := {s | ∃ a ∈ F, s = some (.inr a)} |
| 52 | |
| 53 | axiom evaluate {U Z : Type} (f : U → Z → Z) (F : Set Z) |
| 54 | (w : List U) (a : Z) : |
| 55 | (machine f F).eval (w.map Sum.inl ++ [Sum.inr a]) = some (.inr (w.foldr f a)) |
| 56 | |
| 57 | axiom accepts {A : RankedSet} (E : Algebra A) (F : Set (A 0)) |
| 58 | (w : List (A 1)) (a : A 0) : |
| 59 | w.map Sum.inl ++ [Sum.inr a] ∈ (machine (act E) F).accepts ↔ E.eval 0 (chain w a) ∈ F |
| 60 | |
| 61 | axiom finite_states {Z : Type} [Finite Z] : Finite (State Z) |
| 62 | |
| 63 | end Lax369799.FiniteBranchWords |
| 64 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments