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

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.
Reviewer: Li Xiang (Guiyang)


03B25 Decidability of theories and sets of sentences
68R10 Graph theory (including graph drawing) in computer science
03C85 Second- and higher-order model theory
03B15 Higher-order logic; type theory (MSC2010)
Full Text: DOI


[1] Adamek, J.; Koubek, V., Least fixed point of a functor, J. comput. system sci., 19, 163-178, (1979) · Zbl 0423.18007
[2] Bauderon, M., On systems of equations defining infinite graphs, (), 54-73
[3] M. Bauderon, Infinite hypergraphs, Theoret. Comput. Sci., to appear. · Zbl 0758.05069
[4] Bauderon, M.; Courcelle, B., Graph expressions and graph rewritings, Math. systems theory, 20, 83-127, (1987) · Zbl 0641.68115
[5] Büchi, J.R., Weak second-order logic and finite automata, Z. math. logik frundlag. math., 5, 66-92, (1960) · Zbl 0103.24705
[6] Courcelle, B., An axiomatic approach to the korenjak-hopcroft algorithms, Math. systems theory, 16, 191-231, (1983) · Zbl 0581.68032
[7] Courcelle, B., Fundamental properties of infinite trees, Theoret. comput. sci., 25, 95-169, (1983) · Zbl 0521.68013
[8] Courcelle, B., Equivalences and transformations of regular systems. applications to recursive program schemes and grammers, Theoret. comput. sci., 42, 1-122, (1986) · Zbl 0636.68104
[9] Courelle, B., An axiomatic definition of context-free rewriting and its application to NLC graph grammers, Theoret. comput. sci., 55, 141-181, (1987) · Zbl 0644.68095
[10] Courcelle, B., The monadic second-order logic of graphs I: recognizable sets of finite graphs, Information and computation, 85, 12-75, (1990) · Zbl 0722.03008
[11] Courcelle, B., The monadic second-order logic of graphs II: infinite graphs of bounded width, Math. systems theory, 21, 187-221, (1989) · Zbl 0694.68043
[12] Courcelle, B., The monadic second-order logic of graphs III: tree-width, forbidden minors, and complexity issues, Report 88-52, (1988), submitted
[13] B. Courcelle, The monadic second-order logic of graphs V: On closing the gap between definability and recognizability, Theoret. Comput. Sci, to appear. · Zbl 0754.68065
[14] Courcelle, B., The monadic second-order logic of graphs: definable sets of finite graphs, (), 30-53
[15] Courcelle, B., Graph rewriting: an algebraic and logic approach, (), Ch. 5 · Zbl 0900.68282
[16] Gurevich, Y., Monadic second-order theories, (), 479-506
[17] Gurevich, Y.; Harrington, L., Trees, automatas and games, Proc. of symp. on theory of comput., 60-65, (1982), San Francisco
[18] Rabin, M., Decidability of second-order theories and automata on infinite trees, Trans. amer. math. soc., 141, 1-35, (1969) · Zbl 0221.02031
[19] Rabin, M., Weakly definable relations and special automata, (), 1-23 · Zbl 0214.02208
[20] Rabin, M., Automata on infinite objects and Church’s problem, A.M.S. regional conf. series in math., 13, (1972) · Zbl 0315.02037
[21] Robertson, N.; Seymour, P., Some new results on the well-quasi ordering of graphs, (), 343-354
[22] Shelah, S., The monadic theory of order, Ann. of math., 102, 379-419, (1975) · Zbl 0345.02034
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.