Simplifying the modal mu-calculus alternation hierarchy
Julian C. BradfieldAbstract:
In a previous paper, the strictness of the modal mu-calculus alternation hierarchy was shown by transferring a hierarchy from arithmetic; the latter was a minor corollary of a highly technical analysis of Robert Lubarsky. In this paper, we give an entirely elementary proof of that hierarchy; further, simple examples of strict alternation depth n formulae can be constructed, which in turn give very simple examples to separate the modal hierarchy. In addition, the winning strategy formulae of parity games are shown to be such examples.
ECS-LFCS-98-385.This report is available in the following formats:
Previous | Index | Next