Observation equivalence for concurrent processes #
This file packages the notion of "what a party can tell apart" from concrete executions of a concurrent process.
The process semantics keeps the exact dependent type of each local observation, which is ideal when reasoning inside one fixed execution. But comparison across different executions, processes, or refinement layers needs a uniform carrier. The solution adopted here is to pack each local observation together with its type and then compare executions through these packed observations.
The resulting API provides:
- packed local observations for one sequential step;
- per-step observation summaries for finite traces, finite prefixes, and runs;
- generic path relations saying when two executions match; and
- reusable lemmas showing that controller, event, ticket, and observation data are preserved when those path relations hold.
This is the comparison layer later used by refinement and equivalence results.
PackedObs is a locally observed value packaged together with its observation
type.
This is the simplest uniform carrier for local observations whose precise type may vary from one visited node to the next.
Instances For
Forget the dependent indices of an observed sequential path and keep only the concrete packed sequence of observations that was exposed locally.
This is the uniform, comparison-friendly summary of what one party learned from one complete sequential step path.
Equations
- One or more equations did not get rendered due to their size.
- Interaction.Concurrent.Observation.Step.Observed.toList Interaction.Concurrent.Step.Observed.done = []
Instances For
obsList me step tr is the packed sequence of local observations available to
the fixed party me while the sequential process step step executes along
the path tr.
This forgets the exact dependent observation types but keeps their concrete values in order, which makes it the basic comparison object for one process step.
Equations
Instances For
The per-step packed local observations exposed along a finite complete process trace.
Each list element corresponds to one executed process step and stores the local
observations that me obtained during that step.
Equations
- One or more equations did not get rendered due to their size.
- Interaction.Concurrent.Observation.Process.Trace.observations me (Interaction.Concurrent.ProcessOver.Trace.done a) = []
Instances For
The per-step packed local observations exposed along a finite process prefix.
This is the prefix-level analogue of Trace.observations.
Equations
- One or more equations did not get rendered due to their size.
- Interaction.Concurrent.Observation.Process.Prefix.observations me PFunctor.DynSystem.Prefix.nil = []
Instances For
Rel rel left right states that the two finite prefixes left and right
match step-by-step according to the path relation rel.
The length index forces the two prefixes to have the same number of executed steps.
So Prefix.Rel is the generic finite-horizon comparison interface: the caller
chooses what it means for one process step of left to match one process step
of right, and Rel lifts that choice to whole finite prefixes.
Equations
- One or more equations did not get rendered due to their size.
- Interaction.Concurrent.Observation.Process.Prefix.Rel rel PFunctor.DynSystem.Prefix.nil PFunctor.DynSystem.Prefix.nil = True
Instances For
Transporting both prefixes along equal start states does not change their matching relation.
Concurrent.Process.StepRel left right is a cross-process relation on
concrete process steps. Each step pairs its source process state with the
complete path selected there.
This is the basic matching interface used later by refinement, equivalence, and
observation-preservation theorems. The permissive relation and conjunction are
the lattice operations ⊤ and ⊓ on relations.
Equations
- Interaction.Concurrent.Observation.Process.StepRel left right = left.StepRel right
Instances For
Match two paths by equality of their current controlling parties.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Match two paths by equality of their full controller paths.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Match two paths by equality of stable external event labels.
Equations
Instances For
Match two paths by equality of stable tickets.
Equations
Instances For
Match two paths by equality of the packed local observations exposed to one fixed party.
This is the relation that identifies executions that are observationally
indistinguishable to me at the step level.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Matching by current controller equality preserves the extracted controller sequence of finite prefixes.
Matching by controller-path equality preserves the extracted controller path sequence of finite prefixes.
Matching by stable event equality preserves the extracted event sequence of finite prefixes.
Matching by stable ticket equality preserves the extracted ticket sequence of finite prefixes.
Matching by local observation equality preserves the packed observation sequence of finite prefixes for the chosen party.
The per-step packed local observations exposed along the first n steps of the
run run.
This is the infinite-run analogue of Prefix.observations, truncated to the
first n steps.
Equations
- One or more equations did not get rendered due to their size.
- Interaction.Concurrent.Observation.Process.Run.observationsUpTo me run 0 = []
Instances For
RelUpTo rel left right n states that the first n executed steps of the
runs left and right match step-by-step according to rel.
This is the finite-prefix comparison predicate for runs.
Equations
- One or more equations did not get rendered due to their size.
- Interaction.Concurrent.Observation.Process.Run.RelUpTo rel leftRun rightRun 0 = True
Instances For
Rel rel left right states that every finite prefix of the runs left and
right matches according to rel.
So two runs are related when they remain indistinguishable at every finite horizon under the chosen step-matching criterion.
Equations
- Interaction.Concurrent.Observation.Process.Run.Rel rel leftRun rightRun = ∀ (n : ℕ), Interaction.Concurrent.Observation.Process.Run.RelUpTo rel leftRun rightRun n
Instances For
Pointwise path matching implies prefix matching of the first n
steps.
Pointwise path matching implies full run matching.
Matching by current controller equality preserves the extracted controller
sequence of the first n run steps.
Matching by controller-path equality preserves the extracted controller-path
sequence of the first n run steps.
Matching by stable event equality preserves the extracted event sequence of
the first n run steps.
Matching by stable ticket equality preserves the extracted ticket sequence
of the first n run steps.
Matching by local observation equality preserves the packed observation
sequence of the first n run steps for the chosen party.