8 found
Sort by:
  1. Joseph Y. Halpern, Robert Harper, Neil Immerman, Phokion G. Kolaitis, Moshe Y. Vardi & Victor Vianu (2001). On the Unusual Effectiveness of Logic in Computer Science. Bulletin of Symbolic Logic 7 (2):213-236.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  2. Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi (1997). On the Decision Problem for Two-Variable First-Order Logic. Bulletin of Symbolic Logic 3 (1):53-69.
    We identify the computational complexity of the satisfiability problem for FO 2 , the fragment of first-order logic consisting of all relational first-order sentences with at most two distinct variables. Although this fragment was shown to be decidable a long time ago, the computational complexity of its decision problem has not been pinpointed so far. In 1975 Mortimer proved that FO 2 has the finite-model property, which means that if an FO 2 -sentence is satisfiable, then it has a finite (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  3. Lauri Hella, Phokion G. Kolaitis & Kerkko Luosto (1997). How to Define a Linear Order on Finite Models. Annals of Pure and Applied Logic 87 (3):241-267.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  4. Tomek Bartoszynski, Harvey Friedman, Geoffrey Hellman, Bakhadyr Khoussainov, Phokion G. Kolaitis, Richard Shore, Charles Steinhorn, Mirna Dzamonja, Itay Neeman & Slawomir Solecki (1996). 1995–1996 Annual Meeting of the Association for Symbolic Logic. Bulletin of Symbolic Logic 2 (4).
    Direct download  
     
    My bibliography  
     
    Export citation  
  5. Lauri Hella, Phokion G. Kolaitis & Kerkko Luosto (1996). Almost Everywhere Equivalence of Logics in Finite Model Theory. Bulletin of Symbolic Logic 2 (4):422-443.
    We introduce a new framework for classifying logics on finite structures and studying their expressive power. This framework is based on the concept of almost everywhere equivalence of logics, that is to say, two logics having the same expressive power on a class of asymptotic measure 1. More precisely, if L, L ′ are two logics and μ is an asymptotic measure on finite structures, then $\scr{L}\equiv _{\text{a.e.}}\scr{L}^{\prime}(\mu)$ means that there is a class C of finite structures with μ (C)=1 (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  6. Phokion G. Kolaitis & Jouko A. Väänänen (1995). Generalized Quantifiers and Pebble Games on Finite Structures. Annals of Pure and Applied Logic 74 (1):23-75.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  7. Phokion G. Kolaitis (1985). Canonical Forms and Hierarchies in Generalized Recursion Theory. In Anil Nerode & Richard A. Shore (eds.), Recursion Theory. American Mathematical Society. 42--139.
    No categories
    Direct download  
     
    My bibliography  
     
    Export citation  
  8. Phokion G. Kolaitis (1979). Recursion in a Quantifier Vs. Elementary Induction. Journal of Symbolic Logic 44 (2):235-259.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation