The complexity of random ordered structures

DOI10.1016/J.APAL.2007.11.010MaRDI QIDQ2478557zbMATH OpenOpenAlexFDO

Authors Katherine St. John, Joel Spencer

Publication date 28 March 2008

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.apal.2007.11.010

zbMATH Keywords

first-order logicrandom graphsEhrenfeucht-Fraisse games

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Model theory of finite structures (03C13) Models of other mathematical theories (03C65)

Recommendations

• How complex are random graphs in first order logic?
• First-Order Definability of Trees and Sparse Random Graphs
• Bounded quantifier depth spectra for random graphs
• Theory of Cryptography
• Random graph orders do not satisfy a 0–1 law

Cites work

• scientific article; zbMATH DE number 3467028 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• A zero‐one law for a random subset
• How complex are random graphs in first order logic?
• Probabilities of First-Order Sentences about Unary Functions
• The strange logic of random graphs
• The tenacity of zero-one laws
• Zero-One Laws for Sparse Random Graphs

Cited in

(3)

• Complexity analysis of random geometric structures made simpler
• How complex are random graphs in first order logic?
• The fine-grained complexity of multi-dimensional ordering properties

This page was built for publication: The complexity of random ordered structures

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