Switch to: Citations

Add references

You must login to add references.
  1. Expressive equivalence of least and inflationary fixed-point logic.Stephan Kreutzer - 2004 - Annals of Pure and Applied Logic 130 (1-3):61-78.
    We study the relationship between least and inflationary fixed-point logic. In 1986, Gurevich and Shelah proved that in the restriction to finite structures, the two logics have the same expressive power. On infinite structures however, the question whether there is a formula in IFP not equivalent to any LFP-formula was left open.In this paper, we answer the question negatively, i.e. we show that the two logics are equally expressive on arbitrary structures. We give a syntactic translation of IFP-formulae to LFP-formulae (...)
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • Fixed-point extensions of first-order logic.Yuri Gurevich & Saharon Shelah - 1986 - Annals of Pure and Applied Logic 32:265-280.
    Download  
     
    Export citation  
     
    Bookmark   21 citations  
  • [Omnibus Review].Yiannis N. Moschovakis - 1968 - Journal of Symbolic Logic 33 (3):471-472.
    Download  
     
    Export citation  
     
    Bookmark   55 citations  
  • 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 (...)
    Download  
     
    Export citation  
     
    Bookmark   5 citations