No label defined (Q3746869)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3982496
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3982496 |
Statements
1986
0 references
concurrency
0 references
modelling
0 references
fair termination problem
0 references
probabilistic concurrent finite-state programs
0 references
fairness constraints
0 references
complexity bounds
0 references
0.9526975750923156
0 references
0.8487635850906372
0 references
0.8170872926712036
0 references
0.790669322013855
0 references
0.7852150201797485
0 references
[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).
0 references