The 0-1 law fails for monadic existential second-order logic on undirected graphs

DOI10.1016/S0020-0190(00)00149-6MaRDI QIDQ1607080zbMATH OpenOpenAlexFDO

Authors Jean-Marie Le Bars

Publication date 25 July 2002

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(00)00149-6

zbMATH Keywords

0-1 lawsfragments of monadic existential second-order logic

Mathematics Subject Classification ID

Logic in computer science (03B70) Model theory of finite structures (03C13) Second- and higher-order model theory (03C85) Random graphs (graph-theoretic aspects) (05C80)

Recommendations

• EMSO(FO^2) 0-1 Law Fails for All Dense Random Graphs
• Existential monadic second order logic of undirected graphs: the Le Bars conjecture is false
• Logical laws for short existential monadic second-order sentences about graphs
• Logical laws for existential monadic second-order sentences with infinite first-order parts
• Failure of 0-1 law for sparse random graph in strong logics (Sh1062)

Cites work

• 0-1 laws and decision problems for fragments of second-order logic
• A counterexample to the 0-1 law for the class of existential second-order minimal Gödel sentences with equality
• Counterexamples of the 0-1 Law for Fragments of Existential Second-Order Logic: an Overview
• scientific article; zbMATH DE number 1392294 (Why is no real title available?)
• On random models of finite power and monadic logic
• Probabilities on finite models

Cited in

(9)

• Logical laws for existential monadic second-order sentences with infinite first-order parts
• Existential monadic second order logic of undirected graphs: the Le Bars conjecture is false
• A disproof the Le Bars conjecture about the zero-one law for existential monadic second-order sentences
• Existential monadic second order convergence law fails on sparse random graphs
• Disproof of the zero-one law for existential monadic properties of a sparse binomial random graph
• A logical approach to asymptotic combinatorics. II: Monadic second-order properties
• Counterexamples of the 0-1 Law for Fragments of Existential Second-Order Logic: an Overview
• EMSO(FO^2) 0-1 Law Fails for All Dense Random Graphs
• Logical laws for short existential monadic second-order sentences about graphs

This page was built for publication: The 0-1 law fails for monadic existential second-order logic on undirected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1607080)