The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
type: Item
instance of: scholarly article
title: The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
zbMATH Open document ID: 0809.03005
DOI: 10.1016/0166-218X(94)90019-1
published in: Discrete Applied Mathematics
publication date: 1994-11-03T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03B15
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 03C85
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 681635
zbMATH Keywords: logic definability
zbMATH Keywords: representation of graphs by logical structures
zbMATH Keywords: monadic second order logic
zbMATH Keywords: expressive power
zbMATH Keywords: Hamiltonian cycle
zbMATH Keywords: quantifications over edges and sets of edges
zbMATH Keywords: minor
zbMATH Keywords: orientations
zbMATH Keywords: colorings
zbMATH Keywords: trees
zbMATH Keywords: planarity
reviewed by: Magnus Steinby
MaRDI profile type: Publication
cites work: Reachability is harder for directed than for undirected finite graphs
cites work: Easy problems for tree-decomposable graphs
cites work: Forbidden minors characterization of partial 3-trees
cites work: Graph expressions and graph rewritings
cites work: Advances in graph theory
cites work: Q3787507
cites work: Some combinatorial aspects of time-stamp systems
cites work: An axiomatic definition of context-free rewriting and its application to NLC graph grammars
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
cites work: The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
cites work: The monadic second-order logic of graphs. VII: Graphs as relational structures
cites work: Q4385531
cites work: Q4852905
cites work: Q4037313
cites work: Q3974863
cites work: Q4037316
cites work: Hypergraph languages of bounded degree
cites work: A comparison of boundary graph grammars and context-free hypergraph grammars
cites work: Q4058132
cites work: Q3666827
cites work: Q3785988
cites work: Languages that Capture Complexity Classes
cites work: Q4385543
cites work: Q4036591
cites work: Q3795250
cites work: Homomorphieeigenschaften und mittlere Kantendichte von Graphen
cites work: Decomposition of Finite Graphs Into Forests
cites work: Recursive Graphs, Recursive Labelings and Shortest Paths
cites work: Decidability of Second-Order Theories and Automata on Infinite Trees
cites work: Graph minors. IV: Tree-width and well-quasi-ordering
cites work: Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
cites work: The structure of the models of decidable monadic theories of graphs
cites work: Q4037335
cites work: Beweis einer Abschwächung der Hadwiger-Vermutung
author: Bruno Courcelle
description: scientific article; zbMATH DE number 681635