Simultaneous deterministic replacements in finite presentations
Lax369799.FiniteVertexReplacement · concepts/Lax369799/FiniteVertexReplacement.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Marking a vertex gives a context that retains all its incident edges and boundary marks. Iterating the automaton property over the finite vertex set replaces every label by a deterministic value below it and preserves acceptance. No parallel-unary normal form is used.
Concept map
Evidence
This concept declares 2 statements. Each proof establishes one of them relative to its assumptions.
1 simultaneous_replacement proven
2 vertex_context proven
Lean source view on GitHub
| 1 | import Lax369799.ExpandedSyntacticAlgebra |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Simultaneous deterministic replacements in finite presentations |
| 6 | type: theorem |
| 7 | --- |
| 8 | Marking a vertex gives a context that retains all its incident edges and |
| 9 | boundary marks. Iterating the automaton property over the finite vertex |
| 10 | set replaces every label by a deterministic value below it and preserves |
| 11 | acceptance. No parallel-unary normal form is used. |
| 12 | -/ |
| 13 | namespace Lax369799.FiniteVertexReplacement |
| 14 | open RankedSystems (RankedSet) |
| 15 | open FinitePresentations FiniteContexts FiniteContextualOrder FiniteAcceptance |
| 16 | open FiniteSyntacticAlgebra ExpandedSyntacticAlgebra |
| 17 | |
| 18 | axiom vertex_context {A B : RankedSet} {n : ℕ} (P : FiniteSystem B n) |
| 19 | (q : ∀ v : P.Vertex, A (P.graph.label v).1) (v : P.Vertex) : |
| 20 | ∃ C : Context A (P.graph.label v).1 n, |
| 21 | ∀ r : ∀ w : P.Vertex, A (P.graph.label w).1, |
| 22 | (∀ w, w ≠ v → q w = r w) → |
| 23 | Isomorphic (plug C (atomic (r v))) (withLabels P r) |
| 24 | |
| 25 | axiom simultaneous_replacement {A B : RankedSet} (L : Algebras.Language A) |
| 26 | (hL : Algebras.UnfoldInvariantLanguage L) (hrec : Algebras.Recognizable L) |
| 27 | (E : SyntacticAlgebra L) (P : FiniteSystem B 0) |
| 28 | (q : ∀ v : P.Vertex, Carrier (Accepting L) (P.graph.label v).1) |
| 29 | (hq : AcceptingClass (Accepting L) (E.algebra.eval 0 (withLabels P q))) : |
| 30 | ∃ r : ∀ v : P.Vertex, Carrier (Accepting L) (P.graph.label v).1, |
| 31 | (∀ v, FiniteExtremal.Deterministic E.algebra (r v) ∧ ClassBelow (Accepting L) (r v) (q v)) ∧ |
| 32 | AcceptingClass (Accepting L) (E.algebra.eval 0 (withLabels P r)) |
| 33 | |
| 34 | end Lax369799.FiniteVertexReplacement |
| 35 |
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