A Behavioural Theory of Probabilistic Algorithms Using Probabilistic Abstract State Machines
2026-06-22 • Logic in Computer Science
Logic in Computer Science
AI summaryⓘ
The authors propose a clear set of rules (postulates) to define what probabilistic algorithms are. They then introduce a model called probabilistic Abstract State Machines (pASMs) to describe these algorithms. Their main result is proving that any probabilistic algorithm following their rules can be represented exactly by a pASM. This helps connect abstract definitions of randomness in algorithms with a concrete framework for simulation.
probabilistic algorithmspostulatesrandom branching timeabstract statesbounded explorationAbstract State Machinesprobabilistic Abstract State Machinesalgorithm simulationbehavioral equivalence
Authors
Flavio Ferrarotti, Klaus-Dieter Schewe
Abstract
We motivate an axiomatic definition of probabilistic algorithms (PAs) by four postulates covering random branching time, abstract states, background, and random bounded exploration. Then, we introduce probabilistic Abstract State Machines (pASMs) and show that they specify PAs. Finally, we prove that every PA satisfying these postulates can be simulated step-by-step by a behaviourally equivalent pASM with the same signature and background.