Logic in Computer Science (LICS 1995)

Paper: Generalized Quantifiers and 0-1 Laws (at LICS 1995)

Authors: Anuj Dawar Erich Grädel

Abstract

We study 0-1 laws for extensions of first-order logic by Lindstrom quantifiers. We state sufficient conditions on a quantifier Q expressing a graph property, for the logic FO[Q] - the extension of first-order logic by means of the quantifier Q - to have a 0-1 law. We use these conditions to show, in particular, that FO[Rig], where Rig is the quantifier expressing rigidity, has a 0-1 law. We also show that FO[Ham], where Ham is the quantifier expressing Hamiltonicity, does not have a 0-1 law. Blass and Harary pose the question whether there is a logic which is powerful enough to express Hamiltonicity or rigidity and which has a 0-1 law. It is a consequence of our results that there is no such regular logic (in the sense of abstract model theory) in the case of Hamiltonicity, but there is one in the case of rigidity. We also consider sequences of vectorized quantifiers, and show that the extensions of first-order logic obtained by adding such sequences generated by quantifiers that are closed under substructures have 0-1 laws.

BibTeX

  @InProceedings{DawarGrdel-GeneralizedQuantifi,
    author = 	 {Anuj Dawar and Erich Grädel},
    title = 	 {Generalized Quantifiers and 0-1 Laws},
    booktitle =  {Proceedings of the Tenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1995},
    year =	 1995,
    editor =	 {Dexter Kozen},
    month =	 {June}, 
    pages =      {54-64},
    location =   {San Diego, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }