On the complexity of deciding fair termination of probabilistic concurrent finite-state programs (Q1111384): Difference between revisions
From MaRDI portal
Latest revision as of 10:21, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the complexity of deciding fair termination of probabilistic concurrent finite-state programs |
scientific article |
Statements
On the complexity of deciding fair termination of probabilistic concurrent finite-state programs (English)
0 references
1988
0 references
Systems of probabilistic finite-states concurrent programs are considered and the problem of their fair termination with probability 1 is addressed. Necessary and sufficient conditions for solving this problem under five different fairness assumptions are given. Moreover, the complexity of the presented problem is analysed and it is proved that, depending on the fairness criterion, it is either complete for PTIME or on the second or third level of the alternating logspace hierarchy. Finally, lower and upper bounds are given for the same problem in the special case when a more succinct representation of the input is assumed.
0 references
finite-state programs
0 references
probabilistic finite-states concurrent programs
0 references
fair termination
0 references
fairness
0 references
complexity
0 references
0 references