Counterexamples of the 0-1 Law for Fragments of Existential Second-Order Logic: an Overview

DOI10.2307/421076zbMath0958.03022OpenAlexW2059486372WikidataQ124967083 ScholiaQ124967083MaRDI QIDQ4953235

Jean-Marie Le Bars

Publication date: 22 March 2001

Published in: Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: http://www.math.ucla.edu/~asl/bsl/0601-toc.htm

zbMATH Keywords

second-order logicfinite structures0-1 lawsecond-order quantification

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Model theory of finite structures (03C13) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items

Cycles and transitivity by monochromatic paths in arc-coloured digraphs, H-absorbence and H-independence in 3-quasi-transitive H-coloured digraphs., Characterization of asymmetric CKI- and KP-digraphs with covering number at most 3, Kernels by monochromatic paths in digraphs with covering number 2, Kernels in planar digraphs, Strong kernel number in certain oriented cycle extension of graphs, \(H\)-paths and \(H\)-cycles in \(H\)-coloured digraphs, The 0-1 law fails for monadic existential second-order logic on undirected graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
• 0-1 laws and decision problems for fragments of second-order logic
• On random models of finite power and monadic logic
• A counterexample to the 0-1 law for the class of existential second-order minimal Gödel sentences with equality
• Kernels in random graphs
• The Gödel class with identity is unsolvable
• Asymptotic probabilities of existential second-order Gödel sentences
• Probabilities on finite models
• On languages with two variables
• Cliques in random graphs
• Asymptotic probabilities for second-order existential Kahr-Moore-Wang sentences