In [Bra96], the strictness of the modal mu-calculus alternation hierarchy was shown by transferring a hierarchy from arithmetic; the latter was a corollary of a deep and highly technicla analysis of [Lub93]. In this paper, we show that the alternation hierarchy in arithmetic can be established by entirely elementary means; further, simple examples ofstrict altrnation depth n formulae can be constructed, which in turn give very simple exampels to separate the modal hierarchy. In addition, the winning strategy formulae of parity games are shown to be such examples.
展开▼
