The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs

The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs

1990 | BRUNO COURCELLE
The paper introduces the concept of recognizable sets of finite graphs, which are sets of graphs definable in monadic second-order logic (MSOL). It is shown that every set of finite graphs definable in MSOL is recognizable, but not vice versa. The monadic second-order theory of a context-free set of graphs is decidable. The paper also extends the results of Doner to show that a set of unordered unbounded trees is recognizable if and only if it is definable in a counting version of MSOL. The paper discusses algebraic structures on graphs, including recognizable sets, equational sets, and their properties. It also introduces graph operations and graph expressions, and shows that the set of graphs forms a many-sorted magma. The paper concludes with a discussion of the decidability of certain properties of graphs and trees, and the relationship between different logical systems.The paper introduces the concept of recognizable sets of finite graphs, which are sets of graphs definable in monadic second-order logic (MSOL). It is shown that every set of finite graphs definable in MSOL is recognizable, but not vice versa. The monadic second-order theory of a context-free set of graphs is decidable. The paper also extends the results of Doner to show that a set of unordered unbounded trees is recognizable if and only if it is definable in a counting version of MSOL. The paper discusses algebraic structures on graphs, including recognizable sets, equational sets, and their properties. It also introduces graph operations and graph expressions, and shows that the set of graphs forms a many-sorted magma. The paper concludes with a discussion of the decidability of certain properties of graphs and trees, and the relationship between different logical systems.
Reach us at info@study.space