The complexity of random ordered structures
Annals of Pure and Applied Logic 152 (1-3):174-179 (2008)
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.Author Profiles
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.
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.
Algorithmic randomness of continuous functions.George Barmpalias, Paul Brodhead, Douglas Cenzer, Jeffrey B. Remmel & Rebecca Weber - 2008 - Archive for Mathematical Logic 46 (7-8):533-546.
Spatial embedding and the structure of complex networks.S. Bullock, L. Barnett & E. A. Di Paolo - 2010 - Complexity 16 (2):20-28.
Convergence Laws for Very Sparse Random Structures with Generalized Quantifiers.Risto Kaila - 2002 - Mathematical Logic Quarterly 48 (2):301-320.
Every computably enumerable random real is provably computably enumerable random.Cristian Calude & Nicholas Hay - 2009 - Logic Journal of the IGPL 17 (4):351-374.
Random graphs in the monadic theory of order.Shmuel Lifsches & Saharon Shelah - 1999 - Archive for Mathematical Logic 38 (4-5):273-312.
Randomness, relativization and Turing degrees.André Nies, Frank Stephan & Sebastiaan A. Terwijn - 2005 - Journal of Symbolic Logic 70 (2):515-535.
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.
Analytics
Added to PP
2017-02-19
Downloads
8 (#987,925)
6 months
1 (#447,993)
2017-02-19
Downloads
8 (#987,925)
6 months
1 (#447,993)
Historical graph of downloads
