Probabilistic termination versus fair termination
type: Item
instance of: scholarly article
title: Probabilistic termination versus fair termination
zbMATH Open document ID: 0679.68028
DOI: 10.1016/0304-3975(89)90158-8
author: Michael Tiomkin
published in: Theoretical Computer Science
publication date: 1989-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 68Q60
Mathematics Subject Classification ID: 68N25
Mathematics Subject Classification ID: 03B70
Mathematics Subject Classification ID: 68Q65
zbMATH DE Number: 4113954
zbMATH Keywords: fairness
zbMATH Keywords: probabilistic programs
zbMATH Keywords: termination of concurrent programs
reviewed by: Luboš Brim
MaRDI profile type: Publication
full work available at URL: 0304-3975(89)90158-8
OpenAlex ID: W1980608699
cites work: Guarded commands, nondeterminacy and formal derivation of programs
cites work: Q3738540
cites work: A proof rule for fair termination of guarded commands
cites work: Termination of Probabilistic Concurrent Program
cites work: Q5509984
cites work: Q4138569
cites work: Q5573961
cites work: Q5593890
cites work: Q5807665
cites work: Propositional dynamic logic with local assignments
description: scientific article; zbMATH DE number 4113954