On winning Ehrenfeucht games and monadic NP

Inexpressibility results in Finite Model Theory are often proved by showing that Duplicator, one of the two players of an Ehrenfeucht game, has a winning strategy on certain structures. In this article a new method is introduced that allows, under certain conditions, the extension of a winning strat...

Full description

Saved in:
Bibliographic Details
Published in:Annals of pure and applied logic 1996-05, Vol.79 (1), p.61-92
Main Author: Schwentick, Thomas
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Inexpressibility results in Finite Model Theory are often proved by showing that Duplicator, one of the two players of an Ehrenfeucht game, has a winning strategy on certain structures. In this article a new method is introduced that allows, under certain conditions, the extension of a winning strategy of Duplicator on some small parts of two finite structures to a global winning strategy. As applications of this technique it is shown that • — Graph Connectivity is not expressible in existential monadic second-order logic (MonNP), even in the presence of a built-in linear order, • — Graph Connectivity is not expressible in MonNP even in the presence of arbitrary built-in relations of degree n 0(1), and • — the presence of a built-in linear order gives MonNP more expressive power than the presence of a built-in successor relation.
ISSN:0168-0072
DOI:10.1016/0168-0072(95)00030-5