ACM/IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Seventh Annual IEEE Symposium on

Logic in Computer Science (LICS 1992)

Paper: Zero-one laws for modal logic (at LICS 1992)

Authors: Joseph Y. Halpern Bruce M. Kapron


It is shown that a 0-1 law holds for propositional modal logic, both for structure validity and for frame validity. In the case of structure validity, the result follows easily from the well-known 0-1 law for first-order logic. However, the proof gives considerably more information. It leads to an elegant axiomatization for almost-sure structure validity, and sharper complexity bounds. Since frame validity can be reduced to a II11 formula, the 0-1 law for frame validity helps delineate when 0-1 laws exist for second-order logics


    author = 	 {Joseph Y. Halpern and Bruce M. Kapron},
    title = 	 {Zero-one laws for modal logic},
    booktitle =  {Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science (LICS 1992)},
    year =	 {1992},
    month =	 {June}, 
    pages =      {369--380},
    location =   {Santa Cruz, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}

Last modified: 2022-10-3113:49
Sam Staton