Logic in Computer Science (LICS 1991)

Paper: On the 0-1 law for the class of existential second order minimal Godel sentences with equality (at LICS 1991)

Authors: Leszek Pacholski WiesławSzwast

Abstract

It is proved that the 0-1 law does not hold for the class of existential second sentences whose first order part is in the minimal Godel class, i.e. has the quantifier prenex consisting of two universal quantifiers followed by just one existential quantifier. This completes the classification of existential second order sentences for which the 0-1 law holds. It is also proved that asymptotic probabilities of sentences as above form a dense subset of the unit interval

BibTeX

  @InProceedings{PacholskiSzwast-Onthe01lawforthecla,
    author = 	 {Leszek Pacholski and WiesławSzwast},
    title = 	 {On the 0-1 law for the class of existential second order minimal Godel sentences with equality },
    booktitle =  {Proceedings of the Sixth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1991},
    year =	 1991,
    editor =	 {Giles Kahn},
    month =	 {July}, 
    pages =      {280--285},
    location =   {Amsterdam, The Netherlands}, 
    publisher =	 {IEEE Computer Society Press}
  }