scientific article; zbMATH DE number 3982496

From MaRDI portal
Publication:3746869





[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).











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)