Logspace Hierarchies, Polynomial Time and the Complexity of Fairness Problems Concerning $\omega $-Machines
From MaRDI portal
Publication:3779740
DOI10.1137/0216052zbMath0638.68031OpenAlexW2007706420MaRDI QIDQ3779740
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
computational complexityfinite automata\(\omega \)-automatacomplete problemsoracle Turing machinesalternating logspace hierarchylogspace alternation hierarchyspace oracle hierarchy
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (5)
Nondeterministic bounded query reducibilities ⋮ Problems concerning fairness and temporal logic for conflict-free Petri nets ⋮ Risk assessment for one-counter threads ⋮ On the complexity of finding the chromatic number of a recursive graph. I: The bounded case ⋮ Boundedness, hierarchy of fairness, and communication networks with delay
This page was built for publication: Logspace Hierarchies, Polynomial Time and the Complexity of Fairness Problems Concerning $\omega $-Machines
