Automaton property of the unpruned syntactic algebra
Lax369799.FiniteAutomatonProperty · concepts/Lax369799/FiniteAutomatonProperty.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
If the unary contextual sort is finite, every value in an accepting context can be replaced by a deterministic value below it while preserving acceptance. The proof uses the unpruned normal form and its boundary data, without a yield-continuity axiom.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.FiniteExtremal |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Automaton property of the unpruned syntactic algebra |
| 6 | type: theorem |
| 7 | --- |
| 8 | If the unary contextual sort is finite, every value in an accepting |
| 9 | context can be replaced by a deterministic value below it while preserving |
| 10 | acceptance. The proof uses the unpruned normal form and its boundary data, |
| 11 | without a yield-continuity axiom. |
| 12 | -/ |
| 13 | namespace Lax369799.FiniteAutomatonProperty |
| 14 | open RankedSystems (RankedSet) |
| 15 | open FinitePresentations FiniteContexts FiniteContextualOrder FiniteSyntacticAlgebra |
| 16 | open FiniteAcceptance FiniteExtremal |
| 17 | |
| 18 | axiom automaton_property {A : RankedSet} (L : Algebras.Language A) |
| 19 | (E : Algebra (Carrier (Accepting L))) |
| 20 | (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n), |
| 21 | E.eval n (relabel (quotientMap (Accepting L)) S) = quotientMap (Accepting L) n (flatten S)) |
| 22 | (hfinite : Finite (Carrier (Accepting L) 1)) |
| 23 | {k : ℕ} (C : Context (Carrier (Accepting L)) k 0) (a : Carrier (Accepting L) k) |
| 24 | (ha : AcceptingClass (Accepting L) (E.eval 0 (plug C (atomic a)))) : |
| 25 | ∃ δ, Deterministic E δ ∧ ClassBelow (Accepting L) δ a ∧ |
| 26 | AcceptingClass (Accepting L) (E.eval 0 (plug C (atomic δ))) |
| 27 | |
| 28 | axiom recognizable_automaton_property {A : RankedSet} (L : Algebras.Language A) |
| 29 | (hL : Algebras.UnfoldInvariantLanguage L) (hrec : Algebras.Recognizable L) |
| 30 | (E : Algebra (Carrier (Accepting L))) |
| 31 | (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n), |
| 32 | E.eval n (relabel (quotientMap (Accepting L)) S) = quotientMap (Accepting L) n (flatten S)) |
| 33 | {k : ℕ} (C : Context (Carrier (Accepting L)) k 0) (a : Carrier (Accepting L) k) |
| 34 | (ha : AcceptingClass (Accepting L) (E.eval 0 (plug C (atomic a)))) : |
| 35 | ∃ δ, Deterministic E δ ∧ ClassBelow (Accepting L) δ a ∧ |
| 36 | AcceptingClass (Accepting L) (E.eval 0 (plug C (atomic δ))) |
| 37 | |
| 38 | end Lax369799.FiniteAutomatonProperty |
| 39 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments