Logspace hierarchies, polynomial time and the complexity of fairness problems concerning ω-machines
DOI10.1007/3-540-16078-7_85zbMATH Open0615.68041OpenAlexW1480627260MaRDI QIDQ4723306FDOQ4723306
Authors: Louis E. Rosier, Hsu-Chun Yen 
Publication date: 1986
Published in: STACS 86 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-16078-7_85
Recommendations
- Logspace Hierarchies, Polynomial Time and the Complexity of Fairness Problems Concerning $\omega $-Machines
- Proper hierarchies in polylogarithmic time and absence of complete problems
- On the Structure of Logspace Probabilistic Complexity Classes
- Exponential Determinization for ω‐Automata with a Strong Fairness Acceptance Condition
- The relative power of logspace and polynomial time reductions
- Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
- On the structure of log-space probabilistic complexity classes (extended abstract)
- Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines
- Automata, Languages and Programming
- A positive relativization of polynomial time versus polylog space
fairnesscompletenessrelativized computationoracle machinenetworks of communicating finite state machineslogspace alternation hierarchy\(\omega \)-finite state machines\(\omega \)-one counter machinesrestricted logspace oracle hierarchy
Cited In (5)
- Logspace Hierarchies, Polynomial Time and the Complexity of Fairness Problems Concerning $\omega $-Machines
- Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
- The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\)
- An introduction to the regular theory of fairness
- On the complexity of deciding fair termination of probabilistic concurrent finite-state programs
This page was built for publication: Logspace hierarchies, polynomial time and the complexity of fairness problems concerning ω-machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4723306)
