On the complexity of deciding fair termination of probabilistic concurrent finite-state programs (Q1111384)

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.