Documentation

Determinize.Spec.FiniteModel.Model

Finite models #

A finite Markov chain with rational transition probabilities. Evaluation stops at a state that returns a rational reward or rejects. The output law of the chain is defined here, and Model.Matches relates it to the output law of a program.

What happens at a state: evaluation continues from a transient state, stops with a reward at a returned state, and stops without output at a rejected state.

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

      Evaluation stops at terminal states and rewards are paid once, on return. Transition rows at terminal states are ignored by the output semantics.

      • size : ℕ

        The number of states.

      • initial : Fin self.size

        The state in which evaluation starts.

      • kind : Fin self.size → StateKind

        Whether each state is transient, returns a reward, or rejects.

      • transition : Fin self.size → Fin self.size → ℚ

        The probability of moving from the first state to the second in one step.

      • nonnegative (i j : Fin self.size) : 0 ≤ self.transition i j
      • normalized (i : Fin self.size) : ∑ j : Fin self.size, self.transition i j = 1
      Instances For

        Probability that evaluation is still transient after at most steps transitions.

        Equations
        Instances For

          Unnormalized real output accumulated within steps transitions.

          Equations
          Instances For

            Rejection and nontermination contribute no output mass. There is no conditioning.

            Equations
            Instances For

              The model represents the entire output law of this exact core program, and accepted programs cannot get stuck. Rejection and divergence remain possible.

              Equations
              Instances For