ACM/IEEE Symposium on Logic in Computer Science

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

Fifth Annual IEEE Symposium on

Logic in Computer Science (LICS 1990)

Paper: 0-1 laws for infinitary logics (at LICS 1990)

Authors: Phokion G. Kolaitis Moshe Y. Vardi


Asymptotic probabilities of properties expressible in a certain infinitary logic on finite structures are investigated. Sentences in this logic may have arbitrary disjunctions and conjunctions, but they involve only a finite number of distinct variables. It is shown that zero-one law holds for the infinitary logic considered, i.e. the asymptotic probability of every sentence in this logic exists and is equal to either zero or one. This result subsumes earlier work on asymptotic probabilities for various fixpoint logics and reveals the boundary of zero-one laws for infinitary logics


    author = 	 {Phokion G. Kolaitis and Moshe Y. Vardi},
    title = 	 {0-1 laws for infinitary logics},
    booktitle =  {Proceedings of the Fifth Annual IEEE Symposium on Logic in Computer Science (LICS 1990)},
    year =	 {1990},
    month =	 {June}, 
    pages =      {156--167},
    location =   {Philadelphia, PA, USA}, 
    publisher =	 {IEEE Computer Society Press}

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