Logspace hierarchies, polynomial time and the complexity of fairness problems concerning ω-machines

DOI10.1007/3-540-16078-7_85MaRDI QIDQ4723306zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

fairnesscompletenessrelativized computationoracle machinenetworks of communicating finite state machineslogspace alternation hierarchy\(\omega \)-finite state machines\(\omega \)-one counter machinesrestricted logspace oracle hierarchy

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

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

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
• [[:Publication:1118407|The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^Template:\mathcal L=A\Pi_ 2^Template:\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)