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

Algebras and recognition

Lax369799.Algebras · concepts/Lax369799/Algebras.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 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
    4 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.Morphisms
    2import Lax369799.Flattening
    3
    4/-!
    5---
    6title: Algebras and recognition
    7type: definition
    8---
    9An algebra evaluates systems over its own ranked carrier. Evaluation is
    10invariant under isomorphism, evaluates atomic systems as their labels, and
    11commutes with flattening. The explicit isomorphism clause accounts for our
    12enumeration of finite vertex sets. A regular-tree algebra also identifies
    13unfold-equivalent systems. A recognising map assigns an algebra element to
    14each letter; a set of elements of sort zero specifies acceptance.
    15See Section 3.
    16-/
    17
    18namespace Lax369799.Algebras
    19open RankedSystems Morphisms Flattening
    20
    21structure 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
    28def 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
    31abbrev Language (A : RankedSet) := Set (System A 0)
    32
    33def UnfoldInvariantLanguage {A : RankedSet} (L : Language A) : Prop :=
    34 ∀ S T, UnfoldEquivalent S.val T.val → (S ∈ L ↔ T ∈ L)
    35
    36def 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
    40def 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
    44def 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
    48structure 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
    52end Lax369799.Algebras
    53

    Discussion

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

    Loading discussion…