While this submission is a draft, it cannot be used by other submissions.

Deterministic elements and the earlier replacement property

Lax369799.AutomatonProperty · concepts/Lax369799/AutomatonProperty.lean · lax-369799

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural 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
    7 concepts
    100%
    DefinitionThis conceptRelated conceptA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.

    Lean source view on GitHub

    1import Lax369799.SyntacticOrder
    2
    3/-!
    4---
    5title: Deterministic elements and the earlier replacement property
    6type: definition
    7---
    8An element is deterministic if it is the value of a set-system using only
    9letters of ranks zero and one. Given a rank-zero element f, the automaton
    10property says that an element in an accepting context can be replaced by
    11a deterministic element below it while preserving acceptance above f.
    12This is the earlier replacement interface. The revised manuscript's
    13Definition 90 requires canonical direction decomposition and regular-branch
    14acceptance as well; its syntactic instance is in ExtremalPaths.
    15-/
    16
    17namespace Lax369799.AutomatonProperty
    18open RankedSystems Flattening SetAlgebras
    19
    20def 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
    23def 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
    28def 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
    31def 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
    37end Lax369799.AutomatonProperty
    38

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…