TY - JOUR
T1 - The complexity of random ordered structures
AU - Spencer, Joel H.
AU - St. John, Katherine
N1 - Funding Information:
1 We thank the referees for their helpful comments. The second author gratefully acknowledges support from NSF ITR 01-21651 and MRI 02-15942 and the hospitality of the Centre de Recerca Matemàtica, Barcelona, Spain. 2 Email: [email protected] 3 Email: [email protected]
PY - 2006/1/6
Y1 - 2006/1/6
N2 - We show that for random bit strings, Up(n), with probability, p=12, the first-order quantifier depth D(Up(n)) needed to distinguish non-isomorphic structures is Θ(lglgn), with high probability. Further, we show that, with high probability, for random ordered graphs, G≤,p(n) with edge probabiltiy p=12, D(G≤,p(n))=Θ(log*n), contrasting with the results of random (non-ordered) graphs, Gp(n), by Kim et al. [J.H. Kim, O. Pikhurko, J. Spencer, O. Verbitsky, How complex are random graphs in first order logic? (2005), to appear in Random Structures and Algorithms] of D(Gp(n))=log1/pn+O(lglgn).
AB - We show that for random bit strings, Up(n), with probability, p=12, the first-order quantifier depth D(Up(n)) needed to distinguish non-isomorphic structures is Θ(lglgn), with high probability. Further, we show that, with high probability, for random ordered graphs, G≤,p(n) with edge probabiltiy p=12, D(G≤,p(n))=Θ(log*n), contrasting with the results of random (non-ordered) graphs, Gp(n), by Kim et al. [J.H. Kim, O. Pikhurko, J. Spencer, O. Verbitsky, How complex are random graphs in first order logic? (2005), to appear in Random Structures and Algorithms] of D(Gp(n))=log1/pn+O(lglgn).
KW - Ehrenfeucht-Fraisse games
KW - First order logic
KW - Random bit strings
KW - Random graphs
UR - http://www.scopus.com/inward/record.url?scp=29444444407&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=29444444407&partnerID=8YFLogxK
U2 - 10.1016/j.entcs.2005.05.030
DO - 10.1016/j.entcs.2005.05.030
M3 - Article
AN - SCOPUS:29444444407
SN - 1571-0661
VL - 143
SP - 197
EP - 206
JO - Electronic Notes in Theoretical Computer Science
JF - Electronic Notes in Theoretical Computer Science
IS - SPEC. ISS.
ER -