Switch to: Citations

Add references

You must login to add references.
  1. An Application of Games to the Completeness Problem for Formalized Theories.A. Ehrenfeucht - 1967 - Journal of Symbolic Logic 32 (2):281-282.
    Download  
     
    Export citation  
     
    Bookmark   42 citations  
  • On winning Ehrenfeucht games and monadic NP.Thomas Schwentick - 1996 - Annals of Pure and Applied Logic 79 (1):61-92.
    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 (...)
    Download  
     
    Export citation  
     
    Bookmark   5 citations