0-1 laws for infinitary logics
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 156-167
- https://doi.org/10.1109/lics.1990.113742
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
This publication has 26 references indexed in Scilit:
- On the Expressive Power of Datalog: Tools and a Case StudyJournal of Computer and System Sciences, 1995
- The 0-1 law fails for the class of existential second order Godel sentences with equalityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Second-order and Inductive Definability on Finite StructuresMathematical Logic Quarterly, 1987
- Fixed-point extensions of first-order logicAnnals of Pure and Applied Logic, 1986
- Complexity of the first-order theory of almost all finite structuresInformation and Control, 1983
- Almost sure theoriesAnnals of Mathematical Logic, 1980
- Probabilities on finite modelsThe Journal of Symbolic Logic, 1976
- Hamiltonian circuits in random graphsDiscrete Mathematics, 1976
- Monadic generalized spectraMathematical Logic Quarterly, 1975
- Range and degree of realizability of formulas in the restricted predicate calculusCybernetics and Systems Analysis, 1972