Global and local views of state fairness (Q804304)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Global and local views of state fairness |
scientific article; zbMATH DE number 4201653
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Global and local views of state fairness |
scientific article; zbMATH DE number 4201653 |
Statements
Global and local views of state fairness (English)
0 references
1991
0 references
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.
0 references
fairness
0 references
concurrent programs
0 references
Petri nets
0 references
0 references
0 references
