Deciding the First Level of the [my]-calculus Alternation Hierarchy

zum Volltext (1160 kB)   ZIP
Beteiligte Person(en) / Institution(en)Autor :
DatumErschienen :
  • Juli 2002
Seitenbereich40 Seiten

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.
Statische URLhttps://www.uni-kiel.de/journals/receive/jportal_jparticle_00000175
 
URN:NBNurn:nbn:de:gbv:8:1-zs-00000175-a5
IDNummer des Berichts :
  • TR_0209