The monadic second-order logic of graphs. VIII: Orientations (Q1842126)

[For Part VII of this series of papers see Theor. Comput. Sci. 101, No. 1, 3-33 (1992; Zbl 0809.03006).] Two natural ways of representing graphs and hypergraphs as logical structures are investigated and compared. Including both the vertices and the edges in the domains of the logical structures representing (hyper)graphs leads to a monadic second-order language denoted by \(\mathbf {MS}_{\mathbf{2}}\). If the domains consist of the vertices only, a weaker language \(\mathbf {MS}_{\mathbf{1}}\) is obtained. The border between these two languages was considered already earlier by the author [Discrete Appl. Math. 54, No. 2-3, 117-149 (1994; Zbl 0809.03005)] in this series of papers. In the present paper several questions concerning the role of the orientation of the edges of graphs in connection with \(\mathbf {MS}_{\mathbf{1}}\)- and \(\mathbf {MS}_{\mathbf{2}}\)- definitions are considered. One of the general findings is that even if a class of finite directed graphs is \(\mathbf {MS}_{\mathbf{1}}\)- definable, the class of the corresponding underlying undirected graphs is not necessarily \(\mathbf {MS}_{\mathbf{1}}\)-definable, but that \(\mathbf {MS}_{\mathbf{2}}\)-definability is not similarly sensitive to orientation. The second class of problems concerns the decidability of the \(\mathbf {MS}_{\mathbf{2}}\)- and \(\mathbf {MS}_{\mathbf{1}}\)- theories of classes of finite (hyper)graphs. Using and extending some earlier results, the author shows that tree-width characterizes the classes of graphs and hypergraphs of bounded rank having a decidable \(\mathbf {MS}_{\mathbf{2}}\)-theory, and a complexity measure which would characterize \(\mathbf {MS}_{\mathbf{1}}\)-definability in the same way is conjectured. The main result in the third general problem area considered is that all orientations of undirected graphs or hypergraphs of bounded rank can be defined as \(\mathbf {MS}_{\mathbf{2}}\)-formulae, but not by \(\mathbf {MS}_{\mathbf{1}}\)-formulae.