No label defined (Q4353558)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1059243
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1059243 |
Statements
23 March 1998
0 references
descriptional complexity
0 references
graph properties
0 references
fragments of monadic second-order logic
0 references
expressive power
0 references
forbidden configurations
0 references
0.8392714858055115
0 references
0.8347001075744629
0 references
0.8012480139732361
0 references
0.7986918091773987
0 references
Monadic second-order logic is powerful enough for expressing many nonelementary properties of graphs, such as connectivity or planarity, for example, but still it is algorithmically tractable. In this paper, the author surveys the descriptional complexity of some graph properties in terms of various fragments of monadic second-order logic. Special attention is paid to the question whether a property and its negation are expressible in the same fragments. It is also shown that in some cases quantifications over sets of edges increase the expressive power while in others they can be eliminated. Furthermore, it is shown that some properties have negative definitions in terms of forbidden configurations which are simpler than any positive definitions. Finally, some related topics are dicussed and several conjectures are presented. For the entire collection see [Zbl 0865.00055].
0 references
