Initial source executions and wrapper memory images
ProvedDecrAlmostLinearSSSP.Decremental.Certificates.normal_laws_7Let a source program be a fixed finite deterministic scalar RAM program. Host states contain natural and real registers and memory; scaled instances, cached observations, advancing pointers and dirty queues are the objects defined by the wrapper interface.
Every source initialization is an actual terminating charged execution in its rounded polynomial-weight instance, under the supplied source maintenance hypothesis. The source-output normalization, reserve bound, maximum initial work and wrapper memory-image contracts hold simultaneously across scales. Cache and pointer images agree with the corresponding mathematical initialization state.
For every parameter tuple and state satisfying the explicit source-execution and representation hypotheses, all component contracts hold simultaneously:
Here the component assertions are the execution, exact memory-image, preservation, observation and charged-cost contracts described above, each with its own universal quantifiers. They are used to verify the arbitrary-weight scaling reduction for and .
Formalization Note The collection uses a balanced conjunction so its component contracts can be reused through short projections. It does not supply correctness or termination as a hypothesis on the external graph input.
import Definitions.Def_DecrAlmostLinearSSSP_RAMFoundation set_option autoImplicit false set_option maxRecDepth 10000 set_option maxHeartbeats 2000000 open scoped ENNReal NNReal attribute [local instance] Classical.propDecidable
theorem DecrAlmostLinearSSSP.Decremental.Certificates.normal_laws_7 : (((((((DecrAlmostLinearSSSP.Decremental.Native.ControlFrame DecrAlmostLinearSSSP.Decremental.TapeCopy.weightField) ∧ (DecrAlmostLinearSSSP.Decremental.Native.ControlFrame DecrAlmostLinearSSSP.Decremental.TapeCopy.code)) ∧ ((∀ (N : Nat),
DecrAlmostLinearSSSP.Decremental.Native.ControlFrame (DecrAlmostLinearSSSP.Decremental.Native.prepareBank N)) ∧ (∀ (N entry : Nat) (p : DecrAlmostLinearSSSP.Decremental.Program),
DecrAlmostLinearSSSP.Decremental.Native.ControlFrame (DecrAlmostLinearSSSP.Decremental.SourceCall.code N entry p)))) ∧ (((DecrAlmostLinearSSSP.Decremental.Native.ControlFrame DecrAlmostLinearSSSP.Decremental.CacheCopy.call) ∧ (∀ (p : DecrAlmostLinearSSSP.Decremental.Program),
DecrAlmostLinearSSSP.Decremental.Native.ControlFrame (DecrAlmostLinearSSSP.Decremental.Native.initializeScale p))) ∧ ((∀ (N : Nat) (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.Structured.Eval (DecrAlmostLinearSSSP.Decremental.Native.scaleStart N) s
(@OfNat.ofNat.{0} Nat (nat_lit 6) (instOfNatNat (nat_lit 6)))
(DecrAlmostLinearSSSP.Decremental.Native.scaleStartData N s)) ∧ ((∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.Structured.Eval DecrAlmostLinearSSSP.Decremental.Native.scaleAdvance s
(@OfNat.ofNat.{0} Nat (nat_lit 5) (instOfNatNat (nat_lit 5)))
(DecrAlmostLinearSSSP.Decremental.Native.advanceData s)) ∧ (∀ (N : Nat) (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
@Eq.{1} Nat (s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 56) (instOfNatNat (nat_lit 56))))
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) →
DecrAlmostLinearSSSP.Decremental.Native.BankEnv (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 84) (instOfNatNat (nat_lit 84))))
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 88) (instOfNatNat (nat_lit 88))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) N)
(@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))))
(DecrAlmostLinearSSSP.Decremental.Native.scaleStartData N s)))))) ∧ ((((∀ (i : DecrAlmostLinearSSSP.Decremental.Input) (j record cache stride B utility : Nat)
(s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.Native.BankEnv j record cache stride s →
DecrAlmostLinearSSSP.Decremental.Native.Globals i B utility s →
@Eq.{1} Nat (s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 100) (instOfNatNat (nat_lit 100))))
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) i.n) →
DecrAlmostLinearSSSP.Decremental.Native.BankEnv
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) j
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) record stride)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) cache
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) i.n))
stride (DecrAlmostLinearSSSP.Decremental.Native.advanceData s)) ∧ (∀ (N : Nat), DecrAlmostLinearSSSP.Decremental.Structured.NoMemory (DecrAlmostLinearSSSP.Decremental.Native.scaleStart N))) ∧ ((DecrAlmostLinearSSSP.Decremental.Structured.NoMemory DecrAlmostLinearSSSP.Decremental.Native.scaleAdvance) ∧ (∀ (N : Nat), DecrAlmostLinearSSSP.Decremental.Native.ControlFrame (DecrAlmostLinearSSSP.Decremental.Native.scaleStart N)))) ∧ (((DecrAlmostLinearSSSP.Decremental.Native.ControlFrame DecrAlmostLinearSSSP.Decremental.Native.scaleAdvance) ∧ (∀ (N : Nat), DecrAlmostLinearSSSP.Decremental.Native.GlobalFrame (DecrAlmostLinearSSSP.Decremental.Native.scaleStart N))) ∧ ((DecrAlmostLinearSSSP.Decremental.Native.GlobalFrame DecrAlmostLinearSSSP.Decremental.Native.scaleAdvance) ∧ ((∀ (N : Nat), DecrAlmostLinearSSSP.Decremental.TailFrame (DecrAlmostLinearSSSP.Decremental.Native.scaleStart N)) ∧ (DecrAlmostLinearSSSP.Decremental.TailFrame DecrAlmostLinearSSSP.Decremental.Native.scaleAdvance)))))) ∧ (((((∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {j cache : Nat} {b : Fin i.n → ENNReal}
{s t : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.Native.CacheImage i j cache b s →
(∀ (v : Fin i.n),
And
(@Eq.{1} Nat
(t.natMem
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) cache
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) (@Fin.val i.n v))))
(s.natMem
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) cache
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) (@Fin.val i.n v)))))
(@Eq.{1} Real
(t.realMem
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) cache
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) (@Fin.val i.n v))))
(s.realMem
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) cache
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) (@Fin.val i.n v)))))) →
DecrAlmostLinearSSSP.Decremental.Native.CacheImage i j cache b t) ∧ (∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {j cache : Nat} {s : DecrAlmostLinearSSSP.Decremental.Structured.Data}
{g : DecrAlmostLinearSSSP.Decremental.Machine},
i.Valid →
(∀ (v : Fin i.n),
And
(@Eq.{1} Nat
(s.natMem
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) cache
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) (@Fin.val i.n v))))
(g.natMem (@Fin.val i.n v)))
(And
(@Eq.{1} Real
(s.realMem
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) cache
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) (@Fin.val i.n v))))
(@HMul.hMul.{0, 0, 0} Real Real Real (@instHMul.{0} Real Real.instMul)
(DecrAlmostLinearSSSP.Decremental.delta i j) (g.realMem (@Fin.val i.n v))))
(@Eq.{1} ENNReal
(DecrAlmostLinearSSSP.Decremental.ExtendedMax.cell s
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) cache
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) (@Fin.val i.n v))))
(@HMul.hMul.{0, 0, 0} ENNReal ENNReal ENNReal
(@instHMul.{0} ENNReal
(@Distrib.toMul.{0} ENNReal
(@instDistribOfSemiring.{0} ENNReal
(@CommSemiring.toSemiring.{0} ENNReal ENNReal.instCommSemiring))))
(ENNReal.ofReal (DecrAlmostLinearSSSP.Decremental.delta i j))
(DecrAlmostLinearSSSP.Decremental.stored g (@Fin.val i.n v)))))) →
(∀ (v : Fin i.n),
And
(@LE.le.{0} Nat instLENat (g.natMem (@Fin.val i.n v))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@Eq.{1} Nat (g.natMem (@Fin.val i.n v)) (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) →
@LE.le.{0} Real Real.instLE (@OfNat.ofNat.{0} Real (nat_lit 0) (@Zero.toOfNat0.{0} Real Real.instZero))
(g.realMem (@Fin.val i.n v)))) →
DecrAlmostLinearSSSP.Decremental.Native.CacheImage i j cache
(fun v => DecrAlmostLinearSSSP.Decremental.stored g (@Fin.val i.n v)) s)) ∧ ((∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {p : DecrAlmostLinearSSSP.Decremental.Program}
{B j record cache next : Nat} {g : DecrAlmostLinearSSSP.Decremental.Machine} {b : Fin i.n → ENNReal}
{s t : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.Native.ScaleMemory i p B j record cache next g b s →
(∀ (r : Nat),
@LT.lt.{0} Nat instLTNat r
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.registerBound p.code)
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4)))) →
And
(@Eq.{1} Nat
(t.natMem
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) record
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) r)))
(s.natMem
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) record
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) r))))
(@Eq.{1} Real
(t.realMem
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) record
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) r)))
(s.realMem
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) record
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) r))))) →
(∀ (v : Nat),
And
(@Eq.{1} Nat (t.natMem (DecrAlmostLinearSSSP.Decremental.bankAddress B j v))
(s.natMem (DecrAlmostLinearSSSP.Decremental.bankAddress B j v)))
(@Eq.{1} Real (t.realMem (DecrAlmostLinearSSSP.Decremental.bankAddress B j v))
(s.realMem (DecrAlmostLinearSSSP.Decremental.bankAddress B j v)))) →
(∀ (v : Fin i.n),
And
(@Eq.{1} Nat
(t.natMem
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) cache
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) (@Fin.val i.n v))))
(s.natMem
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) cache
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) (@Fin.val i.n v)))))
(@Eq.{1} Real
(t.realMem
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) cache
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) (@Fin.val i.n v))))
(s.realMem
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) cache
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) (@Fin.val i.n v)))))) →
DecrAlmostLinearSSSP.Decremental.Native.ScaleMemory i p B j record cache next g b t) ∧ (∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {p : DecrAlmostLinearSSSP.Decremental.Program}
{B j record cache next : Nat} {g : DecrAlmostLinearSSSP.Decremental.Machine} {b : Fin i.n → ENNReal}
{s t : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.Native.ScaleMemory i p B j record cache next g b s →
@Eq.{1} (Nat → Nat) t.natMem s.natMem →
@Eq.{1} (Nat → Real) t.realMem s.realMem →
DecrAlmostLinearSSSP.Decremental.Native.ScaleMemory i p B j record cache next g b t))) ∧ (((∀ (base stride j : Nat),
@Eq.{1} Nat
(DecrAlmostLinearSSSP.Decremental.Native.recordAt base stride
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) j
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Native.recordAt base stride j) stride)) ∧ (∀ (base n j : Nat),
@Eq.{1} Nat
(DecrAlmostLinearSSSP.Decremental.Native.cacheAt base n
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) j
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Native.cacheAt base n j)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) n)))) ∧ ((∀ (B n S reserve stride j offset : Nat),
@LT.lt.{0} Nat instLTNat j S →
@LT.lt.{0} Nat instLTNat offset stride →
@LT.lt.{0} Nat instLTNat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Layout.addresses B n S reserve stride).records
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) stride j))
offset)
(DecrAlmostLinearSSSP.Decremental.Layout.addresses B n S reserve stride).caches) ∧ ((∀ (B n S reserve stride j v : Nat),
@LT.lt.{0} Nat instLTNat j S →
@LT.lt.{0} Nat instLTNat v n →
@LT.lt.{0} Nat instLTNat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Layout.addresses B n S reserve stride).caches
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) n j) v)))
(DecrAlmostLinearSSSP.Decremental.Layout.addresses B n S reserve stride).reports) ∧ (∀ (B n S reserve stride v : Nat),
@LT.lt.{0} Nat instLTNat v n →
@LT.lt.{0} Nat instLTNat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Layout.addresses B n S reserve stride).pointers
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) v))
(DecrAlmostLinearSSSP.Decremental.Layout.addresses B n S reserve stride).dirtyFlags))))) ∧ ((((∀ (B n S reserve stride v : Nat),
@LT.lt.{0} Nat instLTNat v n →
@LT.lt.{0} Nat instLTNat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Layout.addresses B n S reserve stride).dirtyFlags
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) v))
(DecrAlmostLinearSSSP.Decremental.Layout.addresses B n S reserve stride).dirtyList) ∧ (∀ (B n S reserve stride v : Nat),
@LT.lt.{0} Nat instLTNat v n →
@LT.lt.{0} Nat instLTNat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Layout.addresses B n S reserve stride).dirtyList
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) v))
(DecrAlmostLinearSSSP.Decremental.Layout.addresses B n S reserve stride).records)) ∧ ((∀ (B n S reserve stride j offset : Nat),
@Even.{0} Nat instAddNat stride →
@Even.{0} Nat instAddNat offset →
∃ a,
@Eq.{1} Nat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Layout.addresses B n S reserve stride).records
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) stride j))
offset)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) B
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) a))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))) ∧ ((∀ (B n S reserve stride j v : Nat),
@Even.{0} Nat instAddNat stride →
∃ a,
@Eq.{1} Nat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Layout.addresses B n S reserve stride).caches
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) n j) v)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) B
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) a))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))) ∧ (∀ (B n S reserve stride : Nat),
@Even.{0} Nat instAddNat stride →
∃ a,
@Eq.{1} Nat (DecrAlmostLinearSSSP.Decremental.Layout.addresses B n S reserve stride).reports
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) B
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) a))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))))) ∧ (((∀ (B n S reserve stride : Nat),
@Even.{0} Nat instAddNat stride →
∃ a,
@Eq.{1} Nat (DecrAlmostLinearSSSP.Decremental.Layout.addresses B n S reserve stride).utility
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) B
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) a))) ∧ (∀ (B n S reserve stride j : Nat),
@LE.le.{0} Nat instLENat j reserve →
@LT.lt.{0} Nat instLTNat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Layout.addresses B n S reserve stride).reports
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) j))
(DecrAlmostLinearSSSP.Decremental.Layout.addresses B n S reserve stride).utility)) ∧ ((∀ (N : Nat),
@Even.{0} Nat instAddNat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) N)
(@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))))) ∧ ((∀ (N j : Nat),
@LT.lt.{0} Nat instLTNat j N →
@LT.lt.{0} Nat instLTNat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8)))
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) j))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) N)
(@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))))) ∧ (∀ (B n S reserve N j r : Nat),
∃ a,
@Eq.{1} Nat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Native.recordAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B n S reserve N).records
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) N)
(@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))))
j)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) r))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) B
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) a))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))))))))) ∧ ((((((∀ (B n S reserve N j v : Nat),
∃ a,
@Eq.{1} Nat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Native.cacheAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B n S reserve N).caches n j)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) v))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) B
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) a))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))) ∧ (∀ (B n S reserve N j r : Nat),
@LT.lt.{0} Nat instLTNat j S →
@LT.lt.{0} Nat instLTNat r
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) N
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4)))) →
@LT.lt.{0} Nat instLTNat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Native.recordAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B n S reserve N).records
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) N)
(@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))))
j)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) r))
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B n S reserve N).caches)) ∧ ((∀ (B n S reserve N j r : Nat),
@LT.lt.{0} Nat instLTNat j S →
@LT.lt.{0} Nat instLTNat r
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) N
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4)))) →
@LT.lt.{0} Nat instLTNat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Native.recordAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B n S reserve N).records
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) N)
(@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))))
j)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) r))
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B n S reserve N).utility) ∧ (∀ (B n S reserve N j v : Nat),
@LT.lt.{0} Nat instLTNat j S →
@LT.lt.{0} Nat instLTNat v n →
@LT.lt.{0} Nat instLTNat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Native.cacheAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B n S reserve N).caches n j)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) v))
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B n S reserve N).utility))) ∧ (((∀ {B n S reserve N j k r t : Nat},
@LT.lt.{0} Nat instLTNat r
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) N
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4)))) →
@LT.lt.{0} Nat instLTNat t
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) N
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4)))) →
@Eq.{1} Nat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Native.recordAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B n S reserve N).records
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) N)
(@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))))
j)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) r))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Native.recordAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B n S reserve N).records
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) N)
(@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))))
k)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) t)) →
@Eq.{1} Nat j k) ∧ (∀ {B n S reserve N j k v w : Nat},
@LT.lt.{0} Nat instLTNat v n →
@LT.lt.{0} Nat instLTNat w n →
@Eq.{1} Nat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Native.cacheAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B n S reserve N).caches n j)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) v))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Native.cacheAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B n S reserve N).caches n k)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) w)) →
@Eq.{1} Nat j k)) ∧ ((∀ (i : DecrAlmostLinearSSSP.Decremental.Input),
i.Valid →
∀ (p : DecrAlmostLinearSSSP.Decremental.Program) (coefficient N : Nat),
@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))) N →
∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.InputCapture.RawInput i s →
@Eq.{1} (Nat → Nat) s.natMem (DecrAlmostLinearSSSP.Decremental.initialMachine p i).natMem →
(@Eq.{1} (Nat → Real) s.realMem fun x =>
@OfNat.ofNat.{0} Real (nat_lit 0) (@Zero.toOfNat0.{0} Real Real.instZero)) →
(∀ (r : Nat),
@LE.le.{0} Nat instLENat N r →
And
(@Eq.{1} Nat (s.natReg (DecrAlmostLinearSSSP.Decremental.shadowReg r))
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(@Eq.{1} Real (s.realReg (DecrAlmostLinearSSSP.Decremental.shadowReg r))
(@OfNat.ofNat.{0} Real (nat_lit 0) (@Zero.toOfNat0.{0} Real Real.instZero)))) →
∃ cost t,
And
(DecrAlmostLinearSSSP.Decremental.Structured.Eval
(DecrAlmostLinearSSSP.Decremental.Native.normalSetup coefficient N) s cost t)
(And
(@LE.le.{0} Nat instLENat cost
(DecrAlmostLinearSSSP.Decremental.Native.setupCost i coefficient N))
(And
(DecrAlmostLinearSSSP.Decremental.Native.Globals i
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) i.n
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3))) i.k))
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) i.n
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3))) i.k))
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
i.n (DecrAlmostLinearSSSP.Decremental.scaleCount i)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) coefficient
(@HPow.hPow.{0, 0, 0} Nat Nat Nat
(@instHPow.{0, 0} Nat Nat
(@NPow.toPow.{0} Nat (@Monoid.toNPow.{0} Nat Nat.instMonoid)))
i.size (@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
N).utility
t)
(And
(DecrAlmostLinearSSSP.Decremental.Layout.Represents t
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) i.n
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3))) i.k))
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
i.n (DecrAlmostLinearSSSP.Decremental.scaleCount i)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) coefficient
(@HPow.hPow.{0, 0, 0} Nat Nat Nat
(@instHPow.{0, 0} Nat Nat
(@NPow.toPow.{0} Nat (@Monoid.toNPow.{0} Nat Nat.instMonoid)))
i.size (@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
N))
(And
(@Eq.{1} Nat (t.natReg (@OfNat.ofNat.{0} Nat (nat_lit 60) (instOfNatNat (nat_lit 60))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) coefficient
(@HPow.hPow.{0, 0, 0} Nat Nat Nat
(@instHPow.{0, 0} Nat Nat
(@NPow.toPow.{0} Nat (@Monoid.toNPow.{0} Nat Nat.instMonoid)))
i.size (@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@Eq.{1} Nat (t.natReg (@OfNat.ofNat.{0} Nat (nat_lit 80) (instOfNatNat (nat_lit 80))))
(DecrAlmostLinearSSSP.Decremental.scaleCount i))
(And
(@Eq.{1} Nat
(t.natReg (@OfNat.ofNat.{0} Nat (nat_lit 100) (instOfNatNat (nat_lit 100))))
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) i.n))
(And
(∀ (q : Fin (DecrAlmostLinearSSSP.Decremental.scaleCount i)),
DecrAlmostLinearSSSP.Decremental.SourceMemory.Image
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) i.n
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3))) i.k))
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
(@Fin.val (DecrAlmostLinearSSSP.Decremental.scaleCount i) q) t
(fun x => @OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) fun x =>
@OfNat.ofNat.{0} Real (nat_lit 0) (@Zero.toOfNat0.{0} Real Real.instZero))
(And
(∀ (address : Nat),
@LE.le.{0} Nat instLENat address
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) i.n
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3))) i.k))
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))) →
@Eq.{1} Nat (t.natMem address)
((DecrAlmostLinearSSSP.Decremental.initialMachine p i).natMem address))
(∀ (r : Nat),
@LE.le.{0} Nat instLENat N r →
And
(@Eq.{1} Nat (t.natReg (DecrAlmostLinearSSSP.Decremental.shadowReg r))
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(@Eq.{1} Real (t.realReg (DecrAlmostLinearSSSP.Decremental.shadowReg r))
(@OfNat.ofNat.{0} Real (nat_lit 0)
(@Zero.toOfNat0.{0} Real Real.instZero))))))))))))) ∧ ((∀ {B n S reserve N j k address : Nat},
@LT.lt.{0} Nat instLTNat j S →
@LT.lt.{0} Nat instLTNat k S →
@Ne.{1} Nat j k →
DecrAlmostLinearSSSP.Decremental.Native.ScaleCell B n S reserve N j address →
Not (DecrAlmostLinearSSSP.Decremental.Native.ScaleCell B n S reserve N k address)) ∧ (∀ {B n S reserve N j address : Nat},
@LT.lt.{0} Nat instLTNat j S →
DecrAlmostLinearSSSP.Decremental.Native.ScaleCell B n S reserve N j address →
∀ (a : Nat),
@Ne.{1} Nat address
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B n S reserve N).utility
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) a))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))))))) ∧ ((((∀ {B n S reserve N j : Nat} {s t : DecrAlmostLinearSSSP.Decremental.Structured.Data},
(∀ (address : Nat),
(∀ (r : Nat),
@LT.lt.{0} Nat instLTNat r
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) N
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4)))) →
@Ne.{1} Nat address
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Native.recordAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B n S reserve N).records
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) N)
(@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))))
j)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) r))) →
(∀ (v : Nat), @Ne.{1} Nat address (DecrAlmostLinearSSSP.Decremental.bankAddress B j v)) →
(∀ (v : Nat),
@LT.lt.{0} Nat instLTNat v n →
@Ne.{1} Nat address
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Native.cacheAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B n S reserve N).caches n j)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) v))) →
(∀ (v : Nat),
@Ne.{1} Nat address
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B n S reserve N).utility
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) v))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))) →
And (@Eq.{1} Nat (t.natMem address) (s.natMem address))
(@Eq.{1} Real (t.realMem address) (s.realMem address))) →
DecrAlmostLinearSSSP.Decremental.Native.FootprintFrame B n S reserve N j s t) ∧ (∀ {B n S reserve N j k address : Nat} {s t : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.Native.FootprintFrame B n S reserve N j s t →
@LT.lt.{0} Nat instLTNat j S →
@LT.lt.{0} Nat instLTNat k S →
@Ne.{1} Nat j k →
DecrAlmostLinearSSSP.Decremental.Native.ScaleCell B n S reserve N k address →
And (@Eq.{1} Nat (t.natMem address) (s.natMem address))
(@Eq.{1} Real (t.realMem address) (s.realMem address)))) ∧ ((∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {p : DecrAlmostLinearSSSP.Decremental.Program} {B S reserve j k : Nat}
{s t : DecrAlmostLinearSSSP.Decremental.Structured.Data} {g : DecrAlmostLinearSSSP.Decremental.Machine}
{b : Fin i.n → ENNReal},
DecrAlmostLinearSSSP.Decremental.Native.FootprintFrame B i.n S reserve
(DecrAlmostLinearSSSP.Decremental.registerBound p.code) j s t →
@LT.lt.{0} Nat instLTNat j S →
@LT.lt.{0} Nat instLTNat k S →
@Ne.{1} Nat j k →
DecrAlmostLinearSSSP.Decremental.Native.ScaleMemory i p B k
(DecrAlmostLinearSSSP.Decremental.Native.recordAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B i.n S reserve
(DecrAlmostLinearSSSP.Decremental.registerBound p.code)).records
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(DecrAlmostLinearSSSP.Decremental.registerBound p.code))
(@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))))
k)
(DecrAlmostLinearSSSP.Decremental.Native.cacheAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B i.n S reserve
(DecrAlmostLinearSSSP.Decremental.registerBound p.code)).caches
i.n k)
(DecrAlmostLinearSSSP.Decremental.Native.recordAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B i.n S reserve
(DecrAlmostLinearSSSP.Decremental.registerBound p.code)).records
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(DecrAlmostLinearSSSP.Decremental.registerBound p.code))
(@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) k
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
g b s →
DecrAlmostLinearSSSP.Decremental.Native.ScaleMemory i p B k
(DecrAlmostLinearSSSP.Decremental.Native.recordAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B i.n S reserve
(DecrAlmostLinearSSSP.Decremental.registerBound p.code)).records
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(DecrAlmostLinearSSSP.Decremental.registerBound p.code))
(@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))))
k)
(DecrAlmostLinearSSSP.Decremental.Native.cacheAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B i.n S reserve
(DecrAlmostLinearSSSP.Decremental.registerBound p.code)).caches
i.n k)
(DecrAlmostLinearSSSP.Decremental.Native.recordAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B i.n S reserve
(DecrAlmostLinearSSSP.Decremental.registerBound p.code)).records
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(DecrAlmostLinearSSSP.Decremental.registerBound p.code))
(@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) k
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
g b t) ∧ ((∀ {B n S reserve N j k : Nat} {s t : DecrAlmostLinearSSSP.Decremental.Structured.Data} {natural : Nat → Nat}
{real : Nat → Real},
DecrAlmostLinearSSSP.Decremental.Native.FootprintFrame B n S reserve N j s t →
@LT.lt.{0} Nat instLTNat j S →
@LT.lt.{0} Nat instLTNat k S →
@Ne.{1} Nat j k →
DecrAlmostLinearSSSP.Decremental.SourceMemory.Image B k s natural real →
DecrAlmostLinearSSSP.Decremental.SourceMemory.Image B k t natural real) ∧ (∀ {B n S reserve N j address : Nat},
DecrAlmostLinearSSSP.Decremental.Native.ScaleCell B n S reserve N j address → @LT.lt.{0} Nat instLTNat B address)))) ∧ (((∀ {B n S reserve N j : Nat} {s t : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.Native.FootprintFrame B n S reserve N j s t →
∀ (address : Nat),
@LE.le.{0} Nat instLENat address B →
And (@Eq.{1} Nat (t.natMem address) (s.natMem address)) (@Eq.{1} Real (t.realMem address) (s.realMem address))) ∧ (∀ (i : DecrAlmostLinearSSSP.Decremental.Input),
i.Valid →
∀ (p : DecrAlmostLinearSSSP.Decremental.Program) (C : Real) (a : Nat → Real) (queryBound : Nat),
@LT.lt.{0} Real Real.instLT
(@HDiv.hDiv.{0, 0, 0} Real Real Real (@instHDiv.{0} Real (@DivInvMonoid.toDiv.{0} Real Real.instDivInvMonoid))
(@OfNat.ofNat.{0} Real (nat_lit 1) (@One.toOfNat1.{0} Real Real.instOne))
(@Nat.cast.{0} Real Real.instNatCast i.size))
i.accuracy →
∀ (j B reserve S : Nat),
@LT.lt.{0} Nat instLTNat j S →
∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.Maintains p C a queryBound Bool.false
(DecrAlmostLinearSSSP.Decremental.barrierInput i j) →
DecrAlmostLinearSSSP.Decremental.Native.Globals i B
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B i.n S reserve
(DecrAlmostLinearSSSP.Decremental.registerBound p.code)).utility
s →
DecrAlmostLinearSSSP.Decremental.Native.BankEnv j
(DecrAlmostLinearSSSP.Decremental.Native.recordAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B i.n S reserve
(DecrAlmostLinearSSSP.Decremental.registerBound p.code)).records
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(DecrAlmostLinearSSSP.Decremental.registerBound p.code))
(@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))))
j)
(DecrAlmostLinearSSSP.Decremental.Native.cacheAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B i.n S reserve
(DecrAlmostLinearSSSP.Decremental.registerBound p.code)).caches
i.n j)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(DecrAlmostLinearSSSP.Decremental.registerBound p.code))
(@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))))
s →
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) i.n
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3))) i.k))
B →
(DecrAlmostLinearSSSP.Decremental.SourceMemory.Image B j s
(fun x => @OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) fun x =>
@OfNat.ofNat.{0} Real (nat_lit 0) (@Zero.toOfNat0.{0} Real Real.instZero)) →
(∀ (address : Nat),
@LE.le.{0} Nat instLENat address B →
@Eq.{1} Nat (s.natMem address)
((DecrAlmostLinearSSSP.Decremental.initialMachine p i).natMem address)) →
(∀ (r : Nat),
@LE.le.{0} Nat instLENat (DecrAlmostLinearSSSP.Decremental.registerBound p.code) r →
And
(@Eq.{1} Nat (s.natReg (DecrAlmostLinearSSSP.Decremental.shadowReg r))
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(@Eq.{1} Real (s.realReg (DecrAlmostLinearSSSP.Decremental.shadowReg r))
(@OfNat.ofNat.{0} Real (nat_lit 0) (@Zero.toOfNat0.{0} Real Real.instZero)))) →
∃ final cost t,
And
(DecrAlmostLinearSSSP.Decremental.Ends p
(DecrAlmostLinearSSSP.Decremental.initialMachine p
(DecrAlmostLinearSSSP.Decremental.barrierInput i j))
final)
(And
(DecrAlmostLinearSSSP.Decremental.Structured.Eval
(DecrAlmostLinearSSSP.Decremental.Native.initializeScale p) s cost t)
(And
(@LE.le.{0} Nat instLENat cost
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.dispatchCharge p.code)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
final.work)
(DecrAlmostLinearSSSP.Decremental.Native.initOverhead i p)))
(And
(DecrAlmostLinearSSSP.Decremental.Native.Globals i B
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B i.n S reserve
(DecrAlmostLinearSSSP.Decremental.registerBound p.code)).utility
t)
(And
(DecrAlmostLinearSSSP.Decremental.Native.BankEnv j
(DecrAlmostLinearSSSP.Decremental.Native.recordAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B i.n S reserve
(DecrAlmostLinearSSSP.Decremental.registerBound p.code)).records
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(DecrAlmostLinearSSSP.Decremental.registerBound p.code))
(@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))))
j)
(DecrAlmostLinearSSSP.Decremental.Native.cacheAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B i.n S reserve
(DecrAlmostLinearSSSP.Decremental.registerBound p.code)).caches
i.n j)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(DecrAlmostLinearSSSP.Decremental.registerBound p.code))
(@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))))
t)
(And
(DecrAlmostLinearSSSP.Decremental.Native.ScaleMemory i p B j
(DecrAlmostLinearSSSP.Decremental.Native.recordAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B i.n S reserve
(DecrAlmostLinearSSSP.Decremental.registerBound p.code)).records
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(DecrAlmostLinearSSSP.Decremental.registerBound p.code))
(@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))))
j)
(DecrAlmostLinearSSSP.Decremental.Native.cacheAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B i.n S reserve
(DecrAlmostLinearSSSP.Decremental.registerBound p.code)).caches
i.n j)
(DecrAlmostLinearSSSP.Decremental.Native.recordAt
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B i.n S reserve
(DecrAlmostLinearSSSP.Decremental.registerBound p.code)).records
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(DecrAlmostLinearSSSP.Decremental.registerBound p.code))
(@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) j
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
final
(fun v => DecrAlmostLinearSSSP.Decremental.stored final (@Fin.val i.n v)) t)
(And
(∀ (r : Nat),
@LE.le.{0} Nat instLENat
(DecrAlmostLinearSSSP.Decremental.registerBound p.code) r →
And
(@Eq.{1} Nat (t.natReg (DecrAlmostLinearSSSP.Decremental.shadowReg r))
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(@Eq.{1} Real
(t.realReg (DecrAlmostLinearSSSP.Decremental.shadowReg r))
(@OfNat.ofNat.{0} Real (nat_lit 0)
(@Zero.toOfNat0.{0} Real Real.instZero))))
(And
(∀ (address : Nat),
@LE.le.{0} Nat instLENat address B →
@Eq.{1} Nat (t.natMem address)
((DecrAlmostLinearSSSP.Decremental.initialMachine p i).natMem
address))
(DecrAlmostLinearSSSP.Decremental.Native.FootprintFrame B i.n S reserve
(DecrAlmostLinearSSSP.Decremental.registerBound p.code) j s t)))))))))) ∧ ((∀ (p : DecrAlmostLinearSSSP.Decremental.Program) (C : Real) (a : Nat → Real) (queryBound : Nat),
(∀ (i : DecrAlmostLinearSSSP.Decremental.Input),
i.Valid →
@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) i.n →
@LE.le.{0} Nat instLENat i.W
(@HPow.hPow.{0, 0, 0} Nat Nat Nat
(@instHPow.{0, 0} Nat Nat (@NPow.toPow.{0} Nat (@Monoid.toNPow.{0} Nat Nat.instMonoid))) i.size
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))) →
@LT.lt.{0} Real Real.instLT
(@HDiv.hDiv.{0, 0, 0} Real Real Real
(@instHDiv.{0} Real (@DivInvMonoid.toDiv.{0} Real Real.instDivInvMonoid))
(@OfNat.ofNat.{0} Real (nat_lit 1) (@One.toOfNat1.{0} Real Real.instOne))
(@Nat.cast.{0} Real Real.instNatCast i.size))
i.accuracy →
@LT.lt.{0} Real Real.instLT i.accuracy
(@OfNat.ofNat.{0} Real (nat_lit 1) (@One.toOfNat1.{0} Real Real.instOne)) →
DecrAlmostLinearSSSP.Decremental.Maintains p C a queryBound Bool.false i) →
∀ (i : DecrAlmostLinearSSSP.Decremental.Input),
i.Valid →
@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) i.n →
@LT.lt.{0} Real Real.instLT
(@HDiv.hDiv.{0, 0, 0} Real Real Real
(@instHDiv.{0} Real (@DivInvMonoid.toDiv.{0} Real Real.instDivInvMonoid))
(@OfNat.ofNat.{0} Real (nat_lit 1) (@One.toOfNat1.{0} Real Real.instOne))
(@Nat.cast.{0} Real Real.instNatCast i.size))
i.accuracy →
∀ (j : Nat),
DecrAlmostLinearSSSP.Decremental.Maintains p C a queryBound Bool.false
(DecrAlmostLinearSSSP.Decremental.barrierInput i j)) ∧ ((∀ (p : DecrAlmostLinearSSSP.Decremental.Program) (C : Real) (a : Nat → Real) (queryBound : Nat)
(i : DecrAlmostLinearSSSP.Decremental.Input) (j : Nat),
DecrAlmostLinearSSSP.Decremental.Maintains p C a queryBound Bool.false
(DecrAlmostLinearSSSP.Decremental.barrierInput i j) →
∃ g, DecrAlmostLinearSSSP.Decremental.Native.InitialFacts p C a i j g) ∧ (∀ (p : DecrAlmostLinearSSSP.Decremental.Program) (C : Real) (a : Nat → Real) (queryBound : Nat),
(∀ (i : DecrAlmostLinearSSSP.Decremental.Input),
i.Valid →
@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) i.n →
@LE.le.{0} Nat instLENat i.W
(@HPow.hPow.{0, 0, 0} Nat Nat Nat
(@instHPow.{0, 0} Nat Nat (@NPow.toPow.{0} Nat (@Monoid.toNPow.{0} Nat Nat.instMonoid))) i.size
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))) →
@LT.lt.{0} Real Real.instLT
(@HDiv.hDiv.{0, 0, 0} Real Real Real
(@instHDiv.{0} Real (@DivInvMonoid.toDiv.{0} Real Real.instDivInvMonoid))
(@OfNat.ofNat.{0} Real (nat_lit 1) (@One.toOfNat1.{0} Real Real.instOne))
(@Nat.cast.{0} Real Real.instNatCast i.size))
i.accuracy →
@LT.lt.{0} Real Real.instLT i.accuracy
(@OfNat.ofNat.{0} Real (nat_lit 1) (@One.toOfNat1.{0} Real Real.instOne)) →
DecrAlmostLinearSSSP.Decremental.Maintains p C a queryBound Bool.false i) →
∀ (i : DecrAlmostLinearSSSP.Decremental.Input),
i.Valid →
@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) i.n →
@LT.lt.{0} Real Real.instLT
(@HDiv.hDiv.{0, 0, 0} Real Real Real
(@instHDiv.{0} Real (@DivInvMonoid.toDiv.{0} Real Real.instDivInvMonoid))
(@OfNat.ofNat.{0} Real (nat_lit 1) (@One.toOfNat1.{0} Real Real.instOne))
(@Nat.cast.{0} Real Real.instNatCast i.size))
i.accuracy →
∃ (f : Fin (DecrAlmostLinearSSSP.Decremental.scaleCount i) → DecrAlmostLinearSSSP.Decremental.Machine),
∀ (j : Fin (DecrAlmostLinearSSSP.Decremental.scaleCount i)),
DecrAlmostLinearSSSP.Decremental.Native.InitialFacts p C a i
(@Fin.val (DecrAlmostLinearSSSP.Decremental.scaleCount i) j) (f j))))))) ∧ (((((∀ {i : DecrAlmostLinearSSSP.Decremental.Input}
(f : Fin (DecrAlmostLinearSSSP.Decremental.scaleCount i) → DecrAlmostLinearSSSP.Decremental.Machine)
(j : Fin (DecrAlmostLinearSSSP.Decremental.scaleCount i)),
@LE.le.{0} Nat instLENat (f j).work (@DecrAlmostLinearSSSP.Decremental.Native.maxInitialWork i f)) ∧ (∀ {p : DecrAlmostLinearSSSP.Decremental.Program} {C : Real} {a : Nat → Real}
{i : DecrAlmostLinearSSSP.Decremental.Input}
(f : Fin (DecrAlmostLinearSSSP.Decremental.scaleCount i) → DecrAlmostLinearSSSP.Decremental.Machine),
(∀ (j : Fin (DecrAlmostLinearSSSP.Decremental.scaleCount i)),
DecrAlmostLinearSSSP.Decremental.Native.InitialFacts p C a i
(@Fin.val (DecrAlmostLinearSSSP.Decremental.scaleCount i) j) (f j)) →
@LE.le.{0} Real Real.instLE (@OfNat.ofNat.{0} Real (nat_lit 0) (@Zero.toOfNat0.{0} Real Real.instZero))
(@HDiv.hDiv.{0, 0, 0} Real Real Real (@instHDiv.{0} Real (@DivInvMonoid.toDiv.{0} Real Real.instDivInvMonoid))
(@HMul.hMul.{0, 0, 0} Real Real Real (@instHMul.{0} Real Real.instMul)
(@HMul.hMul.{0, 0, 0} Real Real Real (@instHMul.{0} Real Real.instMul) C
(@HMul.hMul.{0, 0, 0} Real Real Real (@instHMul.{0} Real Real.instMul)
(@OfNat.ofNat.{0} Real (nat_lit 64)
(@instOfNatAtLeastTwo.{0} Real (nat_lit 64) Real.instNatCast
(@Nat.instAtLeastTwoHAddOfNat (@OfNat.ofNat.{0} Nat (nat_lit 63) (instOfNatNat (nat_lit 63)))
(@Nat.instNeZeroSucc (@OfNat.ofNat.{0} Nat (nat_lit 62) (instOfNatNat (nat_lit 62)))))))
(@Nat.cast.{0} Real Real.instNatCast i.size)))
(a
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 64) (instOfNatNat (nat_lit 64))) i.size)))
(@HDiv.hDiv.{0, 0, 0} Real Real Real (@instHDiv.{0} Real (@DivInvMonoid.toDiv.{0} Real Real.instDivInvMonoid))
i.accuracy
(@OfNat.ofNat.{0} Real (nat_lit 16)
(@instOfNatAtLeastTwo.{0} Real (nat_lit 16) Real.instNatCast
(@Nat.instAtLeastTwoHAddOfNat (@OfNat.ofNat.{0} Nat (nat_lit 15) (instOfNatNat (nat_lit 15)))
(@Nat.instNeZeroSucc (@OfNat.ofNat.{0} Nat (nat_lit 14) (instOfNatNat (nat_lit 14))))))))) →
@LE.le.{0} Real Real.instLE
(@Nat.cast.{0} Real Real.instNatCast (@DecrAlmostLinearSSSP.Decremental.Native.maxInitialWork i f))
(@HDiv.hDiv.{0, 0, 0} Real Real Real (@instHDiv.{0} Real (@DivInvMonoid.toDiv.{0} Real Real.instDivInvMonoid))
(@HMul.hMul.{0, 0, 0} Real Real Real (@instHMul.{0} Real Real.instMul)
(@HMul.hMul.{0, 0, 0} Real Real Real (@instHMul.{0} Real Real.instMul) C
(@HMul.hMul.{0, 0, 0} Real Real Real (@instHMul.{0} Real Real.instMul)
(@OfNat.ofNat.{0} Real (nat_lit 64)
(@instOfNatAtLeastTwo.{0} Real (nat_lit 64) Real.instNatCast
(@Nat.instAtLeastTwoHAddOfNat (@OfNat.ofNat.{0} Nat (nat_lit 63) (instOfNatNat (nat_lit 63)))
(@Nat.instNeZeroSucc (@OfNat.ofNat.{0} Nat (nat_lit 62) (instOfNatNat (nat_lit 62)))))))
(@Nat.cast.{0} Real Real.instNatCast i.size)))
(a
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 64) (instOfNatNat (nat_lit 64))) i.size)))
(@HDiv.hDiv.{0, 0, 0} Real Real Real (@instHDiv.{0} Real (@DivInvMonoid.toDiv.{0} Real Real.instDivInvMonoid))
i.accuracy
(@OfNat.ofNat.{0} Real (nat_lit 16)
(@instOfNatAtLeastTwo.{0} Real (nat_lit 16) Real.instNatCast
(@Nat.instAtLeastTwoHAddOfNat (@OfNat.ofNat.{0} Nat (nat_lit 15) (instOfNatNat (nat_lit 15)))
(@Nat.instNeZeroSucc (@OfNat.ofNat.{0} Nat (nat_lit 14) (instOfNatNat (nat_lit 14))))))))))) ∧ ((∀ (p : DecrAlmostLinearSSSP.Decremental.Program),
DecrAlmostLinearSSSP.Decremental.Native.ControlFrame (DecrAlmostLinearSSSP.Decremental.Native.scaleInitBody p)) ∧ (∀ (p : DecrAlmostLinearSSSP.Decremental.Program),
DecrAlmostLinearSSSP.Decremental.Native.ControlFrame (DecrAlmostLinearSSSP.Decremental.Native.scaleInitLoop p)))) ∧ (((∀ (p : DecrAlmostLinearSSSP.Decremental.Program),
DecrAlmostLinearSSSP.Decremental.Native.ControlFrame (DecrAlmostLinearSSSP.Decremental.Native.scaleInitAll p)) ∧ (∀ (i : DecrAlmostLinearSSSP.Decremental.Input),
i.Valid →
∀ (p : DecrAlmostLinearSSSP.Decremental.Program) (C : Real) (a : Nat → Real) (queryBound : Nat),
@LT.lt.{0} Real Real.instLT
(@HDiv.hDiv.{0, 0, 0} Real Real Real (@instHDiv.{0} Real (@DivInvMonoid.toDiv.{0} Real Real.instDivInvMonoid))
(@OfNat.ofNat.{0} Real (nat_lit 1) (@One.toOfNat1.{0} Real Real.instOne))
(@Nat.cast.{0} Real Real.instNatCast i.size))
i.accuracy →
∀ (B reserve : Nat),
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) i.n
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3))) i.k))
B →
∀ (f : Fin (DecrAlmostLinearSSSP.Decremental.scaleCount i) → DecrAlmostLinearSSSP.Decremental.Machine),
(∀ (q : Fin (DecrAlmostLinearSSSP.Decremental.scaleCount i)),
DecrAlmostLinearSSSP.Decremental.Native.InitialFacts p C a i
(@Fin.val (DecrAlmostLinearSSSP.Decremental.scaleCount i) q) (f q)) →
(∀ (q : Fin (DecrAlmostLinearSSSP.Decremental.scaleCount i)),
DecrAlmostLinearSSSP.Decremental.Maintains p C a queryBound Bool.false
(DecrAlmostLinearSSSP.Decremental.barrierInput i
(@Fin.val (DecrAlmostLinearSSSP.Decremental.scaleCount i) q))) →
∀ (done : Nat) (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.Native.InitPrefix i p B reserve f done s →
@LT.lt.{0} Nat instLTNat done (DecrAlmostLinearSSSP.Decremental.scaleCount i) →
∃ cost t,
And
(DecrAlmostLinearSSSP.Decremental.Structured.Eval
(DecrAlmostLinearSSSP.Decremental.Native.scaleInitBody p) s cost t)
(And
(DecrAlmostLinearSSSP.Decremental.Native.InitPrefix i p B reserve f
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) done
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
t)
(@LE.le.{0} Nat instLENat cost
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.dispatchCharge p.code)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
(@DecrAlmostLinearSSSP.Decremental.Native.maxInitialWork i f))
(DecrAlmostLinearSSSP.Decremental.Native.initOverhead i p))
(@OfNat.ofNat.{0} Nat (nat_lit 5) (instOfNatNat (nat_lit 5)))))))) ∧ ((∀ (i : DecrAlmostLinearSSSP.Decremental.Input),
i.Valid →
∀ (p : DecrAlmostLinearSSSP.Decremental.Program) (C : Real) (a : Nat → Real) (queryBound : Nat),
@LT.lt.{0} Real Real.instLT
(@HDiv.hDiv.{0, 0, 0} Real Real Real (@instHDiv.{0} Real (@DivInvMonoid.toDiv.{0} Real Real.instDivInvMonoid))
(@OfNat.ofNat.{0} Real (nat_lit 1) (@One.toOfNat1.{0} Real Real.instOne))
(@Nat.cast.{0} Real Real.instNatCast i.size))
i.accuracy →
∀ (B reserve : Nat),
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) i.n
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3))) i.k))
B →
∀ (f : Fin (DecrAlmostLinearSSSP.Decremental.scaleCount i) → DecrAlmostLinearSSSP.Decremental.Machine),
(∀ (q : Fin (DecrAlmostLinearSSSP.Decremental.scaleCount i)),
DecrAlmostLinearSSSP.Decremental.Native.InitialFacts p C a i
(@Fin.val (DecrAlmostLinearSSSP.Decremental.scaleCount i) q) (f q)) →
(∀ (q : Fin (DecrAlmostLinearSSSP.Decremental.scaleCount i)),
DecrAlmostLinearSSSP.Decremental.Maintains p C a queryBound Bool.false
(DecrAlmostLinearSSSP.Decremental.barrierInput i
(@Fin.val (DecrAlmostLinearSSSP.Decremental.scaleCount i) q))) →
∀ (done : Nat) (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.Native.InitPrefix i p B reserve f done s →
∃ cost t,
And
(DecrAlmostLinearSSSP.Decremental.Structured.Eval
(DecrAlmostLinearSSSP.Decremental.Native.scaleInitLoop p) s cost t)
(And
(DecrAlmostLinearSSSP.Decremental.Native.InitPrefix i p B reserve f
(DecrAlmostLinearSSSP.Decremental.scaleCount i) t)
(@LE.le.{0} Nat instLENat cost
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.dispatchCharge p.code)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
(@DecrAlmostLinearSSSP.Decremental.Native.maxInitialWork i f))
(DecrAlmostLinearSSSP.Decremental.Native.initOverhead i p))
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(@HSub.hSub.{0, 0, 0} Nat Nat Nat (@instHSub.{0} Nat instSubNat)
(DecrAlmostLinearSSSP.Decremental.scaleCount i) done))
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))))) ∧ ((∀ (i : DecrAlmostLinearSSSP.Decremental.Input),
i.Valid →
∀ (p : DecrAlmostLinearSSSP.Decremental.Program) (C : Real) (a : Nat → Real) (queryBound : Nat),
@LT.lt.{0} Real Real.instLT
(@HDiv.hDiv.{0, 0, 0} Real Real Real (@instHDiv.{0} Real (@DivInvMonoid.toDiv.{0} Real Real.instDivInvMonoid))
(@OfNat.ofNat.{0} Real (nat_lit 1) (@One.toOfNat1.{0} Real Real.instOne))
(@Nat.cast.{0} Real Real.instNatCast i.size))
i.accuracy →
∀ (B reserve : Nat),
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) i.n
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3))) i.k))
B →
∀ (f : Fin (DecrAlmostLinearSSSP.Decremental.scaleCount i) → DecrAlmostLinearSSSP.Decremental.Machine),
(∀ (q : Fin (DecrAlmostLinearSSSP.Decremental.scaleCount i)),
DecrAlmostLinearSSSP.Decremental.Native.InitialFacts p C a i
(@Fin.val (DecrAlmostLinearSSSP.Decremental.scaleCount i) q) (f q)) →
(∀ (q : Fin (DecrAlmostLinearSSSP.Decremental.scaleCount i)),
DecrAlmostLinearSSSP.Decremental.Maintains p C a queryBound Bool.false
(DecrAlmostLinearSSSP.Decremental.barrierInput i
(@Fin.val (DecrAlmostLinearSSSP.Decremental.scaleCount i) q))) →
∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.Native.Globals i B
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B i.n
(DecrAlmostLinearSSSP.Decremental.scaleCount i) reserve
(DecrAlmostLinearSSSP.Decremental.registerBound p.code)).utility
s →
@Eq.{1} Nat (s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 84) (instOfNatNat (nat_lit 84))))
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B i.n
(DecrAlmostLinearSSSP.Decremental.scaleCount i) reserve
(DecrAlmostLinearSSSP.Decremental.registerBound p.code)).records →
@Eq.{1} Nat (s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 88) (instOfNatNat (nat_lit 88))))
(DecrAlmostLinearSSSP.Decremental.Native.scaleLayout B i.n
(DecrAlmostLinearSSSP.Decremental.scaleCount i) reserve
(DecrAlmostLinearSSSP.Decremental.registerBound p.code)).caches →
@Eq.{1} Nat (s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 80) (instOfNatNat (nat_lit 80))))
(DecrAlmostLinearSSSP.Decremental.scaleCount i) →
@Eq.{1} Nat (s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 100) (instOfNatNat (nat_lit 100))))
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) i.n) →
(∀ (q : Fin (DecrAlmostLinearSSSP.Decremental.scaleCount i)),
DecrAlmostLinearSSSP.Decremental.SourceMemory.Image B
(@Fin.val (DecrAlmostLinearSSSP.Decremental.scaleCount i) q) s
(fun x => @OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) fun x =>
@OfNat.ofNat.{0} Real (nat_lit 0) (@Zero.toOfNat0.{0} Real Real.instZero)) →
(∀ (address : Nat),
@LE.le.{0} Nat instLENat address B →
@Eq.{1} Nat (s.natMem address)
((DecrAlmostLinearSSSP.Decremental.initialMachine p i).natMem address)) →
(∀ (r : Nat),
@LE.le.{0} Nat instLENat (DecrAlmostLinearSSSP.Decremental.registerBound p.code)
r →
And
(@Eq.{1} Nat (s.natReg (DecrAlmostLinearSSSP.Decremental.shadowReg r))
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(@Eq.{1} Real (s.realReg (DecrAlmostLinearSSSP.Decremental.shadowReg r))
(@OfNat.ofNat.{0} Real (nat_lit 0)
(@Zero.toOfNat0.{0} Real Real.instZero)))) →
∃ cost t,
And
(DecrAlmostLinearSSSP.Decremental.Structured.Eval
(DecrAlmostLinearSSSP.Decremental.Native.scaleInitAll p) s cost t)
(And
(DecrAlmostLinearSSSP.Decremental.Native.InitPrefix i p B reserve f
(DecrAlmostLinearSSSP.Decremental.scaleCount i) t)
(@LE.le.{0} Nat instLENat cost
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.dispatchCharge p.code)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
(@DecrAlmostLinearSSSP.Decremental.Native.maxInitialWork i f))
(DecrAlmostLinearSSSP.Decremental.Native.initOverhead i p))
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(DecrAlmostLinearSSSP.Decremental.scaleCount i))
(@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))))))) ∧ (∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.Structured.Eval DecrAlmostLinearSSSP.Decremental.Native.clearLast s
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))
(DecrAlmostLinearSSSP.Decremental.Native.clearLastData s)))))) ∧ ((((∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
And
(@Eq.{1} (Nat → Nat) (DecrAlmostLinearSSSP.Decremental.Native.clearLastData s).natMem
(@Function.update.{1, 1} Nat (fun a => Nat) instDecidableEqNat s.natMem
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HSub.hSub.{0, 0, 0} Nat Nat Nat (@instHSub.{0} Nat instSubNat)
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 106) (instOfNatNat (nat_lit 106))))
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 134) (instOfNatNat (nat_lit 134)))))
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 14) (instOfNatNat (nat_lit 14)))))
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 56) (instOfNatNat (nat_lit 56))))))
(@Eq.{1} (Nat → Real) (DecrAlmostLinearSSSP.Decremental.Native.clearLastData s).realMem s.realMem)) ∧ (∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data) (base stride S : Nat),
@LT.lt.{0} Nat instLTNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) S →
@Eq.{1} Nat (s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 106) (instOfNatNat (nat_lit 106))))
(DecrAlmostLinearSSSP.Decremental.Native.recordAt base stride S) →
@Eq.{1} Nat (s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 134) (instOfNatNat (nat_lit 134)))) stride →
@Eq.{1} Nat (s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 14) (instOfNatNat (nat_lit 14))))
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) →
@Eq.{1} Nat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HSub.hSub.{0, 0, 0} Nat Nat Nat (@instHSub.{0} Nat instSubNat)
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 106) (instOfNatNat (nat_lit 106))))
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 134) (instOfNatNat (nat_lit 134)))))
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 14) (instOfNatNat (nat_lit 14)))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Native.recordAt base stride
(@HSub.hSub.{0, 0, 0} Nat Nat Nat (@instHSub.{0} Nat instSubNat) S
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))) ∧ ((∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {j record cache oldNext newNext : Nat}
{s t : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.Native.RecordImage i j record cache oldNext s →
@Eq.{1} (Nat → Nat) t.natMem
(@Function.update.{1, 1} Nat (fun a => Nat) instDecidableEqNat s.natMem
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) record
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
newNext) →
@Eq.{1} (Nat → Real) t.realMem s.realMem →
DecrAlmostLinearSSSP.Decremental.Native.RecordImage i j record cache newNext t) ∧ ((∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {p : DecrAlmostLinearSSSP.Decremental.Program}
{B j record cache oldNext newNext : Nat} {g : DecrAlmostLinearSSSP.Decremental.Machine} {b : Fin i.n → ENNReal}
{s t : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.Native.ScaleMemory i p B j record cache oldNext g b s →
(∃ r,
@Eq.{1} Nat record
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) B
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) r))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))) →
@LT.lt.{0} Nat instLTNat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) record
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
cache →
@Eq.{1} (Nat → Nat) t.natMem
(@Function.update.{1, 1} Nat (fun a => Nat) instDecidableEqNat s.natMem
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) record
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
newNext) →
@Eq.{1} (Nat → Real) t.realMem s.realMem →
DecrAlmostLinearSSSP.Decremental.Native.ScaleMemory i p B j record cache newNext g b t) ∧ (∀ (k : Nat),
@Ne.{1} Nat k (@OfNat.ofNat.{0} Nat (nat_lit 218) (instOfNatNat (nat_lit 218))) →
DecrAlmostLinearSSSP.Decremental.Structured.NatFrame DecrAlmostLinearSSSP.Decremental.Native.clearLast k)))) ∧ (((∀ (k : Nat), DecrAlmostLinearSSSP.Decremental.Structured.RealFrame DecrAlmostLinearSSSP.Decremental.Native.clearLast k) ∧ (DecrAlmostLinearSSSP.Decremental.TailFrame DecrAlmostLinearSSSP.Decremental.Native.clearLast)) ∧ ((DecrAlmostLinearSSSP.Decremental.Native.GlobalFrame DecrAlmostLinearSSSP.Decremental.Native.clearLast) ∧ ((∀ (i : DecrAlmostLinearSSSP.Decremental.Input) (p : DecrAlmostLinearSSSP.Decremental.Program) (B reserve : Nat)
(f : Fin (DecrAlmostLinearSSSP.Decremental.scaleCount i) → DecrAlmostLinearSSSP.Decremental.Machine)
(s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.Native.InitPrefix i p B reserve f (DecrAlmostLinearSSSP.Decremental.scaleCount i) s →
∃ t,
And
(DecrAlmostLinearSSSP.Decremental.Structured.Eval DecrAlmostLinearSSSP.Decremental.Native.clearLast s
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3))) t)
(DecrAlmostLinearSSSP.Decremental.Native.InitDone i p B reserve f t)) ∧ (∀ {s t : DecrAlmostLinearSSSP.Decremental.Structured.Data} {vertex : Nat}
{rows : List.{0} DecrAlmostLinearSSSP.Decremental.LinkedScan.Row},
DecrAlmostLinearSSSP.Decremental.LinkedScan.RowsView s vertex rows →
@Eq.{1} (Nat → Real) t.realMem s.realMem →
@Eq.{1} (Nat → Nat) t.natMem s.natMem → DecrAlmostLinearSSSP.Decremental.LinkedScan.RowsView t vertex rows)))))))) := by sorry