zbMATH — the first resource for mathematics

The monadic second order logic of graphs. VI: On several representations of graphs by relational structures. (English) Zbl 0809.03005
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)

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
Full Text: DOI
[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 New York · Zbl 0367.00008
[6] Brandenburg, F.-J., On polynomial time graph grammars, (), 227-236, Lecture Notes in Computer Science
[7] R. Cori and E. Sopena, Some combinatorial aspects of time-stamp systems, European J. Combin., to appear. · Zbl 0771.05043
[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, (), 124-144, Lecture Notes in Computer Science
[15] Courcelle, B., Graph rewriting: an algebraic and logic approach, (), 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)
[17] Courcelle, B.; Engelfriet, J.; Rozenberg, G., Handle-rewriting hypergraph grammars, (), 253-268, Lecture Notes in Computer Science · Zbl 0765.68084
[18] Engelfriet, J., Context-free NCE graph grammars, (), 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, (), 253-268
[20] J. Engelfriet and L. Heyker, Context-free hypergraph languages of bounded degree, in preparation. · Zbl 0802.68073
[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, (), 43-73
[23] Gaifman, H., Local and non-local properties, (), 105-135
[24] Habel, A.; Kreowski, H.J., May we introduce to you: hyperedge replacement, (), 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, (), 532-543, Lecture Notes in Computer Science · Zbl 0764.68122
[29] Lautemann, C., Efficient algorithms on context-free graph languages, (), 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, (), 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, (), 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
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.