Algebraic transition tables for unfold-automata
Lax369799.AlgebraicTransitions · concepts/Lax369799/AlgebraicTransitions.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Unary and nullary algebra elements serve as edge and leaf types. A positive-arity transition is allowed precisely when the parallel unary value lies below the letter value. The automaton property and unary normal form give an allowed transition preserving acceptance in each accepting context. The word condition is supplied separately.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.DeterministicElements |
| 2 | import Lax369799.UnfoldAutomata |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Algebraic transition tables for unfold-automata |
| 7 | type: theorem |
| 8 | --- |
| 9 | Unary and nullary algebra elements serve as edge and leaf types. A |
| 10 | positive-arity transition is allowed precisely when the parallel unary |
| 11 | value lies below the letter value. The automaton property and unary |
| 12 | normal form give an allowed transition preserving acceptance in each |
| 13 | accepting context. The word condition is supplied separately. |
| 14 | -/ |
| 15 | namespace Lax369799.AlgebraicTransitions |
| 16 | open RankedSystems SetAlgebras AutomatonProperty UnfoldAutomata |
| 17 | |
| 18 | noncomputable def decodeTypes {B : RankedSet} [Fintype (B 1)] {n : ℕ} |
| 19 | (b : Fin n → Fin (Fintype.card (B 1))) : Fin n → B 1 := |
| 20 | fun i => (Fintype.equivFin (B 1)).symm (b i) |
| 21 | |
| 22 | noncomputable def automaton {A B : RankedSet} [Fintype (B 1)] [Fintype (B 0)] |
| 23 | (E : SetAlgebra B) (η : RankedMap A B) |
| 24 | (D : WordCondition (Fintype.card (B 1)) (Fintype.card (B 0))) : UnfoldAutomaton A where |
| 25 | unary := Fintype.card (B 1) |
| 26 | nullary := Fintype.card (B 0) |
| 27 | transition := fun n a => {b | Below E |
| 28 | (E.eval (n + 1) (DeterministicElements.parallel (decodeTypes b))) (η (n + 1) a)} |
| 29 | leafTransition := fun a => {(Fintype.equivFin (B 0)) (η 0 a)} |
| 30 | condition := D |
| 31 | |
| 32 | axiom accepting_transition {A B : RankedSet} [Fintype (B 1)] [Fintype (B 0)] |
| 33 | (E : SetAlgebra B) (f : B 0) (hE : HasAutomatonProperty E f) (η : RankedMap A B) |
| 34 | (D : WordCondition (Fintype.card (B 1)) (Fintype.card (B 0))) |
| 35 | (n : ℕ) (a : A (n + 1)) (C : Flattening.SetContext B (n + 1) 0) |
| 36 | (h : Below E f (E.eval 0 (Flattening.plug C (atomic (η (n + 1) a))))) : |
| 37 | ∃ b ∈ (automaton E η D).transition n a, |
| 38 | Below E f (E.eval 0 (Flattening.plug C |
| 39 | (atomic (E.eval (n + 1) (DeterministicElements.parallel (decodeTypes b)))))) |
| 40 | |
| 41 | end Lax369799.AlgebraicTransitions |
| 42 |
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments