• DocumentCode
    2717034
  • Title

    0-1 laws for infinitary logics

  • Author

    Kolaitis, Phokion G. ; Vardi, Moshe Y.

  • Author_Institution
    Comput. & Inf. Sci., California Univ., Santa Cruz, CA, USA
  • fYear
    1990
  • fDate
    4-7 Jun 1990
  • Firstpage
    156
  • Lastpage
    167
  • Abstract
    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
  • Keywords
    formal logic; probability; 0-1 laws; asymptotic probabilities; asymptotic probability; conjunctions; disjunctions; distinct variables; finite structures; fixpoint logics; infinitary logics; zero-one law; Application software; Combinatorial mathematics; Complexity theory; Computer science; Databases; Logic; Vocabulary;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Logic in Computer Science, 1990. LICS '90, Proceedings., Fifth Annual IEEE Symposium on e
  • Conference_Location
    Philadelphia, PA
  • Print_ISBN
    0-8186-2073-0
  • Type

    conf

  • DOI
    10.1109/LICS.1990.113742
  • Filename
    113742