Switch to: References

Add citations

You must login to add citations.
  1. A uniform method for proving lower bounds on the computational complexity of logical theories.Kevin J. Compton & C. Ward Henson - 1990 - Annals of Pure and Applied Logic 48 (1):1.
    A new method for obtaining lower bounds on the computational complexity of logical theories is presented. It extends widely used techniques for proving the undecidability of theories by interpreting models of a theory already known to be undecidable. New inseparability results related to the well known inseparability result of Trakhtenbrot and Vaught are the foundation of the method. Their use yields hereditary lower bounds . By means of interpretations lower bounds can be transferred from one theory to another. Complicated machine (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   13 citations  
  • Elimination of unbounded quantifiers for some poly-regular groups of infinite rank.Philip Scowcroft - 2007 - Annals of Pure and Applied Logic 149 (1-3):40-80.
    This paper extends theorems of Belegradek about poly-regular groups of finite rank to certain poly-regular groups of infinite rank. A model-theoretic property aiding these investigations is the elimination of unbounded quantifiers, and the paper establishes both a general model-theoretic test for this property and results about bounded quantifiers in the special context of ordered Abelian groups.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • The Complexity of Bounded Quantifiers in Some Ordered Abelian Groups.Philip Scowcroft - 2007 - Notre Dame Journal of Formal Logic 48 (4):521-550.
    This paper obtains lower and upper bounds for the number of alternations of bounded quantifiers needed to express all formulas in certain ordered Abelian groups admitting elimination of unbounded quantifiers. The paper also establishes model-theoretic tests for equivalence to a formula with a given number of alternations of bounded quantifiers.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
    		•
  • Decidable fragments of first-order temporal logics.Ian Hodkinson, Frank Wolter & Michael Zakharyaschev - 2000 - Annals of Pure and Applied Logic 106 (1-3):85-134.
    In this paper, we introduce a new fragment of the first-order temporal language, called the monodic fragment, in which all formulas beginning with a temporal operator have at most one free variable. We show that the satisfiability problem for monodic formulas in various linear time structures can be reduced to the satisfiability problem for a certain fragment of classical first-order logic. This reduction is then used to single out a number of decidable fragments of first-order temporal logics and of two-sorted (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   25 citations  
  • Expanded theory of ordered Abelian groups.Yuri Gurevich - 1977 - Annals of Mathematical Logic 12 (2):193-228.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  • Périodicité des théories élémentaires des corps de séries formelles itérées.Françoise Delon - 1986 - Journal of Symbolic Logic 51 (2):334-351.
    C. U. Jensen suggested the following construction, starting from a fieldK:and asked when two fieldsKαandKβare equivalent. We give a complete answer in the case of a fieldKof characteristic 0.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
    		•
  • Beyond tense logic. [REVIEW]John P. Burgess - 1984 - Journal of Philosophical Logic 13 (3):235-248.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation