Documentation

Determinize.Proof.FiniteModel.Replay

Internal graph invariants for the executable machine. These are intermediate proof obligations; they do not establish the paper's Model.Matches contract.

Equations
Instances For
    def Determinize.Finite.Candidate.row (candidate : Candidate) (i : Fin candidate.states.size) :
    Equations
    Instances For
      def Determinize.Finite.Candidate.weight (candidate : Candidate) (i j : Fin candidate.states.size) :
      Equations
      Instances For

        Local replay checks the entire probability law, including successors with positive mass that are absent from the supplied graph.

        Equations
        • One or more equations did not get rendered due to their size.
        Instances For
          @[instance_reducible]
          instance Determinize.Finite.instDecidableRowReplays (candidate : Candidate) (i : Fin candidate.states.size) :
          Decidable (candidate.RowReplays i)
          Equations
          • One or more equations did not get rendered due to their size.
          Instances For
            @[instance_reducible]
            Equations
            • One or more equations did not get rendered due to their size.

            Sparse representation checks additionally reject out-of-range, duplicate, and nonpositive edges, even when they cancel in the induced matrix.

            Equations
            • One or more equations did not get rendered due to their size.
            Instances For
              Instances For
                @[instance_reducible]
                instance Determinize.Finite.instDecidableAligned (candidate : Candidate) (source : Spec.Paper.Core) (subject : Spec.FiniteModel.Subject) :
                Decidable (candidate.Aligned source subject)
                Equations
                • One or more equations did not get rendered due to their size.
                Instances For
                  @[instance_reducible]
                  instance Determinize.Finite.instDecidableReplayValid (candidate : Candidate) (source : Spec.Paper.Core) (subject : Spec.FiniteModel.Subject) :
                  Decidable (candidate.ReplayValid source subject)
                  Equations
                  • One or more equations did not get rendered due to their size.

                  Structural evidence shared by replay formats; state labels need not be distinct.

                  Instances For
                    @[reducible, inline]
                    Equations
                    • One or more equations did not get rendered due to their size.
                    Instances For
                      @[reducible, inline]
                      abbrev Determinize.Finite.Candidate.toModel (candidate : Candidate) {source : Spec.Paper.Core} {subject : Spec.FiniteModel.Subject} (valid : candidate.ReplayValid source subject) :

                      This constructs a finite rational model, but supplies no Matches proof.

                      Equations
                      • One or more equations did not get rendered due to their size.
                      Instances For
                        theorem Determinize.Finite.replay_successor_covered (candidate : Candidate) {source : Spec.Paper.Core} {subject : Spec.FiniteModel.Subject} (valid : candidate.ReplayValid source subject) (i : Fin candidate.states.size) (evidence : Evidence) (successors : List (ℚ × State)) (action : step (candidate.state i) = Except.ok (Step.next evidence successors)) (outcome : ℚ × State) (member : outcome ∈ successors) (positive : 0 < outcome.1) :
                        ∃ (j : Fin candidate.states.size), candidate.state j = outcome.2
                        theorem Determinize.Finite.replay_transition_weight (candidate : Candidate) {source : Spec.Paper.Core} {subject : Spec.FiniteModel.Subject} (valid : candidate.ReplayValid source subject) (i j : Fin candidate.states.size) (evidence : Evidence) (successors : List (ℚ × State)) (action : step (candidate.state i) = Except.ok (Step.next evidence successors)) :
                        (candidate.toModel valid).transition i j = (List.map (fun (outcome : ℚ × State) => if outcome.2 = candidate.state j then outcome.1 else 0) successors).sum

                        Reachability along positive-probability transitions of the executable machine.

                        Instances For
                          theorem Determinize.Finite.replay_initial (candidate : Candidate) {source : Spec.Paper.Core} {subject : Spec.FiniteModel.Subject} (valid : candidate.ReplayValid source subject) :
                          candidate.state (candidate.toModel valid).initial = initialState source subject
                          theorem Determinize.Finite.replay_reachable_covered (candidate : Candidate) {source : Spec.Paper.Core} {subject : Spec.FiniteModel.Subject} (valid : candidate.ReplayValid source subject) {state : State} (reachable : MachineReachable (initialState source subject) state) :
                          ∃ (i : Fin candidate.states.size), candidate.state i = state

                          Coverage holds for paths of arbitrary length, not just the explorer's horizon.

                          theorem Determinize.Finite.replay_no_failure (candidate : Candidate) {source : Spec.Paper.Core} {subject : Spec.FiniteModel.Subject} (valid : candidate.ReplayValid source subject) (i : Fin candidate.states.size) (failure : Failure) :
                          step (candidate.state i) ≠ Except.error failure
                          theorem Determinize.Finite.replay_reachable_no_failure (candidate : Candidate) {source : Spec.Paper.Core} {subject : Spec.FiniteModel.Subject} (valid : candidate.ReplayValid source subject) {state : State} (reachable : MachineReachable (initialState source subject) state) (failure : Failure) :
                          step state ≠ Except.error failure