Algebras and recognition
Lax369799.Algebras · concepts/Lax369799/Algebras.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
An algebra evaluates systems over its own ranked carrier. Evaluation is invariant under isomorphism, evaluates atomic systems as their labels, and commutes with flattening. The explicit isomorphism clause accounts for our enumeration of finite vertex sets. A regular-tree algebra also identifies unfold-equivalent systems. A recognising map assigns an algebra element to each letter; a set of elements of sort zero specifies acceptance. See Section 3.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.Morphisms |
| 2 | import Lax369799.Flattening |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Algebras and recognition |
| 7 | type: definition |
| 8 | --- |
| 9 | An algebra evaluates systems over its own ranked carrier. Evaluation is |
| 10 | invariant under isomorphism, evaluates atomic systems as their labels, and |
| 11 | commutes with flattening. The explicit isomorphism clause accounts for our |
| 12 | enumeration of finite vertex sets. A regular-tree algebra also identifies |
| 13 | unfold-equivalent systems. A recognising map assigns an algebra element to |
| 14 | each letter; a set of elements of sort zero specifies acceptance. |
| 15 | See Section 3. |
| 16 | -/ |
| 17 | |
| 18 | namespace Lax369799.Algebras |
| 19 | open RankedSystems Morphisms Flattening |
| 20 | |
| 21 | structure Algebra (A : RankedSet) where |
| 22 | eval : ∀ n, System A n → A n |
| 23 | isomorphic : ∀ n (S T : System A n), Isomorphic S.val T.val → eval n S = eval n T |
| 24 | unit : ∀ n (a : A n), eval n (atomicSystem a) = a |
| 25 | associative : ∀ n (S : System (System A) n) (T : System A n), |
| 26 | SystemFlattening S T → eval n (relabelSystem eval S) = eval n T |
| 27 | |
| 28 | def UnfoldInvariant {A : RankedSet} (E : Algebra A) : Prop := |
| 29 | ∀ n (S T : System A n), UnfoldEquivalent S.val T.val → E.eval n S = E.eval n T |
| 30 | |
| 31 | abbrev Language (A : RankedSet) := Set (System A 0) |
| 32 | |
| 33 | def UnfoldInvariantLanguage {A : RankedSet} (L : Language A) : Prop := |
| 34 | ∀ S T, UnfoldEquivalent S.val T.val → (S ∈ L ↔ T ∈ L) |
| 35 | |
| 36 | def Recognizes {A B : RankedSet} (E : Algebra B) (η : RankedMap A B) |
| 37 | (F : Set (B 0)) (L : Language A) : Prop := |
| 38 | ∀ T, T ∈ L ↔ E.eval 0 (relabelSystem η T) ∈ F |
| 39 | |
| 40 | def Recognizable {A : RankedSet} (L : Language A) : Prop := |
| 41 | ∃ (B : RankedSet) (E : Algebra B) (η : RankedMap A B) (F : Set (B 0)), |
| 42 | RankwiseFinite B ∧ Recognizes E η F L |
| 43 | |
| 44 | def RegularTreeRecognizable {A : RankedSet} (L : Language A) : Prop := |
| 45 | ∃ (B : RankedSet) (E : Algebra B) (η : RankedMap A B) (F : Set (B 0)), |
| 46 | RankwiseFinite B ∧ UnfoldInvariant E ∧ Recognizes E η F L |
| 47 | |
| 48 | structure AlgebraMorphism {A B : RankedSet} (E : Algebra A) (F : Algebra B) where |
| 49 | map : RankedMap A B |
| 50 | commutes : ∀ n (S : System A n), F.eval n (relabelSystem map S) = map n (E.eval n S) |
| 51 | |
| 52 | end Lax369799.Algebras |
| 53 |
Used by
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments