First order complexity of finite random structures

DOI10.1145/3661814.3662127MaRDI QIDQ6970246zbMATH OpenFDO

Authors Danila Demin, M. E. Zhukovskii

Publication date 18 June 2025

Full work available at URL https://doi.org/10.1145/3661814.3662127

zbMATH Keywords

first-order logiclogical complexitylogical limit lawsrandom graphsrandom structuresrecursively enumerable languageszero-one laws

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Other degrees and reducibilities in computability and recursion theory (03D30) Random graphs (graph-theoretic aspects) (05C80) Zero-one laws (60F20)

Cites work

• \(\gamma\)-variable first-order logic of uniform attachment random graphs
• A logical approach to asymptotic combinatorics. II: Monadic second-order properties
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• A Problem of the Allocation of Particles in Cells and Random Mappings
• An application of games to the completeness problem for formalized theories
• Convergence law for random graphs with specified degree sequence
• Elements of finite model theory.
• First order complexity of finite random structures
• First-order zero-one law for the uniform model of the random graph
• scientific article; zbMATH DE number 3115890 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 1286037 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 545277 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 887782 (Why is no real title available?)
• scientific article; zbMATH DE number 3266604 (Why is no real title available?)
• Isomorphism and embedding problems for infinite limits of scale-free graphs
• Limiting probabilities of first order properties of random sparse graphs and hypergraphs
• Logical limit laws for minor-closed classes of graphs
• Monadic second-order properties of very sparse random graphs
• MSO zero-one laws on random labelled acyclic graphs
• On the first-order complexity of induced subgraph isomorphism
• On the strength of connectedness of a random hypergraph
• Probabilities of first-order sentences on sparse random relational structures: An application to definability on random CNF formulas
• Probabilities of Sentences about Very Sparse Random Graphs
• Probabilities on finite models
• Some problems in the enumeration of labelled graphs
• The asymptotic distribution of short cycles in random regular graphs
• The descriptive complexity of subgraph isomorphism without numerics
• The logic of random regular graphs
• The strange logic of random graphs
• Threshold spectra via the Ehrenfeucht game
• Zero-One Laws for Sparse Random Graphs

Cited in

(1)

• First order complexity of finite random structures

This page was built for publication: First order complexity of finite random structures

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