Probabilistic termination versus fair termination (Q1822937)
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: Probabilistic termination versus fair termination |
scientific article; zbMATH DE number 4113954
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Probabilistic termination versus fair termination |
scientific article; zbMATH DE number 4113954 |
Statements
Probabilistic termination versus fair termination (English)
0 references
1989
0 references
The probabilistic almost everywhere termination of concurrent programs is proved to be expressible by a \(\Pi^ 0_ 2\) arithmetic formula and hence it has the complexity equivalent to that of deterministic program termination. This is much simpler then the \(\Pi^ 1_ 1\) complexity of ``fair'' termination.
0 references
fairness
0 references
probabilistic programs
0 references
termination of concurrent programs
0 references
