https://scholars.lib.ntu.edu.tw/handle/123456789/155089
標題: | Global and local views of state fairness | 作者: | Howell, Rodney R. Rosier, Louis E. Yen, Hsu-Chun |
公開日期: | 1991 | 卷: | 80 | 期: | 1 | 起(迄)頁: | 77-104 | 來源出版物: | Theoretical Computer Science | 摘要: | In 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. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-0026119449&doi=10.1016%2f0304-3975%2891%2990206-H&partnerID=40&md5=df07486f0a60ed8d41d9377cb7652649 | DOI: | 10.1016/0304-3975(91)90206-H | SDG/關鍵字: | Automata 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 Metatheory |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。