Finite path-summary algebras
Lax369799.PathAlgebra · concepts/Lax369799/PathAlgebra.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
An element records, for each entry state, the possible final states and variable exits with their states. Evaluation follows a finite path through the system, composing local summaries. This gives a rankwise-finite algebra when the state set is finite, suitable for recognizing local predicates along paths from the initial vertex.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.InitialAlgebra |
| 2 | import Mathlib.Data.Fintype.Powerset |
| 3 | import Mathlib.Data.Fintype.Pi |
| 4 | import Mathlib.Data.Fintype.Prod |
| 5 | |
| 6 | /-! |
| 7 | --- |
| 8 | title: Finite path-summary algebras |
| 9 | type: theorem |
| 10 | --- |
| 11 | An element records, for each entry state, the possible final states and |
| 12 | variable exits with their states. Evaluation follows a finite path through |
| 13 | the system, composing local summaries. This gives a rankwise-finite algebra |
| 14 | when the state set is finite, suitable for recognizing local predicates |
| 15 | along paths from the initial vertex. |
| 16 | -/ |
| 17 | namespace Lax369799.PathAlgebra |
| 18 | open RankedSystems Algebras InitialAlgebra |
| 19 | |
| 20 | abbrev Result (Q : Type) (n : ℕ) := Q ⊕ (Fin n × Q) |
| 21 | abbrev Carrier (Q : Type) : RankedSet := fun n => Q → Set (Result Q n) |
| 22 | |
| 23 | def Halt {Q : Type} (a : Symbol (Carrier Q)) (q r : Q) : Prop := |
| 24 | Sum.inl r ∈ a.2 q |
| 25 | |
| 26 | def Exit {Q : Type} (a : Symbol (Carrier Q)) (d : ℕ) (q r : Q) : Prop := |
| 27 | ∃ i : Fin a.1, i.val = d ∧ Sum.inr (i, r) ∈ a.2 q |
| 28 | |
| 29 | inductive Run {Q V : Type} {n : ℕ} (G : Presentation (Carrier Q) n V) : |
| 30 | V → Q → Result Q n → Prop |
| 31 | | halt {v q r} (h : Halt (G.label v) q r) : Run G v q (.inl r) |
| 32 | | exit {v q r i} (d : ℕ) |
| 33 | (h : Exit (G.label v) d q r) (he : G.edge v d (.inr i)) : |
| 34 | Run G v q (.inr (i, r)) |
| 35 | | step {v w q r out} (d : ℕ) |
| 36 | (h : Exit (G.label v) d q r) (he : G.edge v d (.inl w)) |
| 37 | (tail : Run G w r out) : Run G v q out |
| 38 | |
| 39 | noncomputable def evaluate {Q : Type} (n : ℕ) (S : System (Carrier Q) n) : Carrier Q n := |
| 40 | fun q out => Run S.val.graph (initial S) q out |
| 41 | |
| 42 | axiom algebra (Q : Type) : ∃ E : Algebra (Carrier Q), E.eval = evaluate |
| 43 | |
| 44 | axiom finite_carrier (Q : Type) [Finite Q] : RankwiseFinite (Carrier Q) |
| 45 | |
| 46 | end Lax369799.PathAlgebra |
| 47 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments