Logspace Hierarchies, Polynomial Time and the Complexity of Fairness Problems Concerning \omega -Machines

DOI10.1137/0216052zbMATH Open0638.68031OpenAlexW2007706420MaRDI QIDQ3779740FDOQ3779740

Authors: Louis E. Rosier, Hsu-Chun Yen 

Publication date: 1987

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0216052

Recommendations

• Logspace hierarchies, polynomial time and the complexity of fairness problems concerning ω-machines
• The alternation hierarchy for sublogarithmic space is infinite
• scientific article; zbMATH DE number 45125
• Publication:4725752
• On the structure of log-space probabilistic complexity classes (extended abstract)

zbMATH Keywords

computational complexityfinite automata\(\omega \)-automatacomplete problemsoracle Turing machinesalternating logspace hierarchylogspace alternation hierarchyspace oracle hierarchy

Mathematics Subject Classification ID

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

Cited In (6)

• Nondeterministic bounded query reducibilities
• Risk assessment for one-counter threads
• Boundedness, hierarchy of fairness, and communication networks with delay
• Problems concerning fairness and temporal logic for conflict-free Petri nets
• Logspace hierarchies, polynomial time and the complexity of fairness problems concerning ω-machines
• On the complexity of finding the chromatic number of a recursive graph. I: The bounded case

This page was built for publication: Logspace Hierarchies, Polynomial Time and the Complexity of Fairness Problems Concerning $\omega $-Machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3779740)