scientific article; zbMATH DE number 3982496
[For the entire collection see Zbl 0587.00019.] The main contribution of the paper is that the authors give a comprehensive analysis of the fair termination problem for probabilistic concurrent finite-state programs under 5 types of fairness constraints. Firstly, it is defined the model of probabilistic concurrent finite-state programs as well as five types of fairness criteria. Based on this model, it is shown that the fair termination problem depends only on the topological structure of the program's termination, and not on the particular values of the nonzero transition probabilities. This constitutes a generalization of a result known up to now. Therefore, the authors are able to use a graph-theoretical approach to determine whether programs will terminate with probability 1 under each of the fairness constraints. Next, there are investigated upper and lower complexity bounds for the problems considered. Lastly, it is considered the case when a more succinct representation of the inputs is allowed (it has been assumed that the inputs are essentially provided in the form of the global state graph).
- On the complexity of deciding fair termination of probabilistic concurrent finite-state programs
- Probabilistic termination versus fair termination
- Concurrent Probabilistic Programs, Or: How to Schedule If You Must
- Probabilistic verification
- Fair termination for parameterized probabilistic concurrent systems
- Probabilistic Ianov's schemes
- Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
- On the complexity of deciding fair termination of probabilistic concurrent finite-state programs
- Probabilistic termination versus fair termination
- Fair termination for parameterized probabilistic concurrent systems
- Concurrent Probabilistic Programs, Or: How to Schedule If You Must
- Global and local views of state fairness
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3746869)