RUS  ENG
Full version
JOURNALS // Siberian Journal of Pure and Applied Mathematics // Archive

Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform., 2010 Volume 10, Issue 2, Pages 37–44 (Mi vngu38)

Scott Rank of Automatic Partial Orderings

A. A. Gavryushkina

Novosibirsk State University

Abstract: One of the main problems in the theory of automatic structures is the problem of characterization of automatic structures and subclasses of automatic structures. Scott ranks measure the complexity of the description of the isomorphism types of structures. M. Minnes and B. Khoussainov showed that for every ordinal $\alpha$ at most $\omega_1^{CK}+1$ there exists an automatic structure of Scott rank $\alpha$ [7;8]. In this paper we show that the same result holds for automatic partial orders.

Keywords: automatic structure, partial order, Scott rank.

UDC: 510.51

Received: 23.06.2009



© Steklov Math. Inst. of RAS, 2024