Path Abstraction for Markov Reward Models: An Isabelle Formalisation in a Free Monoid View

The classical definition of discrete-time Markov chains maps pairs of states to transition probabilities. An alternative, proposed in the context of path abstraction in probabilistic counterexample refinement, is to view them as a transition kernel on the free monoid on the state space, mapping paths directly to path probabilities. In this paper, we first extend the free monoid view and path abstraction algorithm to cumulative rewards on Markov reward models. We then use Isabelle/HOL to formalise Markov chains and reward models in this view, exploiting the discrete finite-prefix semantics to work with Isabelle's standard HOL-Analysis library. We mechanise the path abstraction algorithm and its key correctness properties of well-definedness and monotonic absorption, establishing the preservation of reachability probabilities and expected rewards. Proving the convergence of these quantities on relevant path sets is aided by our use of the lightweight free monoid semantics in place of the standard measure-theoretic one used in established Isabelle formalisations of Markov models. We obtain a verified abstract implementation of path abstraction in Isabelle/HOL, providing a foundation for refinement to efficient executable code and integration with probabilistic model checkers.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-17
DOI
https://doi.org/10.48550/arxiv.2611.22523
Primary Topic
Formal Methods in Verification
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Path Abstraction for Markov Reward Models: An Isabelle Formalisation in a Free Monoid View

Arnd Hartmanns, Robert Modderman
arXiv (Cornell University)
Formal Methods in Verification
preprint

Path Abstraction for Markov Reward Models: An Isabelle Formalisation in a Free Monoid View

Arnd Hartmanns, Robert Modderman
preprint en

Abstract

The classical definition of discrete-time Markov chains maps pairs of states to transition probabilities. An alternative, proposed in the context of path abstraction in probabilistic counterexample refinement, is to view them as a transition kernel on the free monoid on the state space, mapping paths directly to path probabilities. In this paper, we first extend the free monoid view and path abstraction algorithm to cumulative rewards on Markov reward models. We then use Isabelle/HOL to formalise Markov chains and reward models in this view, exploiting the discrete finite-prefix semantics to work with Isabelle's standard HOL-Analysis library. We mechanise the path abstraction algorithm and its key correctness properties of well-definedness and monotonic absorption, establishing the preservation of reachability probabilities and expected rewards. Proving the convergence of these quantities on relevant path sets is aided by our use of the lightweight free monoid semantics in place of the standard measure-theoretic one used in established Isabelle formalisations of Markov models. We obtain a verified abstract implementation of path abstraction in Isabelle/HOL, providing a foundation for refinement to efficient executable code and integration with probabilistic model checkers.

arXiv (Cornell University)
Formal Methods in Verification
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon