A regular characterization of graph languages definable in monadic second-order logic (Q1177179): 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 23:34, 4 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A regular characterization of graph languages definable in monadic second-order logic |
scientific article |
Statements
A regular characterization of graph languages definable in monadic second-order logic (English)
0 references
26 June 1992
0 references
The author shows that the class of graph languages definable by monadic second-order logic, can be characterized as the smallest class containing certain elementary graph languages, and closed under the boolean operations (union, intersection, and complement) and under relabeling. Similar characterization is given to classes of graph languages restricted by some label-independent properties. Some examples are discussed.
0 references
graph languages
0 references
monadic second-order logic
0 references
