Uniformity in Computable Structure Theory

We investigate the effects of adding uniformity requirements to concepts in computable structure theory such as computable categoricity (of a structure) and intrinsic computability (of a relation on a computable structure). We consider and compare two different notions of uniformity, previously studied by Kudinov and by Ventsov. We discuss some of their results and establish new ones, while also exploring the connections with the relative computable structure theory of Ash, Knight, Manasse, and Slaman and Chisholm and with previous work of Ash, Knight, and Slaman on uniformity in a general computable structure-theoretical setting.     

Model-theoretic complexity of automatic structures

We study the complexity of automatic structures via well-established concepts from both logic and model theory, including ordinal heights (of well-founded relations), Scott ranks of structures, and Cantor–Bendixson ranks (of trees). We prove the following results: (1) The ordinal height of any automatic well-founded partial order is bounded by ω^ω. (2) The ordinal heights of automatic well-founded relations are unbounded below , the first non-computable ordinal. (3) For any computable ordinal α, there is an automatic structure of Scott rank at least α. Moreover, there are automatic structures of Scott rank . (4) For any computable ordinal α, there is an automatic successor tree of Cantor–Bendixson rank α.     

On Initial Segments of Computable Linear Orders

We show there is a computable linear order with a initial segment that is not isomorphic to any computable linear order.     

Games with Unknown Past

We define a new type of two player game occurring on a tree. The tree may have no root and may have arbitrary degrees of nodes. These games extend the class of games considered by Gurevich-Harrington in [5]. We prove that in the game one of the players has a winning strategy which depends on finite bounded information about the past part of a play and on future of each play that is isomorphism types of tree nodes. This result extends further the Gurevich-Harrington determinacy theorem from [5].     

Update games and update networks

In this paper we model infinite processes with finite configurations as infinite games over finite graphs. We investigate those games, called update games, in which each configuration occurs an infinite number of times during a two-person play. We also present an efficient polynomial-time algorithm (and partial characterization) for deciding if a graph is an update network.     

Linear orders with distinguished function symbol

We consider certain linear orders with a function on them, and discuss for which types of functions the resulting structure is or is not computably categorical. Particularly, we consider computable copies of the rationals with a fixed-point free automorphism, and also ω with a non-decreasing function. D. Cenzer was partially supported by National Science Foundation grants DMS 0532644 and 0554841 and 652372. B. Csima was partially supported by Canadian NSERC Discovery Grant 312501. B. Khoussainov has partially been supported by Marsden Fund of Royal New Zealand Society.     

On complexity of Ehrenfeucht–Fraïssé games

In this paper, we initiate the study of Ehrenfeucht–Fraïssé games for some standard finite structures. Examples of such standard structures are equivalence relations, trees, unary relation structures, Boolean algebras, and some of their natural expansions. The paper concerns the following question that we call the Ehrenfeucht–Fraïssé problem. Given nω as a parameter, and two relational structures and from one of the classes of structures mentioned above, how efficient is it to decide if Duplicator wins the n-round EF game ? We provide algorithms for solving the Ehrenfeucht–Fraïssé problem for the mentioned classes of structures. The running times of all the algorithms are bounded by constants. We obtain the values of these constants as functions of n.     

\Pi^0_1-Presentations of Algebras

In this paper we study the question as to which computable algebras are isomorphic to non-computable -algebras. We show that many known algebras such as the standard model of arithmetic, term algebras, fields, vector spaces and torsion-free abelian groups have non-computable-presentations. On the other hand, many of this structures fail to have non-computable -presentation.This research was partially supported by the Marsden Fund of New Zealand. The third author’s research was partially supported by RFFR grant No. 02-01-00593 and Council for Grants under RF President, project NSh-2112.2003.1.     

On Computability Theoretic Properties of Structures and Their Cartesian Products

In this paper we show that for any set X ⊆ ω there exists a structure 𝒜 that has no presentation computable in X such that 𝒜² has a computable presentation. We also show that there exists a structure 𝒜 with infinitely many computable isomorphism types such that 𝒜² has exactly one computable isomorphism type.