Internal graph invariants for the executable machine. These are intermediate
proof obligations; they do not establish the paper's Model.Matches contract.
def
Determinize.Finite.Candidate.RowReplays
(candidate : Candidate)
(i : Fin candidate.states.size)
:
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]
instance
Determinize.Finite.instDecidableMatrixValid
(candidate : Candidate)
:
Decidable candidate.MatrixValid
Equations
- One or more equations did not get rendered due to their size.
def
Determinize.Finite.Candidate.EdgesValid
(candidate : Candidate)
(i : Fin candidate.states.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
@[instance_reducible]
instance
Determinize.Finite.instDecidableEdgesValid
(candidate : Candidate)
(i : Fin candidate.states.size)
:
Decidable (candidate.EdgesValid i)
Equations
- Determinize.Finite.instDecidableEdgesValid candidate i = Determinize.Finite.instDecidableEdgesValid._aux_1 candidate i
def
Determinize.Finite.initialState
(source : Spec.Paper.Core)
(subject : Spec.FiniteModel.Subject)
:
Equations
- Determinize.Finite.initialState source Determinize.Spec.FiniteModel.Subject.source = Determinize.Finite.State.eval source [] []
- Determinize.Finite.initialState source Determinize.Spec.FiniteModel.Subject.determinized = Determinize.Finite.State.eval (Determinize.Spec.Paper.Expr.determinize source) [] []
Instances For
structure
Determinize.Finite.Candidate.Aligned
(candidate : Candidate)
(source : Spec.Paper.Core)
(subject : Spec.FiniteModel.Subject)
:
- source_scoped : Proof.FiniteModel.Binding.Scoped 0 source
- injective : Function.Injective candidate.state
Instances For
@[instance_reducible]
instance
Determinize.Finite.instDecidableAligned
(candidate : Candidate)
(source : Spec.Paper.Core)
(subject : Spec.FiniteModel.Subject)
:
Equations
- One or more equations did not get rendered due to their size.
structure
Determinize.Finite.Candidate.ReplayValid
(candidate : Candidate)
(source : Spec.Paper.Core)
(subject : Spec.FiniteModel.Subject)
:
- aligned : candidate.Aligned source subject
- matrix : candidate.MatrixValid
- edges (i : Fin candidate.states.size) : candidate.EdgesValid i
- replays (i : Fin candidate.states.size) : candidate.RowReplays i
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.
- matrix : candidate.MatrixValid
- edges (i : Fin candidate.states.size) : candidate.EdgesValid i
Instances For
@[reducible, inline]
abbrev
Determinize.Finite.Candidate.graphModel
(candidate : Candidate)
(valid : candidate.GraphValid)
:
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)
:
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))
:
Reachability along positive-probability transitions of the executable machine.
- initial {initial : State} : MachineReachable initial initial
- next {initial before after : State} {probability : ℚ} {evidence : Evidence} {successors : List (ℚ × State)} : MachineReachable initial before → step before = Except.ok (Step.next evidence successors) → (probability, after) ∈ successors → 0 < probability → MachineReachable initial after
Instances For
theorem
Determinize.Finite.replay_initial
(candidate : Candidate)
{source : Spec.Paper.Core}
{subject : Spec.FiniteModel.Subject}
(valid : candidate.ReplayValid 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)
:
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)
:
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)
: