Deciding the First Level of the μ-calculus Alternation Hierarchy
We show that the following problem is decidable and complete for deterministic exponential time. Given a formula of modal my-calculus, determine if the formula is equivalent to a formula without greatest fixed point operators. In other words, we show that the first level of the my-calculus fixed point alternation hierarchy is decidable in deterministic exponential time.
Use and reproduction:No Creative Commons license - The provisions of the German Copyright Act (UrhG) apply.Please note that individual components of the publication may be subject to other licensing or copyright conditions.