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.


Logo BII



Use and reproduction:

No 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.


Citation style:
Could not load citation form.