Global and local views of state fairness (Q804304)

Global and local versions of state fairness for systems of concurrent programs and Petri nets are discussed. The most important assertions are the following: Theorem 4.5: The following two problems are PSPACE-complete: (a) the globally state fair nontermination problem for systems of concurrent Boolean programs (b) the globally state fair nontermination problem for i-bounded Petri nets. Theorem 4.7: The following two problems are complete for EXPTIME: (a) the locally state fair nontermination problem for systems of concurrent Boolean programs (b) the locally state fair nontermination problem for 1-bounded Petri nets. Theorem 5.1: The globally state fair nontermination problem for Petri nets is decidable. Theorem 5.2: The locally state fair nontermination problem for Petri nets is \(\Sigma_ 1\)-hard, where \(\Sigma_ 1\) is the set of languages accepted by Turing machines.