Deterministic elements and the earlier replacement property
Lax369799.AutomatonProperty · concepts/Lax369799/AutomatonProperty.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
An element is deterministic if it is the value of a set-system using only letters of ranks zero and one. Given a rank-zero element f, the automaton property says that an element in an accepting context can be replaced by a deterministic element below it while preserving acceptance above f. This is the earlier replacement interface. The revised manuscript's Definition 90 requires canonical direction decomposition and regular-branch acceptance as well; its syntactic instance is in ExtremalPaths.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.SyntacticOrder |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Deterministic elements and the earlier replacement property |
| 6 | type: definition |
| 7 | --- |
| 8 | An element is deterministic if it is the value of a set-system using only |
| 9 | letters of ranks zero and one. Given a rank-zero element f, the automaton |
| 10 | property says that an element in an accepting context can be replaced by |
| 11 | a deterministic element below it while preserving acceptance above f. |
| 12 | This is the earlier replacement interface. The revised manuscript's |
| 13 | Definition 90 requires canonical direction decomposition and regular-branch |
| 14 | acceptance as well; its syntactic instance is in ExtremalPaths. |
| 15 | -/ |
| 16 | |
| 17 | namespace Lax369799.AutomatonProperty |
| 18 | open RankedSystems Flattening SetAlgebras |
| 19 | |
| 20 | def Deterministic {A : RankedSet} (E : SetAlgebra A) {n : ℕ} (a : A n) : Prop := |
| 21 | ∃ S : SetSystem A n, (∀ v, (S.graph.label v).1 ≤ 1) ∧ E.eval n S = a |
| 22 | |
| 23 | def HasAutomatonProperty {A : RankedSet} (E : SetAlgebra A) (f : A 0) : Prop := |
| 24 | ∀ n (C : SetContext A n 0) (a : A n), Below E f (E.eval 0 (plug C (atomic a))) → |
| 25 | ∃ δ : A n, Deterministic E δ ∧ Below E δ a ∧ |
| 26 | Below E f (E.eval 0 (plug C (atomic δ))) |
| 27 | |
| 28 | def PlantInvariant {A : RankedSet} (E : SetAlgebra A) (f : A 0) : Prop := |
| 29 | ∀ S : SetSystem A 0, Below E f (E.eval 0 S) ↔ Below E f (E.eval 0 (plant S)) |
| 30 | |
| 31 | def OrderSeparating {A : RankedSet} (E : SetAlgebra A) (f : A 0) : Prop := |
| 32 | ∀ n (a b : A n), |
| 33 | (∀ C : SetContext A n 0, |
| 34 | Below E f (E.eval 0 (plug C (atomic a))) → |
| 35 | Below E f (E.eval 0 (plug C (atomic b)))) → Below E a b |
| 36 | |
| 37 | end Lax369799.AutomatonProperty |
| 38 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments