On the complexity of deciding fair termination of probabilistic concurrent finite-state programs

DOI10.1016/0304-3975(88)90031-XMaRDI QIDQ1111384zbMATHOpenAlexFDO

Authors Louis E. Rosier, Hsu-Chun Yen

Publication date 1988

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

Full work available at URL https://doi.org/10.1016/0304-3975(88)90031-x

zbMATH Keywords

fairnesscomplexityfair terminationfinite-state programsprobabilistic finite-states concurrent programs

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• scientific article; zbMATH DE number 3982496
• Probabilistic termination versus fair termination
• Concurrent Probabilistic Programs, Or: How to Schedule If You Must
• Fair termination for parameterized probabilistic concurrent systems
• Global and local views of state fairness

Cites work

• scientific article; zbMATH DE number 3883610 (Why is no real title available?)
• scientific article; zbMATH DE number 3655356 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3735115 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3240812 (Why is no real title available?)
• A multiparameter analysis of the boundedness problem for vector addition systems
• Alternation
• Complete problems for deterministic polynomial time
• Gradually intractable problems and nondeterministic log-space lower bounds
• Logspace hierarchies, polynomial time and the complexity of fairness problems concerning ω-machines
• Some combinatorial game problems require Ω( n ^k ) time
• Space-bounded hierarchies and probabilistic computations
• Techniques for separating space complexity classes
• Termination of Probabilistic Concurrent Program
• The choice coordination problem
• The complexity of problems in systems of communicating sequential processes
• Verification of Probabilistic Programs

Cited in

(12)

• A multiparameter analysis of domino tiling with an application to concurrent systems
• scientific article; zbMATH DE number 3982496 (Why is no real title available?)
• Quantitative analysis under fairness constraints
• Communicating processes, scheduling, and the complexity of nontermination
• Probabilistic termination versus fair termination
• Global and local views of state fairness
• Concurrent Probabilistic Programs, Or: How to Schedule If You Must
• Problems concerning fairness and temporal logic for conflict-free Petri nets
• Fair termination for parameterized probabilistic concurrent systems
• Fair termination is decidable for ground systems
• Termination Problems in Chemical Kinetics
• Priority systems with many identical processes

This page was built for publication: On the complexity of deciding fair termination of probabilistic concurrent finite-state programs

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