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

DOI10.1016/0304-3975(88)90031-XzbMath0658.68054MaRDI QIDQ1111384

Hsu-Chun Yen, Louis E. Rosier

Publication date: 1988

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

zbMATH Keywords

complexity; fairness; fair termination; finite-state programs; probabilistic finite-states concurrent programs

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

68Q60: Specification and verification (program logics, model checking, etc.)

Related Items

Priority systems with many identical processes, Global and local views of state fairness, Problems concerning fairness and temporal logic for conflict-free Petri nets, A multiparameter analysis of domino tiling with an application to concurrent systems, Communicating processes, scheduling, and the complexity of nontermination, Quantitative Analysis under Fairness Constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Space-bounded hierarchies and probabilistic computations
• The complexity of problems in systems of communicating sequential processes
• The choice coordination problem
• Techniques for separating space complexity classes
• Complete problems for deterministic polynomial time
• A multiparameter analysis of the boundedness problem for vector addition systems
• Verification of Probabilistic Programs
• Gradually intractable problems and nondeterministic log-space lower bounds
• Some combinatorial game problems require Ω( n ^k ) time
• Alternation
• Logspace hierarchies, polynomial time and the complexity of fairness problems concerning ω-machines
• Termination of Probabilistic Concurrent Program