14 found
Order:
  1.  40
    Modal characterisation theorems over special classes of frames.Anuj Dawar & Martin Otto - 2010 - Annals of Pure and Applied Logic 161 (1):1-42.
    We investigate model theoretic characterisations of the expressive power of modal logics in terms of bisimulation invariance. The paradigmatic result of this kind is van Benthem’s theorem, which says that a first-order formula is invariant under bisimulation if, and only if, it is equivalent to a formula of basic modal logic. The present investigation primarily concerns ramifications for specific classes of structures. We study in particular model classes defined through conditions on the underlying frames, with a focus on frame classes (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   17 citations  
  2.  55
    Fixed point logics.Anuj Dawar & Yuri Gurevich - 2002 - Bulletin of Symbolic Logic 8 (1):65-88.
    We consider fixed point logics, i.e., extensions of first order predicate logic with operators defining fixed points. A number of such operators, generalizing inductive definitions, have been studied in the context of finite model theory, including nondeterministic and alternating operators. We review results established in finite model theory, and also consider the expressive power of the resulting logics on infinite structures. In particular, we establish the relationship between inflationary and nondeterministic fixed point logics and second order logic, and we consider (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  3.  24
    Descriptive complexity of graph spectra.Anuj Dawar, Simone Severini & Octavio Zapata - 2019 - Annals of Pure and Applied Logic 170 (9):993-1007.
  4.  29
    Choiceless polynomial time, counting and the Cai–Fürer–Immerman graphs.Anuj Dawar, David Richerby & Benjamin Rossman - 2008 - Annals of Pure and Applied Logic 152 (1):31-50.
    We consider Choiceless Polynomial Time , a language introduced by Blass, Gurevich and Shelah, and show that it can express a query originally constructed by Cai, Fürer and Immerman to separate fixed-point logic with counting from image. This settles a question posed by Blass et al. The program we present uses sets of unbounded finite rank: we demonstrate that this is necessary by showing that the query cannot be computed by any program that has a constant bound on the rank (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  5.  51
    Decidable Fragments of the Simple Theory of Types with Infinity and $mathrm{NF}$.Anuj Dawar, Thomas Forster & Zachiri McKenzie - 2017 - Notre Dame Journal of Formal Logic 58 (3):433-451.
    We identify complete fragments of the simple theory of types with infinity and Quine’s new foundations set theory. We show that TSTI decides every sentence ϕ in the language of type theory that is in one of the following forms: ϕ=∀x1r1⋯∀xkrk∃y1s1⋯∃ylslθ where the superscripts denote the types of the variables, s1>⋯>sl, and θ is quantifier-free, ϕ=∀x1r1⋯∀xkrk∃y1s⋯∃ylsθ where the superscripts denote the types of the variables and θ is quantifier-free. This shows that NF decides every stratified sentence ϕ in the language (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  6.  47
    Elementary Properties of the Finite Ranks.Anuj Dawar, Kees Doets, Steven Lindell & Scott Weinstein - 1998 - Mathematical Logic Quarterly 44 (3):349-353.
    This note investigates the class of finite initial segments of the cumulative hierarchy of pure sets. We show that this class is first-order definable over the class of finite directed graphs and that this class admits a first-order definable global linear order. We apply this last result to show that FO = FO.
    Direct download  
     
    Export citation  
     
    Bookmark   2 citations  
  7.  29
    Turing Centenary Conference: How the World Computes.S. Barry Cooper, Anuj Dawar, Martin Hyland & Benedikt Löwe - 2014 - Annals of Pure and Applied Logic 165 (9):1353-1354.
  8.  18
    Edinburgh, Scotland July 1–4, 2008.Olivier Danvy, Anuj Dawar, Makoto Kanazawa, Sam Lomonaco, Mark Steedman, Henry Towsner & Nikolay Vereshchagin - 2008 - Bulletin of Symbolic Logic 14 (4).
  9.  59
    Capturing Relativized Complexity Classes without Order.Anuj Dawar, Georg Gottlob & Lauri Hella - 1998 - Mathematical Logic Quarterly 44 (1):109-122.
    We consider the problem of obtaining logical characterisations of oracle complexity classes. In particular, we consider the complexity classes LOGSPACENP and PTIMENP. For these classes, characterisations are known in terms of NP computable Lindström quantifiers which hold on ordered structures. We show that these characterisations are unlikely to extend to arbitrary structures, since this would imply the collapse of certain exponential complexity hierarchies. We also observe, however, that PTIMENP can be characterised in terms of Lindström quantifers , though it remains (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  10.  42
    Vassar college, 124 Raymond avenue, poughkeepsie, ny 12604, usa. In a review, a reference “jsl xliii 148,” for example, refers either to the publication reviewed on page 148 of volume 43 of the journal, or to the review itself (which contains full bibliographical information for the reviewed publication). Analogously, a reference “bsl VII 376” refers to the review beginning on page 376 in volume 7 of this bulletin, or. [REVIEW]John Baldwin, Lev Beklemishev, Anuj Dawar, Mirna Dzamonja, David Evans, Erich Grädel, Denis Hirschfeldt, Hannes Leitgeb, Roger Maddux & Grigori Mints - 2008 - Bulletin of Symbolic Logic 14 (1).
    Direct download  
     
    Export citation  
     
    Bookmark  
  11.  21
    College, 124 Raymond avenue, poughkeepsie, ny 12604, usa. In a review, a reference “jsl xliii 148,” for example, refers either to the publication reviewed on page 148 of volume 43 of the journal, or to the review itself (which contains full bibliographical information for the reviewed publication). Analogously, a reference “bsl VII 376” refers to the review beginning on page 376 in volume 7 of this bulletin, or. [REVIEW]Mark Colyvan Burgess, Anuj Dawar, Marcelo Fiore, Noam Greenberg, Hannes Leitgeb, Ernest Schimmerling, Carsten Schürmann & Kai Wehmeier - 2010 - Bulletin of Symbolic Logic 16 (3).
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  12.  18
    The Association for Symbolic Logic publishes analytical reviews of selected books and articles in the field of symbolic logic. The reviews were published in The Journal of Symbolic Logic from the founding of the Journal in 1936 until the end of 1999. The Association moved the reviews to this Bulletin, beginning in 2000. The Reviews Section is edited by Steve Awodey (Managing Editor), John Baldwin, John. [REVIEW]Mark Colyvan Burgess, Anuj Dawar, Marcelo Fiore, Noam Greenberg & Hannes Leitgeb - 2010 - Bulletin of Symbolic Logic 16 (1).
  13.  37
    Vassar college, 124 Raymond avenue, poughkeepsie, ny 12604, usa. In a review, a reference “jsl xliii 148,” for example, refers either to the publication reviewed on page 148 of volume 43 of the journal, or to the review itself (which contains full bibliographical information for the reviewed publication). Analogously, a reference “bsl VII 376” refers to the review beginning on page 376 in volume 7 of this bulletin, or. [REVIEW]Mark Colyvan Burgess, Anuj Dawar, Mirna Dzamonja, Marcelo Fiore & Hannes Leitgeb - 2009 - Bulletin of Symbolic Logic 15 (4).
    Direct download  
     
    Export citation  
     
    Bookmark  
  14.  27
    (1 other version)Martin Otto. The expressive power of fixed-point logic with counting. The journal of symbolic logic, vol. 61 , pp. 147–176. - Martin Otto. Bounded variable logics and counting. A study infinite models. Lecture notes in logic, no. 9. Springer, Berlin, Heidelberg, New York, etc., 1997, ix + 183 pp. [REVIEW]Anuj Dawar - 1998 - Journal of Symbolic Logic 63 (1):329-331.