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

Clone-automata

Lax369799.BisimAutomata · concepts/Lax369799/BisimAutomata.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 over the transition alphabet is a clone-automaton when its transitions are closed under uniformly duplicating every component a positive number of times. Thus a transition of arity n with types (b₁,…,bₙ) entails a transition of arity nm with m consecutive copies of each bᵢ. Nullary transitions are unchanged. This is the duplication condition of Section 6.4; it is distinct from invariance of the recognised language. The identifier IsBisimAutomaton is retained from the earlier development; it expresses the clone condition of the revised Section 6.4.

    Concept map
    8 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.UnfoldAutomata
    2import Lax369799.TransitionEncoding
    3import Mathlib.Data.Fin.Basic
    4
    5/-!
    6---
    7title: Clone-automata
    8type: definition
    9---
    10An unfold-automaton over the transition alphabet is a clone-automaton when
    11its transitions are closed under uniformly duplicating every component a
    12positive number of times. Thus a transition of arity n with types
    13(b₁,…,bₙ) entails a transition of arity nm with m consecutive copies of
    14each bᵢ. Nullary transitions are unchanged. This is the duplication
    15condition of Section 6.4; it is distinct from invariance of the recognised
    16language.
    17The identifier IsBisimAutomaton is retained from the earlier development;
    18it expresses the clone condition of the revised Section 6.4.
    19-/
    20
    21namespace Lax369799.BisimAutomata
    22open RankedSystems Algebras UnfoldAutomata TransitionEncoding
    23
    24def Duplicate {H : Type} {n m : ℕ} (b : Fin n → H) : Fin (n * m) → H :=
    25 fun i => b i.divNat
    26
    27def IsBisimAutomaton {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) : Prop :=
    28 ∀ (ν : Set P) (n : ℕ) (b : Fin (n + 1) → Fin M.unary),
    29 b ∈ M.transition n ν → ∀ m, 0 < m →
    30 ∃ (k : ℕ) (h : (n + 1) * m = k + 1),
    31 (fun i => Duplicate b (Fin.cast h.symm i)) ∈ M.transition k ν
    32
    33end Lax369799.BisimAutomata
    34

    Discussion

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

    Loading discussion…