The monadic second-order logic of graphs. IV: Definability properties of equational graphs (Q807611): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 01:17, 5 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The monadic second-order logic of graphs. IV: Definability properties of equational graphs |
scientific article |
Statements
The monadic second-order logic of graphs. IV: Definability properties of equational graphs (English)
0 references
1990
0 references
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.
0 references
monadic second-order logic of countable graphs
0 references
equational graph
0 references
