On winning Ehrenfeucht games and monadic NP (Q1919539): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 07:17, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On winning Ehrenfeucht games and monadic NP |
scientific article |
Statements
On winning Ehrenfeucht games and monadic NP (English)
0 references
24 February 1997
0 references
For a given property of structures, in model theory, and in particular in finite model theory, its inexpressibility in first-order logic (or fragments of second-order logic) is often proved by means of Ehrenfeucht-Fraïssé games. The main theorem of the present paper states sufficient conditions that ensure that a winning strategy (in these games) for small parts of structures can be extended to a global strategy; one of these conditions says that the substructures induced on the points far distant from the distinguished small subsets are isomorphic. Among others the theorem is applied to show that the connectivity of ordered graphs is not expressible in monadic \(\Sigma^1_1\).
0 references
inexpressibility in first-order logic
0 references
fragments of second-order logic
0 references
Ehrenfeucht-Fraïssé games
0 references
winning strategy
0 references
global strategy
0 references
connectivity of ordered graphs
0 references