Expressive power of monadic logics on words, trees, pictures, and graphs

We give a survey of the expressive power of various monadic logics on specific classes of finite labeled graphs, including words, trees, and pictures. Among the logics we consider, there are monadic second-order logic and its existential fragment, the modal mu-calculus, and monadic least fixed-point logic. We focus on nesting-depth and quan-tifier alternation as a complexity measure of these logics.