×

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.
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
PDFBibTeX XMLCite
Full Text: DOI

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, (Van Leeuwen, J., Handbook of Theoretical Computer Science, Vol. B (1990), Elsevier: Elsevier Amsterdam), 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, (Robertson, N.; Seymour, P., Graph Structure Theory. Graph Structure Theory, Contemporary Mathematics, Vol. 147 (1993), Amer. Mathematical Soc: Amer. Mathematical Soc Providence, RI), 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.; 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: Clarendon Press Oxford, U.K · Zbl 0726.05001
[17] Dirac, G., On rigid circuit graphs, (Abh. Math. Sem. Univ. Hamburg, 25 (1961)), 71-76 · Zbl 0098.14703
[18] Engelfriet, J., A characterization of context-free NCE graph languages by monadic second-order logic on trees, (Lecture Notes in Computer Science, Vol. 532 (1991), Springer: Springer Berlin), 311-327 · Zbl 0765.68090
[19] Engelfriet, J.; Rozenberg, G., Graph grammars based on node rewriting: an introduction to NLC graph grammars, (Lecture Notes in Computer Science, Vol. 532 (1991), Springer: Springer Berlin), 12-23 · Zbl 0765.68091
[20] Gurevich, Y., Monadic second-order theories, (Barwise, J.; Feferman, S., Model Theoretic Logic (1985), Springer: Springer Berlin), 479-506
[21] Habel, A., Hyperedge replacement: grammars and languages, (Lecture Notes in Computer Science, Vol. 643 (1993), Springer: Springer Berlin) · Zbl 0787.68066
[22] Rabin, M., A simple method for undecidability proofs and some applications, (Bar-Hillel, Y., Logic, Methodology and Philosophy of Science II (1965), North-Holland: North-Holland Amsterdam), 58-68 · Zbl 0192.05502
[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: North-Holland Amsterdam · Zbl 0053.00401
[28] Thomas, W., Automata on infinite objects, (Van Leeuwen, J., Handbook of Theoretical Computer Science, Vol. B (1990), Elsevier: Elsevier Amsterdam), 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.