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

DOI10.2307/421076zbMath0958.03022WikidataQ124967083 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 logic; finite structures; 0-1 law; second-order quantification

Mathematics Subject Classification ID

03-02: Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations

03C13: Model theory of finite structures

03B20: Subsystems of classical logic (including intuitionistic logic)

Related Items

H-absorbence and H-independence in 3-quasi-transitive H-coloured digraphs., Cycles and transitivity by monochromatic paths in arc-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, The 0-1 law fails for monadic existential second-order logic on undirected graphs, \(H\)-paths and \(H\)-cycles in \(H\)-coloured digraphs, Kernels in planar digraphs, Strong kernel number in certain oriented cycle extension of 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