The monadic second order logic of graphs. VI: On several representations of graphs by relational structures. (English) Zbl 0809.03005

Courcelle, Bruno

Discrete Appl. Math. 54, No. 2-3, 117-149 (1994).

The paper continues the author’s extensive study of graph properties expressible by formulas of monadic second order logic (MSOL). [For the previous five parts, cf. Zbl 0722.03008, Zbl 0694.68043, Zbl 0754.03006, Zbl 0731.03006, Zbl 0754.68065, respectively. Part VII is reviewed below.] The special interest in MSLO in this context is due to the fact that, while it is strong enough for expressing many important properties of graphs, it still has useful decidability properties; in particular, graph properties expressible in MSOL are decidable within sets generated by context-free graph grammars. In the usual representation of a graph as a logical structure, the domain consists of the vertices of the graph. The author notes that there are also alternative representations, and a central theme of this paper is the effect of the representation on the expressive power of MSOL. In particular, one may include also the edges in the domain and allow quantifications over them. It turns out that some new properties, like the existence of a Hamiltonian cycle, can be expressed by means of quantifications over edges and sets of edges. On the other hand, for any fixed \(k\), within the class of graphs of degree at most \(k\), edge quantifications do not increase the expressive power of MSOL. The same holds for the classes consisting of graphs which do not contain a given graph as a minor. Similar conclusions are arrived at for these classes with respect to the effect of allowing the use of orientations of edges. All graphs considered here are simple and loop- free. The paper contains also many other results concerning colorings, trees and planarity.

Reviewer: M.Steinby (Turku)

MSC:

03B15	Higher-order logic; type theory (MSC2010)
05C20	Directed graphs (digraphs), tournaments
03C85	Second- and higher-order model theory
68R10	Graph theory (including graph drawing) in computer science
05C15	Coloring of graphs and hypergraphs
05C10	Planar graphs; geometric and topological aspects of graph theory
05C05	Trees

Keywords:

logic definability; representation of graphs by logical structures; monadic second order logic; expressive power; Hamiltonian cycle; quantifications over edges and sets of edges; minor; orientations; colorings; trees; planarity

Citations:

Zbl 0722.03008; Zbl 0694.68043; Zbl 0754.03006; Zbl 0731.03006; Zbl 0754.68065

References:

