On random models of finite power and monadic logic

DOI10.1016/0012-365X(85)90112-8zbMath0579.03006MaRDI QIDQ1066878

Matt Kaufmann, Saharon Shelah

Publication date: 1985

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

monadic second-order logic0-1 lawfraction of models of power nmonadic quantification

Mathematics Subject Classification ID

Related Items (25)

Nonconvergence, undecidability, and intractability in asymptotic problems ⋮ Asymptotic probabilities of existential second-order Gödel sentences ⋮ European Summer Meeting of the Association for Symbolic Logic ⋮ The computational complexity of asymptotic problems. I: Partial orders ⋮ Application of a Tauberian theorem to finite model theory ⋮ Convergence in homogeneous random graphs ⋮ EMSO(FO$^2$) 0-1 Law Fails for All Dense Random Graphs ⋮ Disproof of the zero-one law for existential monadic properties of a sparse binomial random graph ⋮ Logical laws for short existential monadic second-order sentences about graphs ⋮ Logical laws for existential monadic second-order sentences with infinite first-order parts ⋮ A uniform method for proving lower bounds on the computational complexity of logical theories ⋮ Existential monadic second order logic of undirected graphs: the Le Bars conjecture is false ⋮ 0-1 laws and decision problems for fragments of second-order logic ⋮ A disproof the Le Bars conjecture about the zero-one law for existential monadic second-order sentences ⋮ Counting finite models ⋮ Logical limit laws for minor-closed classes of graphs ⋮ Infinitary logics and 0-1 laws ⋮ MSO 0-1 law for recursive random trees ⋮ Finite-model theory -- A personal perspective ⋮ Existential monadic second order convergence law fails on sparse random graphs ⋮ Counterexamples of the 0-1 Law for Fragments of Existential Second-Order Logic: an Overview ⋮ Probabilities in first—order logic of a unary function and a binary relation ⋮ Zero-One Laws for Sparse Random Graphs ⋮ Almost Everywhere Equivalence of Logics in Finite Model Theory ⋮ The 0-1 law fails for monadic existential second-order logic on undirected graphs

Cites Work

• A logical approach to asymptotic combinatorics I. First order properties
• Concerning measures in first order calculi
• Almost sure theories
• Probabilities on finite models

This page was built for publication: On random models of finite power and monadic logic