On winning strategies in Ehrenfeucht-Fraïssé games

Sanjeev Arora, Ronald Fagin

Research output: Contribution to journalArticle

15 Scopus citations

Abstract

We present a powerful and versatile new sufficient condition for the second player (the "duplicator") to have a winning strategy in an Ehrenfeucht-Fraïssé game on graphs. We accomplish two things with this technique. First, we give a simpler and much easier-to-understand proof of Ajtai and Fagin's result that reachability in directed finite graphs is not in monadic NP. (Monadic NP, otherwise known as monadic ∑11, corresponds to existential second-order logic with the restriction that the second-order quantifiers range only over sets, and not over relations of higher arity, such as binary relations.) Second, we show that this result holds in the presence of a larger class of built-in relations than was known before.

Original languageEnglish (US)
Pages (from-to)97-121
Number of pages25
JournalTheoretical Computer Science
Volume174
Issue number1-2
DOIs
StatePublished - Mar 15 1997

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On winning strategies in Ehrenfeucht-Fraïssé games'. Together they form a unique fingerprint.

  • Cite this