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

DOI10.1007/3-540-16078-7_85zbMath0615.68041OpenAlexW1480627260MaRDI QIDQ4723306

Hsu-Chun Yen, Louis E. Rosier

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

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

Related Items (4)

Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states ⋮ An introduction to the regular theory of fairness ⋮ On the complexity of deciding fair termination of probabilistic concurrent finite-state programs ⋮ The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\)

This page was built for publication: Logspace hierarchies, polynomial time and the complexity of fairness problems concerning ω-machines