In this paper we present a technology for proving some non expressibility results for monadic second order logic. As a corollary we get a new, easy, proof of the two results from [AFS00] mentioned above. With our technology we can also make a first small step towards an answer to the hierarchy question by showing that the hierarchy inside closed monadic NP does not collapse on a first order level. The monadic complexity of properties definable in Kozen's mu-calculus is also considered as our technology also applies to the mu-calculus itself.
展开▼
