Lune

LICS2025Top-tier venue

Probabilistic Strategies: Definability and the Tensor Completeness Problem

Nathan J. Bowler, Sergey Goncharov, Paul Blain Levy

Abstract

Programs that combine I/O and countable probabilistic choice, modulo either bisimilarity or trace equivalence, can be seen as describing a probabilistic strategy. For wellfounded programs, we might expect to axiomatize bisimilarity via a sum of equational theories and trace equivalence via a tensor of such theories. This is by analogy with similar results for nondeterminism, established previously. While bisimilarity is indeed axiomatized via a sum of theories, and the tensor is indeed at least sound for trace equivalence, completeness in general, remains an open problem. Nevertheless, we show completeness in the case that either the probabilistic choice or the I/O operations used are finitary. We also show completeness up to impersonation, i.e. that the tensor theory regards trace equivalent programs as solving the same system of equations. This entails completeness up to the cancellation law of the probabilistic choice operator.

Furthermore, we show that a probabilistic trace strategy arises as the semantics of a well-founded program iff it is victorious. This means that, when the strategy is played against any partial counterstrategy, the probability of play continuing forever is zero.

We link our results (and open problem) to particular monads that can be used to model computational effects.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on1

  1. Refinement-Based Game Semantics for Certified Abstraction LayersJérémie Koenig, Zhong ShaoLICS 2020 · 17 citations

Related papers

  1. Combining Nondeterminism, Probability, and Termination: Equational and Metric ReasoningMatteo Mio, Ralph Sarkis, Valeria VignudelliLICS 2021 · 14 citations
  2. Step-Indexed Logical Relations for Countable Nondeterminism and Probabilistic ChoiceAlejandro Aguirre, Lars BirkedalPOPL 2023 · 13 citations
  3. Combining probabilistic and non-deterministic choice via weak distributive lawsAlexandre Goy, Daniela PetrisanLICS 2020 · 30 citations
  4. Fully Abstract Normal Form Bisimulation for Call-by-Value PCFVasileios Koutavas, Yu-Yang Lin, Nikos TzevelekosLICS 2023 · 8 citations
  5. Behavioural Preorders via Graded MonadsChase Ford, Stefan Milius, Lutz SchröderLICS 2021 · 8 citations
Dusk over the sea between two cliffs drawn in fine vertical lines