On the complexity of deciding fair termination of probabilistic concurrent finite-state programs
From MaRDI portal
Publication:1111384
DOI10.1016/0304-3975(88)90031-XzbMath0658.68054OpenAlexW2077620037MaRDI QIDQ1111384
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
complexityfairnessfair terminationfinite-state programsprobabilistic finite-states concurrent programs
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60)
Related Items (6)
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 ⋮ Priority systems with many identical processes ⋮ Quantitative Analysis under Fairness Constraints ⋮ Global and local views of state fairness
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On the complexity of deciding fair termination of probabilistic concurrent finite-state programs
