排序方式: 共有13条查询结果,搜索用时 15 毫秒
1.
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. 相似文献
2.
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 α. 相似文献
3.
We show there is a computable linear order with a
initial segment that is not isomorphic to any computable linear order. 相似文献
4.
5.
Bakhadyr Khoussainov Alexander Yakhnis Vladimir Yakhnis 《Mathematical Logic Quarterly》1998,44(2):185-204
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]. 相似文献
6.
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. 相似文献
7.
Douglas Cenzer Barbara F. Csima Bakhadyr Khoussainov 《Archive for Mathematical Logic》2009,48(1):63-76
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. 相似文献
8.
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. 相似文献
9.
Bakhadyr Khoussainov Theodore Slaman Pavel Semukhin 《Archive for Mathematical Logic》2006,45(6):769-781
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. 相似文献
10.
Bakhadyr Khoussainov 《Mathematical Logic Quarterly》2000,46(4):467-475
In this paper we show that for any set X ⊆ ω there exists a structure 𝒜 that has no presentation computable in X such that 𝒜2 has a computable presentation. We also show that there exists a structure 𝒜 with infinitely many computable isomorphism types such that 𝒜2 has exactly one computable isomorphism type. 相似文献