The monadic second-order logic of graphs. IV: Definability properties of equational graphs (Q807611)

This paper continues the author's study of the monadic second-order logic of countable graphs [see Inf. Comput. 85, No.1, 12-75 (1990; Zbl 0722.03008); Math. Syst. Theory 21, No.4, 187-221 (1989; Zbl 0694.68043)]. It is shown that every equational graph can be characterized, up to isomorphism, by a formula of monadic second-order logic. It follows that the isomorphism of two equational graphs is decidable. The author also establishes that a graph specified in an equational graph by monadic second-order formulas is equational.