The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs (Q1960417): Difference between revisions

[For the previous parts see Zbl 0877.68087, Zbl 0872.03026, and the citations given there.] This is the eleventh paper in the author's extensive study of the expressive power of monadic second-order (MSO) logic in the realm of graph theory. Here he proves that the unique decompositions of connected graphs introduced by W. Tutte are definable by MSO-formulas. For obtaining this result it is first shown that every 2-dag has a unique canonical decomposition which is MSO-definable; a 2-dag is a (finite) directed acyclic graph in which every vertex lies on a path from a fixed source vertex to a fixed target vertex.