Probabilistic termination versus fair termination (Q1822937)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Probabilistic termination versus fair termination |
scientific article |
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
