Howell, Rodney R.Rodney R.HowellRosier, Louis E.Louis E.RosierYen, Hsu-ChunHsu-ChunYen2009-03-042018-07-062009-03-042018-07-061991https://www.scopus.com/inward/record.uri?eid=2-s2.0-0026119449&doi=10.1016%2f0304-3975%2891%2990206-H&partnerID=40&md5=df07486f0a60ed8d41d9377cb7652649In this paper, we compare global and local versions of state fairness for systems of concurrent programs and Petri nets. We then investigate complexity and decidability issues for the fair nontermination 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. (In fact, they are Π1-complete and Σ|-complete, respectively.1) On the other hand, the problem is decidable for general Petri nets with respect to global state fairness, and undecidable (Σ1-complete) with respect to local state fairness. © 1991.application/pdf3451294 bytesapplication/pdfen-USAutomata Theory - Computability and Decidability; Computer Programming - Algorithms; Computer Systems Programming - Multiprocessing Programs; Mathematical Techniques - Petri Nets; Boolean Programs; Concurrent Programs; Nontermination Problems; State Fairness; Computer MetatheoryGlobal and local views of state fairnessjournal article10.1016/0304-3975(91)90206-H2-s2.0-0026119449http://ntur.lib.ntu.edu.tw/bitstream/246246/142304/1/02.pdf