A modal perspective on monadic second-order alternation hierarchies
Antti Kuusisto · 2008
We establish that the quantifier alternation hierarchy of for- mulae of Second-Order Propositional Modal Logic ( SOPML) induces an infinite corresponding semantic hierarchy over the class of finite directed graphs. This is a response to an open problem posed in (4) and (8). We also provide modal characterizations of the expressive power of Monadic Second-Order Logic ( MSO) and address a number of points that should promote the potential advantages of viewing MSO and its fragments from the modal perspective.