[1]	Ajtai, M.; Fagin, R., Reachability is harder for directed than for undirected finite graphs, J. Symbolic Logic, 55, 113-150 (1990) · Zbl 0708.03016
[2]	Arnborg, S.; Lagergren, J.; Seese, D., Easy problems easy for tree-decomposable graphs, J. Algorithms, 12, 308-340 (1991) · Zbl 0734.68073
[3]	Arnborg, S.; Proskurowski, A.; Corneil, D., Forbidden minors characterization of partial 3-trees, Discrete Math., 80, 1-19 (1990) · Zbl 0701.05016
[4]	Bauderon, M.; Courcelle, B., Graph expressions and graphs rewritings, Math. Systems Theory, 20, 83-127 (1987) · Zbl 0641.68115
[5]	Bollobas, B., External Graph Theory (1978), Academic Press: Academic Press New York · Zbl 0367.00008
[6]	Brandenburg, F.-J., On polynomial time graph grammars, (Proceedings STACS’88, 294 (1988), Springer: Springer Berlin), 227-236, Lecture Notes in Computer Science
[8]	Courcelle, B., An axiomatic definition of context-free rewriting and its application to NLC graph grammars, Theoret. Comput. Sci., 55, 141-181 (1987) · Zbl 0644.68095
[9]	Courcelle, B., The monadic second-order logic of graphs I: Recognizable sets of finite graphs, Inform. and Comput., 85, 12-75 (1990) · Zbl 0722.03008
[10]	Courcelle, B., The monadic second-order logic of graphs III: Tree-decompositions, minors, and complexity issues, Informatique Théorique et Applications, 26, 257-286 (1992) · Zbl 0754.03006
[11]	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
[12]	Courcelle, B., The monadic second-order logic of graphs VII: Graphs as relational structures, Theoret. Comput. Sci., 101, 3-33 (1992) · Zbl 0809.03006
[13]	Courcelle, B., The monadic second-order logic of graphs VIII: Orientations, Research Report 92-69 (1992)
[14]	Courcelle, B., Monadic second-order definable graph transductions, (Proceedings of CAAP’92, 581 (1992), Springer: Springer Berlin), 124-144, Lecture Notes in Computer Science
[15]	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
[16]	Courcelle, B.; Engelfriet, J., A logical characterization of hypergraph languages defined by hyperedge replacement grammars, Research Report 91-44 (1991) · Zbl 0830.68098
[17]	Courcelle, B.; Engelfriet, J.; Rozenberg, G., Handle-rewriting hypergraph grammars, (J. Comput. System Sci., 532 (1991), Springer: Springer Berlin), 253-268, Lecture Notes in Computer Science · Zbl 0765.68084
[18]	Engelfriet, J., Context-free NCE graph grammars, (Proceedings of FCT’89, 380 (1989), Springer: Springer Berlin), 148-161, Lecture in Computer Science · Zbl 0756.68070
[19]	Engelfriet, J., A characterization of context-free NCE graph languages by monadic second-order logic on trees, (Lecture in Computer Science, 532 (1991), Springer: Springer Berlin), 253-268 · Zbl 0765.68090
[21]	Engelfriet, J.; Rozenberg, G., A comparison of boundary graph grammars and context-free hypergraph grammars, Inform. and Comput., 84, 163-206 (1990) · Zbl 0706.68067
[22]	Fagin, R., Generalized first-order spectra and polynomial time recognizable sets, (Karp, R., Complexity of Computation, SIAM-AMS Proceedings, 7 (1974)), 43-73
[23]	Gaifman, H., Local and non-local properties, (Stern, J., Logic Colloquium (Herbrand Symposium) (1981), North-Holland: North-Holland Amsterdam), 105-135
[24]	Habel, A.; Kreowski, H. J., May we introduce to you: hyperedge replacement, (Lecture Notes in Computer Science, 291 (1987), Springer: Springer Berlin), 15-26 · Zbl 0643.68106
[25]	Immerman, N., Languages that capture complexity classes, SIAM J. Comput., 16, 760-777 (1987) · Zbl 0634.68034
[26]	Israeli, A.; Li, M., Bounded time-stamps, Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, 371-382 (1987)
[27]	Kannellakis, P., Elements of relational data base theory, Theoret. Comput. Sci., 101, 1073-1156 (1992)
[28]	Lagergren, J.; Arnborg, S., Finding minimal forbidden minors using a finite congruence, (Proceedings of the 18th ICALP, 510 (1991), Springer: Springer Berlin), 532-543, Lecture Notes in Computer Science · Zbl 0764.68122
[29]	Lautemann, C., Efficient algorithms on context-free graph languages, (Lecture Notes in Computer Science, 317 (1988), Springer: Springer Berlin), 362-378
[30]	Mader, W., Homomorphieeigenschaften und mittlere Kanten-dichte von Graphen, Math. Ann., 174, 265-268 (1967) · Zbl 0171.22405
[31]	Nash-Williams, C., Decomposition of finite graphs into forests, J. London Math. Soc., 39, 12 (1964) · Zbl 0119.38805
[32]	Proskurowski, A., Recursive graphs, recursive labellings and shortest paths, SIAM J. Comput., 10, 391-397 (1981) · Zbl 0471.05055
[33]	Rabin, M., Decidability of second-order theories and automata on infinite trees, Trans. Amer. Math. Soc., 141, 1-35 (1969) · Zbl 0221.02031
[34]	Rabin, M., Decidable theories, (Barwise, J., Handbook of Mathematical Logic (1977), North Holland: North Holland Amsterdam), 595-629
[35]	Raspaud, A., Good and semistrong colorings of oriented planar graphs (1991)
[36]	Robertson, N.; Seymour, P., Graph minors IV: tree width and well-quasi-ordering, J. Combin. Theory Ser. B., 48, 227-254 (1990) · Zbl 0719.05032
[37]	Rozenberg, G.; Welzl, E., Boundary NLC grammars, Basic definitions normal forms and complexity, Inform. and Control, 69, 136-167 (1986) · Zbl 0608.68060
[38]	Seese, D., The structure of the models of decidable monadic theories of graphs, Ann. Pure Appl. Logic, 53 (1991) · Zbl 0733.03026
[39]	Vogler, W., Recognizing edge replacement graph languages in cubic time, (Lecture Notes in Computer Science, 532 (1991), Springer: Springer Berlin), 676-687 · Zbl 0769.68078
[40]	Wagner, K., Beweis einer Abschwachung der Hadwiger-Vermutung, Math. Ann., 153, 139-141 (1964) · Zbl 0192.30002
[41]	Zielonka, W., Time-stamp systems for a fixed set of agents (1990), unpublished