A regular characterization of graph languages definable in monadic second-order logic (Q1177179)

The author shows that the class of graph languages definable by monadic second-order logic, can be characterized as the smallest class containing certain elementary graph languages, and closed under the boolean operations (union, intersection, and complement) and under relabeling. Similar characterization is given to classes of graph languages restricted by some label-independent properties. Some examples are discussed.