The complexity of random ordered structures

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


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.



    Upload a copy of this work     Papers currently archived: 76,140

External links

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

Through your library

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.
Random generations of the countable random graph.Su Gao & A. Vershik - 2006 - Annals of Pure and Applied Logic 143 (1-3):79-86.
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.
Recursive events in random sequences.George Davie - 2001 - Archive for Mathematical Logic 40 (8):629-638.
Random graphs in the monadic theory of order.Shmuel Lifsches & Saharon Shelah - 1999 - Archive for Mathematical Logic 38 (4-5):273-312.
Every 2-random real is Kolmogorov random.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (3):907-913.
The Kolmogorov complexity of random reals.Liang Yu, Decheng Ding & Rodney Downey - 2004 - Annals of Pure and Applied Logic 129 (1-3):163-180.


Added to PP

8 (#987,925)

6 months
1 (#447,993)

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