12 found
Phokion G. Kolaitis [10]Phokion Kolaitis [5]
  1.  61
    On the decision problem for two-variable first-order logic.Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi - 1997 - 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 (8 more)  
    Export citation  
    Bookmark   33 citations  
  2.  30
    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 (...)
    Direct download (3 more)  
    Export citation  
    Bookmark   17 citations  
  3. Almost everywhere equivalence of logics in finite model theory.Lauri Hella, Phokion G. Kolaitis & Kerkko Luosto - 1996 - 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 (8 more)  
    Export citation  
    Bookmark   10 citations  
  4.  31
    On the unusual effectiveness of logic in computer science.Joseph Y. Halpern, Robert Harper, Neil Immerman, Phokion G. Kolaitis, Moshe Y. Vardi & Victor Vianu - 2001 - Bulletin of Symbolic Logic 7 (2):213-236.
    In 1960, E. P. Wigner, a joint winner of the 1963 Nobel Prize for Physics, published a paper titled On the Unreasonable Effectiveness of Mathematics in the Natural Sciences [61]. This paper can be construed as an examination and affirmation of Galileo's tenet that “The book of nature is written in the language of mathematics”. To this effect, Wigner presented a large number of examples that demonstrate the effectiveness of mathematics in accurately describing physical phenomena. Wigner viewed these examples as (...)
    Direct download (12 more)  
    Export citation  
    Bookmark   13 citations  
  5.  17
    How to define a linear order on finite models.Lauri Hella, Phokion G. Kolaitis & Kerkko Luosto - 1997 - Annals of Pure and Applied Logic 87 (3):241-267.
    We carry out a systematic investigation of the definability of linear order on classes of finite rigid structures. We obtain upper and lower bounds for the expressibility of linear order in various logics that have been studied extensively in finite model theory, such as least fixpoint logic LFP, partial fixpoint logic PFP, infinitary logic Lω∞ω with a finite number of variables, as well as the closures of these logics under implicit definitions. Moreover, we show that the upper and lower bounds (...)
    Direct download (4 more)  
    Export citation  
    Bookmark   6 citations  
  6. Association for Symbolic Logic.Jon Barwise, Howard S. Becker, Chi Tat Chong, Herbert B. Enderton, Michael Hallett, C. Ward Henson, Harold Hodes, Neil Immerman, Phokion Kolaitis & Alistair Lachlan - 1998 - Bulletin of Symbolic Logic 4 (4):465-510.
  7. University of Illinois at Chicago, Chicago, IL, June 1–4, 2003.Gregory Cherlin, Alan Dow, Yuri Gurevich, Leo Harrington, Ulrich Kohlenbach, Phokion Kolaitis, Leonid Levin, Michael Makkai, Ralph McKenzie & Don Pigozzi - 2004 - Bulletin of Symbolic Logic 10 (1).
    Export citation  
  8.  57
    Finite Model Theory and its Applications.Erich Grädel, Phokion Kolaitis, Libkin G., Marx Leonid, Spencer Maarten, Vardi Joel, Y. Moshe, Yde Venema & Scott Weinstein - 2007 - Springer.
    This book gives a comprehensive overview of central themes of finite model theory – expressive power, descriptive complexity, and zero-one laws – together with selected applications relating to database theory and artificial intelligence, especially constraint databases and constraint satisfaction problems. The final chapter provides a concise modern introduction to modal logic, emphasizing the continuity in spirit and technique with finite model theory. This underlying spirit involves the use of various fragments of and hierarchies within first-order, second-order, fixed-point, and infinitary logics (...)
    Direct download (2 more)  
    Export citation  
  9.  22
    Recursion in a quantifier vs. elementary induction.Phokion G. Kolaitis - 1979 - Journal of Symbolic Logic 44 (2):235-259.
  10.  16
    1995–1996 annual meeting of the association for symbolic logic.Tomek Bartoszynski, Harvey Friedman, Geoffrey Hellman, Bakhadyr Khoussainov, Phokion G. Kolaitis, Richard Shore, Charles Steinhorn, Mirna Dzamonja, Itay Neeman & Slawomir Solecki - 1996 - Bulletin of Symbolic Logic 2 (4):448-472.
  11.  12
    University of Sao Paulo (Sao Paulo), Brazil, July 28–31, 1998.Sergei Artemov, Sam Buss, Edmund Clarke Jr, Heinz Dieter Ebbinghaus, Hans Kamp, Phokion Kolaitis, Maarten de Rijke & Valeria de Paiva - 1999 - Bulletin of Symbolic Logic 5 (3).
    Direct download  
    Export citation  
  12.  6
    Canonical Forms and Hierarchies in Generalized Recursion Theory.Phokion G. Kolaitis - 1985 - In Anil Nerode & Richard A. Shore (eds.), Recursion Theory. American Mathematical Society. pp. 42--139.
    Direct download  
    Export citation