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 (...)
    Download  
     
    Export citation  
     
    Bookmark   13 citations  
  • Counting Finite Models.Alan R. Woods - 1997 - Journal of Symbolic Logic 62 (3):925-949.
    Let $\varphi$ be a monadic second order sentence about a finite structure from a class $\mathscr{K}$ which is closed under disjoint unions and has components. Compton has conjectured that if the number of $n$ element structures has appropriate asymptotics, then unlabelled asymptotic probabilities $\nu $ respectively) for $\varphi$ always exist. By applying generating series methods to count finite models, and a tailor made Tauberian lemma, this conjecture is proved under a mild additional condition on the asymptotics of the number of (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Zero-one law and definability of linear order.Hannu Niemistö - 2009 - Journal of Symbolic Logic 74 (1):105-123.
    Download  
     
    Export citation  
     
    Bookmark  
  • Counting finite models.Alan R. Woods - 1997 - Journal of Symbolic Logic 62 (3):925-949.
    Let φ be a monadic second order sentence about a finite structure from a class K which is closed under disjoint unions and has components. Compton has conjectured that if the number of n element structures has appropriate asymptotics, then unlabelled (labelled) asymptotic probabilities ν(φ) (μ(φ) respectively) for φ always exist. By applying generating series methods to count finite models, and a tailor made Tauberian lemma, this conjecture is proved under a mild additional condition on the asymptotics of the number (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Zero-one laws with variable probability.Joel Spencer - 1993 - Journal of Symbolic Logic 58 (1):1-14.
    Download  
     
    Export citation  
     
    Bookmark