In: Theoretical Computer Science, Vol. 80, pages 77-104. 1991.
Abstract: The authors compare global and local versions of state fairness for systems of concurrent programs and Petri nets. They investigate complexity and decidability issues for the fair nondetermination problem. It turns out that for systems of concurrent Boolean programs and 1-bounded Petri nets, the problem is PSPACE-complete with respect to global state fairness, but EXPTIME-complete with respect to local state fairness. For general systems of concurrent programs, both the globally and locally state fair nontermination problems are undecidable.
Keywords: global (and) local (version of) state fairness; complexity (and) decidability (of the) fair nondetermination problem; concurrent Boolean program; (1-) bounded net; PSPACE completeness; EXPTIME completeness; undecidability.