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

*(English)*Zbl 0830.03016[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.

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.

Reviewer: M.Steinby (Turku)

##### MSC:

03C85 | Second- and higher-order model theory |

03B25 | Decidability of theories and sets of sentences |

68R10 | Graph theory (including graph drawing) in computer science |

05C65 | Hypergraphs |

##### Keywords:

representation of graphs and hypergraphs as logical structures; monadic second-order logic; definability; orientation of the edges; decidability; tree-width; bounded rank; complexity measure
PDF
BibTeX
XML
Cite

\textit{B. Courcelle}, Ann. Pure Appl. Logic 72, No. 2, 103--143 (1995; Zbl 0830.03016)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Ajtai, M.; Fagin, R., Reachability is Harder for directed than for undirected graphs, J. symbolic logic, 55, 113-150, (1990) · Zbl 0708.03016 |

[2] | Arnborg, S.; Lagergren, J.; Seese, D., Problems easy for tree-decomposable graphs, J. algorithms, 12, 308-340, (1991) · Zbl 0734.68073 |

[3] | Bauderon, M.; Courcelle, B., Graph expressions and graph rewritings, Math. systems theory, 20, 83-127, (1987) · Zbl 0641.68115 |

[4] | Büchi, J., Weak second-order logic and finite automata, Z. math. logik grundlagen math., 5, 66-92, (1960) · Zbl 0103.24705 |

[5] | Courcelle, B., Graph rewriting: an algebraic and logic approach, (), 193-242 · Zbl 0900.68282 |

[6] | Courcelle, B., The monadic second-order logic of graphs I: recognizable sets of finite graphs, Inform. comput., 85, 12-75, (1990) · Zbl 0722.03008 |

[7] | Courcelle, B., The monadic second order logic of graphs VI: on several representations of graphs by relational structures, Discrete appl. math., 54, 117-149, (1994) · Zbl 0809.03005 |

[8] | Courcelle, B., The monadic second-order logic of graphs V: on closing the gap between definability and recognizability, Theoret. comput. sci., 80, 153-202, (1991) · Zbl 0754.68065 |

[9] | Courcelle, B., The monadic second-order logic of graphs III: tree-decompositions, minors and complexity issues, RAIRO informatique théorique et applications, 26, 257-286, (1992) · Zbl 0754.03006 |

[10] | Courcelle, B., The monadic second order logic of graphs VII: graphs as relational structures, Theoret. comput. sci., 101, 3-33, (1992) · Zbl 0809.03006 |

[11] | Courcelle, B., Monadic second order graph transductions; a survey, Theoret. comput. sci., 126, 53-75, (1994) · Zbl 0805.68077 |

[12] | Courcelle, B., Graph grammars, monadic second-order logic and the theory of graph minors, (), 565-590 · Zbl 0787.05086 |

[13] | Courcelle, B.; Engelfriet, J.; Rozenberg, G., Handle-rewriting hypergraph grammars, J. comput. system sci., 46, 218-270, (1993) · Zbl 0825.68446 |

[14] | B. Courcelle and J. Engelfriet, A logical characterization of the sets of hypergraphs generated by hyperedge replacement grammars, Math. Systems Theory, in press. · Zbl 0830.68098 |

[15] | Courcelle, B.; Mosbah, M., Monadic second-order evaluations on tree-decomposable graphs, Theoret. comput. sci., 109, 49-82, (1993) · Zbl 0789.68083 |

[16] | Diestel, R., Graph decomposition, A study in infinite graph theory, (1990), Clarendon Press Oxford, U.K · Zbl 0726.05001 |

[17] | Dirac, G., On rigid circuit graphs, (), 71-76 · Zbl 0098.14703 |

[18] | Engelfriet, J., A characterization of context-free NCE graph languages by monadic second-order logic on trees, (), 311-327 · Zbl 0765.68090 |

[19] | Engelfriet, J.; Rozenberg, G., Graph grammars based on node rewriting: an introduction to NLC graph grammars, (), 12-23 · Zbl 0765.68091 |

[20] | Gurevich, Y., Monadic second-order theories, (), 479-506 |

[21] | Habel, A., Hyperedge replacement: grammars and languages, () · Zbl 0787.68066 |

[22] | Rabin, M., A simple method for undecidability proofs and some applications, (), 58-68 |

[23] | Robertson, N.; Seymour, P., Graph minors V, excluding a planar graph, J. combin. theory ser. B, 41, 92-114, (1986) · Zbl 0598.05055 |

[24] | Seese, D., Ein unentscheidbarkeitskriterium, Wiss. Z. der humbold univ. zu Berlin math. natur. wiss., R24, 772-780, (1975) · Zbl 0331.02026 |

[25] | Seese, D., The structure of the models of decidable monadic theories of graphs, Ann. pure appl. logic, 53, 169-195, (1991) · Zbl 0733.03026 |

[26] | Tarjan, R., Depth-first search and linear graph algorithms, SIAM J. comput., 1, 146-160, (1972) · Zbl 0251.05107 |

[27] | Tarski, A.; Mostowski, A.; Robinson, R., Undecidable theories, (1953), North-Holland Amsterdam · Zbl 0053.00401 |

[28] | Thomas, W., Automata on infinite objects, (), 133-192 · Zbl 0900.68316 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.