The monadic second-order logic of graphs. IV: Definability properties of equational graphs (Q807611): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0168-0072(90)90027-y / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W1480506611 / rank | |||
Normal rank | |||
Latest revision as of 09:54, 30 July 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
0 references
0 references
0 references
