Switch to: Citations

Add references

You must login to add references.
  1. 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  
  • Generalized quantifiers and pebble games on finite structures.Phokion G. Kolaitis & Jouko A. Väänänen - 1995 - Annals of Pure and Applied Logic 74 (1):23-75.
    First-order logic is known to have a severely limited expressive power on finite structures. As a result, several different extensions have been investigated, including fragments of second-order logic, fixpoint logic, and the infinitary logic L∞ωω in which every formula has only a finite number of variables. In this paper, we study generalized quantifiers in the realm of finite structures and combine them with the infinitary logic L∞ωω to obtain the logics L∞ωω, where Q = {Qi: iε I} is a family (...)
    Download  
     
    Export citation  
     
    Bookmark   21 citations  
  • (1 other version)Finite Model Theory.Heinz-Dieter Ebbinghaus & Jörg Flum - 2001 - Studia Logica 69 (3):449-449.
    Download  
     
    Export citation  
     
    Bookmark   48 citations