Results for 'computable structures'

999 found
Order:
  1.  18
    Realizing Levels of the Hyperarithmetic Hierarchy as Degree Spectra of Relations on Computable Structures.Walker M. White & Denis R. Hirschfeldt - 2002 - Notre Dame Journal of Formal Logic 43 (1):51-64.
    We construct a class of relations on computable structures whose degree spectra form natural classes of degrees. Given any computable ordinal and reducibility r stronger than or equal to m-reducibility, we show how to construct a structure with an intrinsically invariant relation whose degree spectrum consists of all nontrivial r-degrees. We extend this construction to show that can be replaced by either or.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  2.  9
    Strange Structures From Computable Model Theory.Howard Becker - 2017 - Notre Dame Journal of Formal Logic 58 (1):97-105.
    Let L be a countable language, let I be an isomorphism-type of countable L-structures, and let a∈2ω. We say that I is a-strange if it contains a computable-from-a structure and its Scott rank is exactly ω1a. For all a, a-strange structures exist. Theorem : If C is a collection of ℵ1 isomorphism-types of countable structures, then for a Turing cone of a’s, no member of C is a-strange.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  3.  6
    On the Complexity of Categoricity in Computable Structures.Walker M. White - 2003 - Mathematical Logic Quarterly 49 (6):603.
    We investigate the computational complexity the class of Γ-categorical computable structures. We show that hyperarithmetic categoricity is Π11-complete, while computable categoricity is Π04-hard.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  4.  8
    Computable Structures and the Hyperarithmetical Hierarchy.C. J. Ash - 2000 - Elsevier.
    This book describes a program of research in computable structure theory. The goal is to find definability conditions corresponding to bounds on complexity which persist under isomorphism. The results apply to familiar kinds of structures (groups, fields, vector spaces, linear orderings Boolean algebras, Abelian p-groups, models of arithmetic). There are many interesting results already, but there are also many natural questions still to be answered. The book is self-contained in that it includes necessary background material from recursion theory (...)
    Direct download  
     
    Export citation  
     
    Bookmark   25 citations  
  5.  13
    Embeddings of Computable Structures.Asher M. Kach, Oscar Levin & Reed Solomon - 2010 - Notre Dame Journal of Formal Logic 51 (1):55-68.
    We study what the existence of a classical embedding between computable structures implies about the existence of computable embeddings. In particular, we consider the effect of fixing and varying the computable presentations of the computable structures.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  6.  6
    Classifications of Computable Structures.Karen Lange, Russell Miller & Rebecca M. Steiner - 2018 - Notre Dame Journal of Formal Logic 59 (1):35-59.
    Let K be a family of structures, closed under isomorphism, in a fixed computable language. We consider effective lists of structures from K such that every structure in K is isomorphic to exactly one structure on the list. Such a list is called a computable classification of K, up to isomorphism. Using the technique of Friedberg enumeration, we show that there is a computable classification of the family of computable algebraic fields and that with (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  7.  28
    Isomorphism Relations on Computable Structures.Ekaterina B. Fokina, Sy-David Friedman, Valentina Harizanov, Julia F. Knight, Charles Mccoy & Antonio Montalbán - 2012 - Journal of Symbolic Logic 77 (1):122-132.
    We study the complexity of the isomorphism relation on classes of computable structures. We use the notion of FF-reducibility introduced in [9] to show completeness of the isomorphism relation on many familiar classes in the context of all ${\mathrm{\Sigma }}_{1}^{1}$ equivalence relations on hyperarithmetical subsets of ω.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  8. Degree Spectra of Relations on Computable Structures in the Presence of Δ02 Isomorphisms.Denis R. Hirschfeldt - 2002 - Journal of Symbolic Logic 67 (2):697 - 720.
    We give some new examples of possible degree spectra of invariant relations on Δ 0 2 -categorical computable structures, which demonstrate that such spectra can be fairly complicated. On the other hand, we show that there are nontrivial restrictions on the sets of degrees that can be realized as degree spectra of such relations. In particular, we give a sufficient condition for a relation to have infinite degree spectrum that implies that every invariant computable relation on a (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  9.  9
    Computable Structures of Rank.J. F. Knight & J. Millar - 2010 - Journal of Mathematical Logic 10 (1):31-43.
    For countable structure, "Scott rank" provides a measure of internal, model-theoretic complexity. For a computable structure, the Scott rank is at most [Formula: see text]. There are familiar examples of computable structures of various computable ranks, and there is an old example of rank [Formula: see text]. In the present paper, we show that there is a computable structure of Scott rank [Formula: see text]. We give two different constructions. The first starts with an arithmetical (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  10. Computable Structures of Rank Omega (Ck)(1).J. F. Knight & J. Millar - 2010 - Journal of Mathematical Logic 10 (1):31-43.
    For countable structure, "Scott rank" provides a measure of internal, model-theoretic complexity. For a computable structure, the Scott rank is at most [Formula: see text]. There are familiar examples of computable structures of various computable ranks, and there is an old example of rank [Formula: see text]. In the present paper, we show that there is a computable structure of Scott rank [Formula: see text]. We give two different constructions. The first starts with an arithmetical (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  11.  13
    Hanf Number for Scott Sentences of Computable Structures.S. S. Goncharov, J. F. Knight & I. Souldatos - 2018 - Archive for Mathematical Logic 57 (7-8):889-907.
    The Hanf number for a set S of sentences in \ is the least infinite cardinal \ such that for all \, if \ has models in all infinite cardinalities less than \, then it has models of all infinite cardinalities. Friedman asked what is the Hanf number for Scott sentences of computable structures. We show that the value is \. The same argument proves that \ is the Hanf number for Scott sentences of hyperarithmetical structures.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  12.  45
    Degrees of Categoricity of Computable Structures.Ekaterina B. Fokina, Iskander Kalimullin & Russell Miller - 2010 - Archive for Mathematical Logic 49 (1):51-67.
    Defining the degree of categoricity of a computable structure ${\mathcal{M}}$ to be the least degree d for which ${\mathcal{M}}$ is d-computably categorical, we investigate which Turing degrees can be realized as degrees of categoricity. We show that for all n, degrees d.c.e. in and above 0 (n) can be so realized, as can the degree 0 (ω).
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  13.  4
    Coding and Definability in Computable Structures.Antonio Montalbán - 2018 - Notre Dame Journal of Formal Logic 59 (3):285-306.
    These are the lecture notes from a 10-hour course that the author gave at the University of Notre Dame in September 2010. The objective of the course was to introduce some basic concepts in computable structure theory and develop the background needed to understand the author’s research on back-and-forth relations.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  14.  6
    Turing Degrees of Hypersimple Relations on Computable Structures.Valentina S. Harizanov - 2003 - Annals of Pure and Applied Logic 121 (2-3):209-226.
    Let be an infinite computable structure, and let R be an additional computable relation on its domain A. The syntactic notion of formal hypersimplicity of R on , first introduced and studied by Hird, is analogous to the computability-theoretic notion of hypersimplicity of R on A, given the definability of certain effective sequences of relations on A. Assuming that R is formally hypersimple on , we give general sufficient conditions for the existence of a computable isomorphic copy (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  15.  12
    Degree Spectra and Computable Dimensions in Algebraic Structures.Denis R. Hirschfeldt, Bakhadyr Khoussainov, Richard A. Shore & Arkadii M. Slinko - 2002 - Annals of Pure and Applied Logic 115 (1-3):71-113.
    Whenever a structure with a particularly interesting computability-theoretic property is found, it is natural to ask whether similar examples can be found within well-known classes of algebraic structures, such as groups, rings, lattices, and so forth. One way to give positive answers to this question is to adapt the original proof to the new setting. However, this can be an unnecessary duplication of effort, and lacks generality. Another method is to code the original structure into a structure in the (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   34 citations  
  16. Pairs of Computable Structures.C. J. Ash & J. F. Knight - 1990 - Annals of Pure and Applied Logic 46 (3):211-234.
  17.  13
    Computable Structures in Generic Extensions.Julia Knight, Antonio Montalbán & Noah Schweber - 2016 - Journal of Symbolic Logic 81 (3):814-832.
  18.  18
    Degree Spectra of Relations on Computable Structures.Denis R. Hirschfeldt - 2000 - Bulletin of Symbolic Logic 6 (2):197-212.
  19.  5
    Review: C. J. Ash, J. Knight, Computable Structures and the Hyperarithmetical Hierarchy. [REVIEW]Valentina Harizanov - 2001 - Bulletin of Symbolic Logic 7 (3):383-385.
  20.  3
    Isomorphism of Computable Structures and Vaught's Conjecture.Howard Becker - 2013 - Journal of Symbolic Logic 78 (4):1328-1344.
  21.  3
    Ash C. J. And Knight J.. Computable Structures and the Hyperarithmetical Hierarchy. Studies in Logic and the Foundations of Mathematics, Vol. 144. Elsevier, Amsterdam Etc. 2000, Xv + 346 Pp. [REVIEW]Valentina Harizanov - 2001 - Bulletin of Symbolic Logic 7 (3):383-385.
  22. Degree Spectra of Relations on Computable Structures in the Presence of Δ20 Isomorphisms.Denis Hirschfeldt - 2002 - Journal of Symbolic Logic 67 (2):697-720.
  23.  8
    Computability and Continuity in Computable Metric Partial Algebras Equipped with Computability Structures.F. Dahlgren - 2004 - Mathematical Logic Quarterly 50 (4):486.
    In this paper we give an axiomatisation of the concept of a computability structure with partial sequences on a many-sorted metric partial algebra, thus extending the axiomatisation given by Pour-El and Richards in [9] for Banach spaces. We show that every Banach-Mazur computable partial function from an effectively separable computable metric partial Σ-algebra A to a computable metric partial Σ-algebra B must be continuous, and conversely, that every effectively continuous partial function with semidecidable domain and which preserves (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  24.  2
    Degree Spectra of Relations on Structures of Finite Computable Dimension.Denis R. Hirschfeldt - 2002 - Annals of Pure and Applied Logic 115 (1-3):233-277.
    We show that for every computably enumerable degree a > 0 there is an intrinsically c.e. relation on the domain of a computable structure of computable dimension 2 whose degree spectrum is { 0 , a } , thus answering a question of Goncharov and Khoussainov 55–57). We also show that this theorem remains true with α -c.e. in place of c.e. for any α∈ω∪{ω} . A modification of the proof of this result similar to what was done (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  25.  6
    S. S. Goncharov. Autostability and Computable Families of Constructivizations. Algebra and Logic, Vol. 14 , No. 6, Pp. 392–409. - S. S. Goncharov. The Quantity of Nonautoequivalent Constructivizations. Algebra and Logic, Vol. 16 , No. 3, Pp. 169–185. - S. S. Goncharov and V. D. Dzgoev. Autostability of Models. Algebra and Logic, Vol. 19 , No. 1, Pp. 28–37. - J. B. Remmel. Recursively Categorical Linear Orderings. Proceedings of the American Mathematical Society, Vol. 83 , No. 2, Pp. 387–391. - Terrence Millar. Recursive Categoricity and Persistence. The Journal of Symbolic Logic, Vol. 51 , No. 2, Pp. 430–434. - Peter Cholak, Segey Goncharov, Bakhadyr Khoussainov and Richard A. Shore. Computably Categorical Structures and Expansions by Constants. The Journal of Symbolic Logic, Vol. 64 , No. 1, Pp. 13–137. - Peter Cholak, Richard A. Shore and Reed Solomon. A Computably Stable Structure with No Scott Family of Finitary Formulas. Archive for Mathematical Logic, Vol. 45 , No. 5, Pp. 519–538. [REVIEW]Daniel Turetsky - 2012 - Bulletin of Symbolic Logic 18 (1):131-134.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  26.  8
    Provable Computable Selection Functions on Abstract Structures.J. Tucker & J. Zucker - 1992 - In Peter Aczel, Harold Simmons & S. S. Wainer (eds.), Proof Theory: A Selection of Papers From the Leeds Proof Theory Programme, 1990. Cambridge University Press. pp. 275.
  27.  10
    Categoricity Spectra for Rigid Structures.Ekaterina Fokina, Andrey Frolov & Iskander Kalimullin - 2016 - Notre Dame Journal of Formal Logic 57 (1):45-57.
    For a computable structure $\mathcal {M}$, the categoricity spectrum is the set of all Turing degrees capable of computing isomorphisms among arbitrary computable copies of $\mathcal {M}$. If the spectrum has a least degree, this degree is called the degree of categoricity of $\mathcal {M}$. In this paper we investigate spectra of categoricity for computable rigid structures. In particular, we give examples of rigid structures without degrees of categoricity.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  28.  2
    New Degree Spectra of Abelian Groups.Alexander G. Melnikov - 2017 - Notre Dame Journal of Formal Logic 58 (4):507-525.
    We show that for every computable ordinal of the form β=δ+2n+1>1, where δ is zero or a limit ordinal and n∈ω, there exists a torsion-free abelian group having an X-computable copy if and only if X is nonlowβ.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  29.  15
    The Isomorphism Problem for Computable Abelian P-Groups of Bounded Length.Wesley Calvert - 2005 - Journal of Symbolic Logic 70 (1):331 - 345.
    Theories of classification distinguish classes with some good structure theorem from those for which none is possible. Some classes (dense linear orders, for instance) are non-classifiable in general, but are classifiable when we consider only countable members. This paper explores such a notion for classes of computable structures by working out a sequence of examples. We follow recent work by Goncharov and Knight in using the degree of the isomorphism problem for a class to distinguish classifiable classes from (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  30.  8
    The Isomorphism Problem for Classes of Computable Fields.Wesley Calvert - 2004 - Archive for Mathematical Logic 43 (3):327-336.
    Theories of classification distinguish classes with some good structure theorem from those for which none is possible. Some classes (dense linear orders, for instance) are non-classifiable in general, but are classifiable when we consider only countable members. This paper explores such a notion for classes of computable structures by working out several examples. One motivation is to see whether some classes whose set of countable members is very complex become classifiable when we consider only computable members. We (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  31.  14
    Index Sets for Classes of High Rank Structures.W. Calvert, E. Fokina, S. S. Goncharov, J. F. Knight, O. Kudinov, A. S. Morozov & V. Puzarenko - 2007 - Journal of Symbolic Logic 72 (4):1418 - 1432.
    This paper calculates, in a precise way, the complexity of the index sets for three classes of computable structures: the class $K_{\omega _{1}^{\mathit{CK}}}$ of structures of Scott rank $\omega _{1}^{\mathit{CK}}$ , the class $K_{\omega _{1}^{\mathit{CK}}+1}$ of structures of Scott rank $\omega _{1}^{\mathit{CK}}+1$ , and the class K of all structures of non-computable Scott rank. We show that I(K) is m-complete $\Sigma _{1}^{1},\,I(K_{\omega _{1}^{\mathit{CK}}})$ is m-complete $\Pi _{2}^{0}$ relative to Kleen's O, and $I(K_{\omega _{1}^{\mathit{CK}}+1})$ is (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  32.  13
    There is No Classification of the Decidably Presentable Structures.Matthew Harrison-Trainor - 2018 - Journal of Mathematical Logic 18 (2):1850010.
    A computable structure [Formula: see text] is decidable if, given a formula [Formula: see text] of elementary first-order logic, and a tuple [Formula: see text], we have a decision procedure to decide whether [Formula: see text] holds of [Formula: see text]. We show that there is no reasonable classification of the decidably presentable structures. Formally, we show that the index set of the computable structures with decidable presentations is [Formula: see text]-complete. We also show that for (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  33.  37
    Categoricity of Computable Infinitary Theories.W. Calvert, S. S. Goncharov, J. F. Knight & Jessica Millar - 2009 - Archive for Mathematical Logic 48 (1):25-38.
    Computable structures of Scott rank ${\omega_1^{CK}}$ are an important boundary case for structural complexity. While every countable structure is determined, up to isomorphism, by a sentence of ${\mathcal{L}_{\omega_1 \omega}}$ , this sentence may not be computable. We give examples, in several familiar classes of structures, of computable structures with Scott rank ${\omega_1^{CK}}$ whose computable infinitary theories are each ${\aleph_0}$ -categorical. General conditions are given, covering many known methods for constructing computable structures (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  34.  3
    Index Sets for Some Classes of Structures.Ekaterina B. Fokina - 2009 - Annals of Pure and Applied Logic 157 (2-3):139-147.
    For a class K of structures, closed under isomorphism, the index set is the set I of all indices for computable members of K in a universal computable numbering of all computable structures for a fixed computable language. We study the complexity of the index set of class of structures with decidable theories. We first prove the result for the class of all structures in an arbitrary finite nontrivial language. After the complexity (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  35.  15
    Effective Categoricity of Equivalence Structures.Wesley Calvert, Douglas Cenzer, Valentina Harizanov & Andrei Morozov - 2006 - Annals of Pure and Applied Logic 141 (1):61-78.
    We investigate effective categoricity of computable equivalence structures . We show that is computably categorical if and only if has only finitely many finite equivalence classes, or has only finitely many infinite classes, bounded character, and at most one finite k such that there are infinitely many classes of size k. We also prove that all computably categorical structures are relatively computably categorical, that is, have computably enumerable Scott families of existential formulas. Since all computable equivalence (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   16 citations  
  36.  13
    Computable Isomorphisms, Degree Spectra of Relations, and Scott Families.Bakhadyr Khoussainov & Richard A. Shore - 1998 - Annals of Pure and Applied Logic 93 (1-3):153-193.
    The spectrum of a relation on a computable structure is the set of Turing degrees of the image of R under all isomorphisms between and any other computable structure . The relation is intrinsically computably enumerable if its image under all such isomorphisms is c.e. We prove that any computable partially ordered set is isomorphic to the spectrum of an intrinsically c.e. relation on a computable structure. Moreover, the isomorphism can be constructed in such a way (...)
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   15 citations  
  37.  34
    Classes of Ulm Type and Coding Rank-Homogeneous Trees in Other Structures.E. Fokina, J. F. Knight, A. Melnikov, S. M. Quinn & C. Safranski - 2011 - Journal of Symbolic Logic 76 (3):846 - 869.
    The first main result isolates some conditions which fail for the class of graphs and hold for the class of Abelian p-groups, the class of Abelian torsion groups, and the special class of "rank-homogeneous" trees. We consider these conditions as a possible definition of what it means for a class of structures to have "Ulm type". The result says that there can be no Turing computable embedding of a class not of Ulm type into one of Ulm type. (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  38.  10
    Computable Categoricity and the Ershov Hierarchy.Bakhadyr Khoussainov, Frank Stephan & Yue Yang - 2008 - Annals of Pure and Applied Logic 156 (1):86-95.
    In this paper, the notions of Fα-categorical and Gα-categorical structures are introduced by choosing the isomorphism such that the function itself or its graph sits on the α-th level of the Ershov hierarchy, respectively. Separations obtained by natural graphs which are the disjoint unions of countably many finite graphs. Furthermore, for size-bounded graphs, an easy criterion is given to say when it is computable-categorical and when it is only G2-categorical; in the latter case it is not Fα-categorical for (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  39.  14
    Degrees of Bi-Embeddable Categoricity of Equivalence Structures.Nikolay Bazhenov, Ekaterina Fokina, Dino Rossegger & Luca San Mauro - 2019 - Archive for Mathematical Logic 58 (5-6):543-563.
    We study the algorithmic complexity of embeddings between bi-embeddable equivalence structures. We define the notions of computable bi-embeddable categoricity, \ bi-embeddable categoricity, and degrees of bi-embeddable categoricity. These notions mirror the classical notions used to study the complexity of isomorphisms between structures. We show that the notions of \ bi-embeddable categoricity and relative \ bi-embeddable categoricity coincide for equivalence structures for \. We also prove that computable equivalence structures have degree of bi-embeddable categoricity \, (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  40.  11
    Equivalence Structures and Isomorphisms in the Difference Hierarchy.Douglas Cenzer, Geoffrey LaForte & Jeffrey Remmel - 2009 - Journal of Symbolic Logic 74 (2):535-556.
    We examine the effective categoricity of equivalence structures via Ershov's difference hierarchy. We explore various kinds of categoricity available by distinguishing three different notions of isomorphism available in this hierarchy. We prove several results relating our notions of categoricity to computable equivalence relations: for example, we show that, for such relations, computable categoricity is equivalent to our notion of weak ω-c.e. categoricity, and that $\Delta _2^0 $ -categoricity is equivalent to our notion of graph-ω-c.e. categoricity.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  41.  15
    Computable Isomorphisms of Boolean Algebras with Operators.Bakhadyr Khoussainov & Tomasz Kowalski - 2012 - Studia Logica 100 (3):481-496.
    In this paper we investigate computable isomorphisms of Boolean algebras with operators (BAOs). We prove that there are examples of polymodal Boolean algebras with finitely many computable isomorphism types. We provide an example of a polymodal BAO such that it has exactly one computable isomorphism type but whose expansions by a constant have more than one computable isomorphism type. We also prove a general result showing that BAOs are complete with respect to the degree spectra of (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  42.  17
    Computability Theory, Semantics, and Logic Programming.Melvin Fitting - 1987 - Clarendon Press.
    This book describes computability theory and provides an extensive treatment of data structures and program correctness. It makes accessible some of the author's work on generalized recursion theory, particularly the material on the logic programming language PROLOG, which is currently of great interest. Fitting considers the relation of PROLOG logic programming to the LISP type of language.
    Direct download  
     
    Export citation  
     
    Bookmark   3 citations  
  43.  20
    Computable and Continuous Partial Homomorphisms on Metric Partial Algebras.Viggo Stoltenberg-Hansen & John V. Tucker - 2003 - Bulletin of Symbolic Logic 9 (3):299-334.
    We analyse the connection between the computability and continuity of functions in the case of homomorphisms between topological algebraic structures. Inspired by the Pour-El and Richards equivalence theorem between computability and boundedness for closed linear operators on Banach spaces, we study the rather general situation of partial homomorphisms between metric partial universal algebras. First, we develop a set of basic notions and results that reveal some of the delicate algebraic, topological and effective properties of partial algebras. Our main computability (...)
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  44.  4
    Finite Computable Dimension Does Not Relativize.Charles F. D. McCoy - 2002 - Archive for Mathematical Logic 41 (4):309-320.
    In many classes of structures, each computable structure has computable dimension 1 or $\omega$. Nevertheless, Goncharov showed that for each $n < \omega$, there exists a computable structure with computable dimension $n$. In this paper we show that, under one natural definition of relativized computable dimension, no computable structure has finite relativized computable dimension greater than 1.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  45.  16
    Σ 1 0 and Π 1 0 Equivalence Structures.Douglas Cenzer, Valentina Harizanov & Jeffrey B. Remmel - 2011 - Annals of Pure and Applied Logic 162 (7):490-503.
    We study computability theoretic properties of and equivalence structures and how they differ from computable equivalence structures or equivalence structures that belong to the Ershov difference hierarchy. Our investigation includes the complexity of isomorphisms between equivalence structures and between equivalence structures.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  46.  18
    Spectra of Structures and Relations.Valentina S. Harizanov & Russel G. Miller - 2007 - Journal of Symbolic Logic 72 (1):324 - 348.
    We consider embeddings of structures which preserve spectra: if g: M → S with S computable, then M should have the same Turing degree spectrum (as a structure) that g(M) has (as a relation on S). We show that the computable dense linear order L is universal for all countable linear orders under this notion of embedding, and we establish a similar result for the computable random graph G. Such structures are said to be spectrally (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  47.  40
    The Algebraic Structure of the Isomorphic Types of Tally, Polynomial Time Computable Sets.Yongge Wang - 2002 - Archive for Mathematical Logic 41 (3):215-244.
    We investigate the polynomial time isomorphic type structure of (the class of tally, polynomial time computable sets). We partition P T into six parts: D −, D^ − , C, S, F, F^, and study their p-isomorphic properties separately. The structures of , , and are obvious, where F, F^, and C are the class of tally finite sets, the class of tally co-finite sets, and the class of tally bi-dense sets respectively. The following results for the (...) of and will be proved, where D^ is the class of tally, co-dense, polynomial time computable sets and S is the class of tally, scatted (i.e., neither dense nor co-dense), polynomial time computable sets. 1. is a countable distributive lattice with the greatest element. 2. Infinitely many intervals in can be distinguished by first order formulas. 3. There exist infinitely many nontrivial automorphisms for . 4. is not distributive, but any interval in is a countable distributive lattice. RID=""ID="" Mathematics Subject Classification (2000): 03D15, 03D25, 03D30, 03D35, 06A06, 06B20 RID=""ID="" Key words or phrases: Computational complexity – Polynomial time – Degree structure – Lattice – Isomorphism RID=""ID="" Part of this work was done when the author was a PhD student at the University of Heidelberg under the direction of Professor Ambos-Spies. (shrink)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  48.  17
    Prime Models of Finite Computable Dimension.Pavel Semukhin - 2009 - Journal of Symbolic Logic 74 (1):336-348.
    We study the following open question in computable model theory: does there exist a structure of computable dimension two which is the prime model of its first-order theory? We construct an example of such a structure by coding a certain family of c.e. sets with exactly two one-to-one computable enumerations into a directed graph. We also show that there are examples of such structures in the classes of undirected graphs, partial orders, lattices, and integral domains.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  49.  5
    A Friedberg Enumeration of Equivalence Structures.Rodney G. Downey, Alexander G. Melnikov & Keng Meng Ng - 2017 - Journal of Mathematical Logic 17 (2):1750008.
    We solve a problem posed by Goncharov and Knight 639–681, 757]). More specifically, we produce an effective Friedberg enumeration of computable equivalence structures, up to isomorphism. We also prove that there exists an effective Friedberg enumeration of all isomorphism types of infinite computable equivalence structures.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  50.  10
    Computability in Structures Representing a Scott Set.Alex M. McAllister - 2001 - Archive for Mathematical Logic 40 (3):147-165.
    Continuing work begun in [10], we utilize a notion of forcing for which the generic objects are structures and which allows us to determine whether these “generic” structures compute certain sets and enumerations. The forcing conditions are bounded complexity types which are consistent with a given theory and are elements of a given Scott set. These generic structures will “represent” this given Scott set, in the sense that the structure has a certain weak saturation property with respect (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
1 — 50 / 999