Probabilistic termination versus fair termination

DOI10.1016/0304-3975(89)90158-8MaRDI QIDQ1822937zbMATH OpenOpenAlexFDO

Authors Michael Tiomkin

Publication date 1989

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(89)90158-8

zbMATH Keywords

fairnessprobabilistic programstermination of concurrent programs

Mathematics Subject Classification ID

Logic in computer science (03B70) Theory of operating systems (68N25) Specification and verification (program logics, model checking, etc.) (68Q60) Abstract data types; algebraic specification (68Q65)

Review text

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.

Recommendations

• On the complexity of deciding fair termination of probabilistic concurrent finite-state programs
• scientific article; zbMATH DE number 3982496
• Concurrent Probabilistic Programs, Or: How to Schedule If You Must
• On the hardness of almost-sure termination
• On the hardness of analyzing probabilistic programs

Cites work

• A proof rule for fair termination of guarded commands
• Guarded commands, nondeterminacy and formal derivation of programs
• scientific article; zbMATH DE number 3972158 (Why is no real title available?)
• scientific article; zbMATH DE number 3566657 (Why is no real title available?)
• scientific article; zbMATH DE number 3222422 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3313523 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• Propositional dynamic logic with local assignments
• Termination of Probabilistic Concurrent Program

Cited in

(12)

• On the complexity of deciding fair termination of probabilistic concurrent finite-state programs
• Temporal predicate transformers and fair termination
• On the hardness of analyzing probabilistic programs
• On the hardness of almost-sure termination
• Fair termination for parameterized probabilistic concurrent systems
• Termination Problems in Chemical Kinetics
• Concurrent Probabilistic Programs, Or: How to Schedule If You Must
• scientific article; zbMATH DE number 3982496 (Why is no real title available?)
• scientific article; zbMATH DE number 2013585 (Why is no real title available?)
• Progress measures and stack assertions for fair termination
• Fairness and Correctness in Case of a Premature Abort
• Fair termination revisited - with delay

This page was built for publication: Probabilistic termination versus fair termination

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1822937)