|
Abstract : |
We present a powerful and versatile new sufficient condition for the second player (the "duplicator") to have a winning strategy in an Ehrenfeucht-Fraiss'e game on graphs. We accomplish two things with this technique. First, we give a simpler and much easier-tounderstand proof of Ajtai and Fagin's result that reachability in directed finite graphs is not in monadic NP. (Monadic NP, otherwise known as monadic \Sigma 1 1, 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., |
