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 the normal view instead:
scientific article; zbMATH DE number 4113954
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.8851013779640198
0 references
0.8206990957260132
0 references
0.820296585559845
0 references
0.8000049591064453
0 references
