Documentation

Determinize.Proof.Traces.Semantics

Detailed trace semantics as kernels #

The one-step law together with its recorded event (record, tracedStepKernel), the joint law of a detailed trace and output at an exact depth as a measurable kernel (exactKernel, equal to exactMeasure), and trace erasure (correspondence): forgetting the trace recovers the ordinary output semantics.

theorem Determinize.Proof.StepTraces.map_bind {α : Type u_1} {β : Type u_2} {γ : Type u_3} [MeasurableSpace α] [MeasurableSpace β] [MeasurableSpace γ] (μ : MeasureTheory.Measure α) (kernel : ProbabilityTheory.Kernel α β) (f : β → γ) (hf : Measurable f) :
MeasureTheory.Measure.map f (μ.bind ⇑kernel) = μ.bind fun (a : α) => MeasureTheory.Measure.map f (kernel a)
theorem Determinize.Proof.StepTraces.bind_map {α : Type u_1} {β : Type u_2} {γ : Type u_3} [MeasurableSpace α] [MeasurableSpace β] [MeasurableSpace γ] (μ : MeasureTheory.Measure α) (f : α → β) (hf : Measurable f) (kernel : ProbabilityTheory.Kernel β γ) :
(MeasureTheory.Measure.map f μ).bind ⇑kernel = μ.bind fun (a : α) => kernel (f a)

A one-step expression kernel used to prove measurability of the direct trace evaluator.

Equations
Instances For
    theorem Determinize.Proof.StepTraces.recordKernel_apply {α : Type u_1} [MeasurableSpace α] {action : α → Spec.Paper.Action} (family : Paper.MeasurableActionFamily α action) (parameter : α) :
    (recordKernel family).kernel parameter = record (action parameter)
    Equations
    • One or more equations did not get rendered due to their size.
    Instances For

      One reduction step with its recorded event, record (reduce expression), as a measurable kernel (tracedStepKernel_apply).

      Equations
      • One or more equations did not get rendered due to their size.
      Instances For

        Extend an exact-depth kernel by one recorded step: run previous on the successor and put the event in front of the trace.

        Equations
        • One or more equations did not get rendered due to their size.
        Instances For

          exactMeasure depth as a measurable kernel (exactKernel_apply).

          Equations
          • One or more equations did not get rendered due to their size.
          Instances For
            theorem Determinize.Proof.StepTraces.exactKernel_apply (depth : ℕ) (expression : Spec.Paper.Expr) :
            (exactKernel depth).kernel expression = exactMeasure depth expression
            theorem Determinize.Proof.StepTraces.exact_succ_kernel (depth : ℕ) (expression : Spec.Paper.Expr) (notValue : expression.isValue ≠ true) :
            exactMeasure (depth + 1) expression = (record (Spec.Paper.reduce expression)).bind ⇑(successorKernel (exactKernel depth)).kernel