Clone-automata
Lax369799.BisimAutomata · concepts/Lax369799/BisimAutomata.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural 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
Lean source view on GitHub
| 1 | import Lax369799.UnfoldAutomata |
| 2 | import Lax369799.TransitionEncoding |
| 3 | import Mathlib.Data.Fin.Basic |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Clone-automata |
| 8 | type: definition |
| 9 | --- |
| 10 | An unfold-automaton over the transition alphabet is a clone-automaton when |
| 11 | its transitions are closed under uniformly duplicating every component a |
| 12 | positive 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 |
| 14 | each bᵢ. Nullary transitions are unchanged. This is the duplication |
| 15 | condition of Section 6.4; it is distinct from invariance of the recognised |
| 16 | language. |
| 17 | The identifier IsBisimAutomaton is retained from the earlier development; |
| 18 | it expresses the clone condition of the revised Section 6.4. |
| 19 | -/ |
| 20 | |
| 21 | namespace Lax369799.BisimAutomata |
| 22 | open RankedSystems Algebras UnfoldAutomata TransitionEncoding |
| 23 | |
| 24 | def Duplicate {H : Type} {n m : ℕ} (b : Fin n → H) : Fin (n * m) → H := |
| 25 | fun i => b i.divNat |
| 26 | |
| 27 | def 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 | |
| 33 | end Lax369799.BisimAutomata |
| 34 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments