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

Finite branch observations of a run

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

proven

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

    Theorem

    A terminating branch determines a unary path followed by its nullary leaf. This path maps into the flattened run presentation. Consequently an accepted evaluated run has accepted terminating branch observations.

    Concept map
    72 concepts; 2 descendants hidden
    100%
    Algebraic decomposition with boundary dataAlgebraic transition tables forunfold-automataAlgebras and recognitionDeterministic elements and the earlierreplacement propertyBounded profiles refine finite contextualequivalenceUnary types preserving explicit choicesSplitting outgoing choices in cyclic unarycontextsContext decomposition with hole boundarydataRelabelling and deterministic contextsubstitutionFinite resolution approximation in a contextSmallification preserving identitycontinuationsUnary normal form of deterministic elementsDeterministic normal forms with identitycontinuationsUnary continuations of deterministiccontextsAcceptance certificates retaining expandedresolutionsContinuity through expanded representativesSyntactic algebras with expanded continuityTransition tables for the algebra withexpanded continuityPlanted normal contexts and deterministicwitnessesUnary types selected by extremal refinementYield acceptance of finite presentationsAutomaton property of the unprunedsyntactic algebraFinite-state evaluation of terminating branchwordsContexts over finite presentationsContextual preorders on finite presentationsFinite yield approximation of contextualacceptance and orderContext decomposition without pruningExtremal unary data for finite presentationsUnions of initial and root marksMorphisms of unpruned finite presentationsUnary normal forms without pruningOrdered syntactic algebras of finitepresentationsEvaluation of finite path graphsFinite presentations without reachabilitypruningSmall profiles of finite presentationsFinite approximation of a flatteningresolutionNormal forms retaining split-variableresolutionsContextual quotient algebras of finitepresentationsSimultaneous deterministic replacements infinite presentationsYield continuity for finite-presentationcontextsFinite sums are contextual meetsFlattening and contextsFlattening, resolutions, and yield congruenceFunctional restrictions of selected unarygraphsFinite support for initial observationsMorphisms, unfoldings, and yieldsBounded profiles in root-free substitutionpatternsBounded optimal flatten-resolutionsParallel replacements in accepting contextsLocally surjective maps of finitepresentationsResolution values of finite presentationsTransfer of resolutions through boundedprofilesRanked sets, set-systems, and systemsRenaming variables in systems andresolutionsCompression of the variables offlatten-resolutionsFinite families of split-variable resolutionsResolutions and bounded profilesRoot entries in substituted presentationsFinite support for root observationsFinite branch observations of a runUnary presentations associated with legalrunsChoice preservation of extremally selectedunary typesParallel transitions with selected unarycomponentsThe earlier continuity-bearing set-algebrainterfaceExtremal witnesses with separate rootedcomponentsSyntactic set-algebras and rankwise finitenessYield-syntactic order and quotientEvaluation and variable renaming inregular-tree algebrasVariable exits of unary systemsUnfold-automata and regular-tree acceptanceCompression of variable maps by finiteobservationsContinuity of yields in a context
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    This concept declares 5 statements. Each proof establishes one of them relative to its assumptions.

    Lean source view on GitHub

    1import Lax369799.RunPresentations
    2import Lax369799.FinitePathEvaluation
    3
    4/-!
    5---
    6title: Finite branch observations of a run
    7type: theorem
    8---
    9A terminating branch determines a unary path followed by its nullary leaf.
    10This path maps into the flattened run presentation. Consequently an
    11accepted evaluated run has accepted terminating branch observations.
    12-/
    13namespace Lax369799.RunBranchObservations
    14open RankedSystems (RankedSet System)
    15open FinitePresentations FiniteContextualOrder FiniteAcceptance
    16open FiniteSyntacticAlgebra ExpandedSyntacticAlgebra UnfoldAutomata ExpandedTransitions
    17
    18noncomputable def path {A : RankedSet} (L : Algebras.Language A)
    19 [Fintype (Carrier (Accepting L) 1)] [Fintype (Carrier (Accepting L) 0)]
    20 (E : SyntacticAlgebra L)
    21 (D : WordCondition (Fintype.card (Carrier (Accepting L) 1))
    22 (Fintype.card (Carrier (Accepting L) 0)))
    23 {S : System A 0} (r : Labelling (Fintype.card (Carrier (Accepting L) 1))
    24 (Fintype.card (Carrier (Accepting L) 0)) S)
    25 {k : ℕ} (b : FiniteBranch S k) : FiniteSystem (Carrier (Accepting L)) 0 where
    26 size := k + 1
    27 graph := {
    28 label := Fin.lastCases
    29 ⟨0, (Fintype.equivFin (Carrier (Accepting L) 0)).symm
    30 (r.leafType (b.vertex (Fin.last k)) b.ends)⟩
    31 (fun i => ⟨1, (Fintype.equivFin (Carrier (Accepting L) 1)).symm
    32 (r.edgeType (b.vertex i.castSucc) (b.direction i))⟩)
    33 initial := {0}
    34 root := ∅
    35 edge := fun v d t => ∃ i : Fin k, v = i.castSucc ∧ d = 0 ∧ t = .inl i.succ
    36 direction_valid := by
    37 rintro v d t ⟨i, rfl, rfl, rfl⟩
    38 simp }
    39
    40axiom path_morphism {A : RankedSet} (L : Algebras.Language A)
    41 [Fintype (Carrier (Accepting L) 1)] [Fintype (Carrier (Accepting L) 0)]
    42 (E : SyntacticAlgebra L)
    43 (D : WordCondition (Fintype.card (Carrier (Accepting L) 1))
    44 (Fintype.card (Carrier (Accepting L) 0)))
    45 {S : System A 0} (r : Labelling (Fintype.card (Carrier (Accepting L) 1))
    46 (Fintype.card (Carrier (Accepting L) 0)) S)
    47 {k : ℕ} (b : FiniteBranch S k) :
    48 Nonempty (FiniteMorphisms.Morphism (path L E D r b) (RunPresentations.presentation L E D r))
    49
    50axiom path_accepting {A : RankedSet} (L : Algebras.Language A)
    51 [Fintype (Carrier (Accepting L) 1)] [Fintype (Carrier (Accepting L) 0)]
    52 (E : SyntacticAlgebra L)
    53 (D : WordCondition (Fintype.card (Carrier (Accepting L) 1))
    54 (Fintype.card (Carrier (Accepting L) 0)))
    55 {S : System A 0} (r : Labelling (Fintype.card (Carrier (Accepting L) 1))
    56 (Fintype.card (Carrier (Accepting L) 0)) S)
    57 (hr : AcceptingClass (Accepting L) (E.algebra.eval 0
    58 (withLabels (ofSetSystem S.val) (runLabel L E D r))))
    59 {k : ℕ} (b : FiniteBranch S k) :
    60 AcceptingClass (Accepting L) (E.algebra.eval 0 (path L E D r b))
    61
    62/-- A finite graph describing a regular infinite branch of the input. -/
    63structure RegularBranch {A : RankedSet} (S : System A 0) where
    64 size : ℕ
    65 start : Fin size
    66 next : Fin size → Fin size
    67 vertex : Fin size → S.val.Vertex
    68 direction : ∀ i, Fin (Rank S (vertex i))
    69 starts : vertex start ∈ S.val.graph.initial
    70 follows : ∀ i, S.val.graph.edge (vertex i) (direction i).val (.inl (vertex (next i)))
    71
    72noncomputable def regularPath {A : RankedSet} (L : Algebras.Language A)
    73 [Fintype (Carrier (Accepting L) 1)] [Fintype (Carrier (Accepting L) 0)]
    74 (E : SyntacticAlgebra L)
    75 (D : WordCondition (Fintype.card (Carrier (Accepting L) 1))
    76 (Fintype.card (Carrier (Accepting L) 0)))
    77 {S : System A 0} (r : Labelling (Fintype.card (Carrier (Accepting L) 1))
    78 (Fintype.card (Carrier (Accepting L) 0)) S)
    79 (b : RegularBranch S) : FiniteSystem (Carrier (Accepting L)) 0 where
    80 size := b.size
    81 graph := {
    82 label := fun i => ⟨1, (Fintype.equivFin (Carrier (Accepting L) 1)).symm
    83 (r.edgeType (b.vertex i) (b.direction i))⟩
    84 initial := {b.start}
    85 root := ∅
    86 edge := fun v d t => d = 0 ∧ t = .inl (b.next v)
    87 direction_valid := by rintro v d t ⟨rfl, _⟩; exact Nat.zero_lt_one }
    88
    89axiom regularPath_morphism {A : RankedSet} (L : Algebras.Language A)
    90 [Fintype (Carrier (Accepting L) 1)] [Fintype (Carrier (Accepting L) 0)]
    91 (E : SyntacticAlgebra L)
    92 (D : WordCondition (Fintype.card (Carrier (Accepting L) 1))
    93 (Fintype.card (Carrier (Accepting L) 0)))
    94 {S : System A 0} (r : Labelling (Fintype.card (Carrier (Accepting L) 1))
    95 (Fintype.card (Carrier (Accepting L) 0)) S)
    96 (b : RegularBranch S) :
    97 Nonempty (FiniteMorphisms.Morphism (regularPath L E D r b) (RunPresentations.presentation L E D r))
    98
    99axiom regularPath_accepting {A : RankedSet} (L : Algebras.Language A)
    100 [Fintype (Carrier (Accepting L) 1)] [Fintype (Carrier (Accepting L) 0)]
    101 (E : SyntacticAlgebra L)
    102 (D : WordCondition (Fintype.card (Carrier (Accepting L) 1))
    103 (Fintype.card (Carrier (Accepting L) 0)))
    104 {S : System A 0} (r : Labelling (Fintype.card (Carrier (Accepting L) 1))
    105 (Fintype.card (Carrier (Accepting L) 0)) S)
    106 (hr : AcceptingClass (Accepting L) (E.algebra.eval 0
    107 (withLabels (ofSetSystem S.val) (runLabel L E D r))))
    108 (b : RegularBranch S) :
    109 AcceptingClass (Accepting L) (E.algebra.eval 0 (regularPath L E D r b))
    110
    111axiom path_evaluation {A : RankedSet} (L : Algebras.Language A)
    112 [Fintype (Carrier (Accepting L) 1)] [Fintype (Carrier (Accepting L) 0)]
    113 (E : SyntacticAlgebra L)
    114 (D : WordCondition (Fintype.card (Carrier (Accepting L) 1))
    115 (Fintype.card (Carrier (Accepting L) 0)))
    116 {S : System A 0} (r : Labelling (Fintype.card (Carrier (Accepting L) 1))
    117 (Fintype.card (Carrier (Accepting L) 0)) S)
    118 {k : ℕ} (b : FiniteBranch S k) :
    119 E.algebra.eval 0 (path L E D r b) = FiniteBranchWords.value E.algebra
    120 (List.ofFn (fun i => (Fintype.equivFin (Carrier (Accepting L) 1)).symm
    121 (r.edgeType (b.vertex i.castSucc) (b.direction i))))
    122 ((Fintype.equivFin (Carrier (Accepting L) 0)).symm
    123 (r.leafType (b.vertex (Fin.last k)) b.ends))
    124
    125end Lax369799.RunBranchObservations
    126
    Show ProofShow ProofShow ProofShow ProofShow Proof

    Discussion

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

    Loading discussion…