Quantitative automata for the finite bisimulation theorem
Lax369799.QuantitativeAutomata · concepts/Lax369799/QuantitativeAutomata.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
A bound for the recognizing algebra gives explicit bounds for the unary and nullary types, word states and priorities of the equivalent clone automaton. The infinite stabilization defining its transition table does not change any of these finite bounds.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.QuantitativeProfiles |
| 2 | import Lax369799.QuantitativeWordConditions |
| 3 | import Lax369799.BisimAutomatonTheorem |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Quantitative automata for the finite bisimulation theorem |
| 8 | type: theorem |
| 9 | --- |
| 10 | A bound for the recognizing algebra gives explicit bounds for the unary |
| 11 | and nullary types, word states and priorities of the equivalent clone |
| 12 | automaton. The infinite stabilization defining its transition table does |
| 13 | not change any of these finite bounds. |
| 14 | -/ |
| 15 | |
| 16 | namespace Lax369799.QuantitativeAutomata |
| 17 | |
| 18 | def unaryBound (f : ℕ → ℕ) := QuantitativeProfiles.quotientBound f 1 |
| 19 | def nullaryBound (f : ℕ → ℕ) := QuantitativeProfiles.quotientBound f 0 |
| 20 | |
| 21 | def stateBound (f : ℕ → ℕ) := |
| 22 | QuantitativeWordConditions.stateBound (unaryBound f) (nullaryBound f) |
| 23 | |
| 24 | def priorityBound (f : ℕ → ℕ) := |
| 25 | QuantitativeWordConditions.priorityBound (unaryBound f) |
| 26 | |
| 27 | open TransitionEncoding UnfoldAutomata |
| 28 | |
| 29 | axiom automaton_bound {P : Type} [Finite P] |
| 30 | (L : Algebras.Language (TransitionAlphabet P)) |
| 31 | (hL : ∀ S T,RankedBisimilar S T → (S ∈ L ↔ T ∈ L)) |
| 32 | (f : ℕ → ℕ) (hA : QuantitativeRecognition.Bound f L) : |
| 33 | ∃ M : UnfoldAutomaton (TransitionAlphabet P), |
| 34 | BisimAutomata.IsBisimAutomaton M ∧ Recognizes M L ∧ |
| 35 | M.unary ≤ unaryBound f ∧ M.nullary ≤ nullaryBound f ∧ |
| 36 | M.condition.states ≤ stateBound f ∧ (∀ q,M.condition.priority q ≤ priorityBound f) |
| 37 | |
| 38 | end Lax369799.QuantitativeAutomata |
Builds on
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments