On the complexity of deciding fair termination of probabilistic concurrent finite-state programs
DOI10.1016/0304-3975(88)90031-XzbMATH Open0658.68054OpenAlexW2077620037MaRDI QIDQ1111384FDOQ1111384
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
Recommendations
fairnesscomplexityfair terminationfinite-state programsprobabilistic finite-states concurrent programs
Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Space-bounded hierarchies and probabilistic computations
- Alternation
- Complete problems for deterministic polynomial time
- Title not available (Why is that?)
- A multiparameter analysis of the boundedness problem for vector addition systems
- Title not available (Why is that?)
- Techniques for separating space complexity classes
- Some combinatorial game problems require Ω( n k ) time
- Verification of Probabilistic Programs
- The complexity of problems in systems of communicating sequential processes
- Termination of Probabilistic Concurrent Program
- The choice coordination problem
- Logspace hierarchies, polynomial time and the complexity of fairness problems concerning ω-machines
- Gradually intractable problems and nondeterministic log-space lower bounds
- Title not available (Why is that?)
Cited In (12)
- Probabilistic termination versus fair termination
- Quantitative analysis under fairness constraints
- Concurrent Probabilistic Programs, Or: How to Schedule If You Must
- Problems concerning fairness and temporal logic for conflict-free Petri nets
- Fair termination is decidable for ground systems
- A multiparameter analysis of domino tiling with an application to concurrent systems
- Termination Problems in Chemical Kinetics
- Title not available (Why is that?)
- Global and local views of state fairness
- Communicating processes, scheduling, and the complexity of nontermination
- Fair termination for parameterized probabilistic concurrent systems
- 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)
