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

Courcelle, Bruno

Ann. Pure Appl. Logic 49, No. 3, 193-255 (1990).

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)

MSC:

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)

Keywords:

monadic second-order logic of countable graphs; equational graph

Citations:

Zbl 0722.03008; Zbl 0694.68043

References:

[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