The complexity of random ordered structures

&
Annals of Pure and Applied Logic 152 (1-3):174-179 (2008)
  Copy   BIBTEX

Abstract

We show that for random bit strings, Up, with probability, image, the first order quantifier depth D) needed to distinguish non-isomorphic structures is Θ, with high probability. Further, we show that, with high probability, for random ordered graphs, G≤,p with edge probability image, D)=Θ, contrasting with the results for random graphs, Gp, given by Kim et al. [J.H. Kim, O. Pikhurko, J. Spencer, O. Verbitsky, How complex are random graphs in first order logic? Random Structures and Algorithms 26 119–145] of D)=log1/pn+O.

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2007.11.010

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,031

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

The complexity of random ordered structures.Joel H. Spencer & Katherine St John - 2008 - Annals of Pure and Applied Logic 152 (1):174-179.
The Strange Logic of Random Graphs.Joel Spencer - 2001 - Springer Verlag.
Infinitary logics and very sparse random graphs.James F. Lynch - 1997 - Journal of Symbolic Logic 62 (2):609-623.
Infinitary Logics and Very Sparse Random Graphs.James Lynch - 1997 - Journal of Symbolic Logic 62 (2):609-623.
Evolving Shelah‐Spencer graphs.Richard Elwes - 2021 - Mathematical Logic Quarterly 67 (1):6-17.
Random generations of the countable random graph.Su Gao & A. Vershik - 2006 - Annals of Pure and Applied Logic 143 (1-3):79-86.
In the random graph G(n, p), p = n−a: If ψ has probability O(n−ε) for every ε > 0 then it has probability O(e−nε) for some ε > 0.Saharon Shelah - 1996 - Annals of Pure and Applied Logic 82 (1):97-102.
In the random graph G(n, p), p = n−a: If ψ has probability O(n−ε) for every ε > 0 then it has probability O(e−nε) for some ε > 0. [REVIEW]Saharon Shelah - 1996 - Annals of Pure and Applied Logic 82 (1):97-102.
The metamathematics of random graphs.John T. Baldwin - 2006 - Annals of Pure and Applied Logic 143 (1-3):20-28.
Monadic second-order properties of very sparse random graphs.L. B. Ostrovsky & M. E. Zhukovskii - 2017 - Annals of Pure and Applied Logic 168 (11):2087-2101.

Analytics

Added to PP
2017-02-19

Downloads
14 (#1,019,271)

6 months
5 (#711,233)

Historical graph of downloads
How can I increase my downloads?

Author Profiles

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references