4 papers
A Behavioural Theory of Probabilistic Algorithms Using Probabilistic Abstract State Machines
Flavio Ferrarotti, Klaus-Dieter Schewe
We motivate an axiomatic definition of probabilistic algorithms (PAs) by four postulates covering random branching time, abstract states, background, and random bounded exploration…
TREBL -- A Relative Complete Temporal Event-B Logic. Part I: Theory
Klaus-Dieter Schewe, Flavio Ferrarotti, Peter Rivière +3
The verification of liveness conditions is an important aspect of state-based rigorous methods. This article addresses the extension of the logic of Event-B to a powerful logic, in…
Behavioural Theory of Reflective Algorithms II: Reflective Parallel Algorithms
Klaus-Dieter Schewe, Flavio Ferrarotti
We develop a behavioural theory of reflective parallel algorithms (RAs), i.e. synchronous parallel algorithms that can modify their own behaviour. The theory comprises a set of pos…
Insignificant Choice Polynomial Time: A Logic Capturing PTIME
Klaus-Dieter Schewe
In this article choiceless polynomial time (CPT) is extended using non-determini\-stic Abstract State Machines (ASMs), which are restricted by three conditions: (1) choice is restr…