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
Link To Document :
بازگشت