26 found
Order:
  1.  15
    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 given (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   35 citations  
  2.  26
    Computable Models of Theories with Few Models.Bakhadyr Khoussainov, Andre Nies & Richard A. Shore - 1997 - Notre Dame Journal of Formal Logic 38 (2):165-178.
    In this paper we investigate computable models of -categorical theories and Ehrenfeucht theories. For instance, we give an example of an -categorical but not -categorical theory such that all the countable models of except its prime model have computable presentations. We also show that there exists an -categorical but not -categorical theory such that all the countable models of except the saturated model, have computable presentations.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   19 citations  
  3.  25
    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 that the image of (...)
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   15 citations  
  4.  38
    Computably Categorical Structures and Expansions by Constants.Peter Cholak, Sergey Goncharov, Bakhadyr Khoussainov & Richard A. Shore - 1999 - Journal of Symbolic Logic 64 (1):13-37.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  5. A Computably Categorical Structure Whose Expansion by a Constant has Infinite Computable Dimension.Denis R. Hirschfeldt, Bakhadyr Khoussainov & Richard A. Shore - 2003 - Journal of Symbolic Logic 68 (4):1199-1241.
    Cholak, Goncharov, Khoussainov, and Shore [1] showed that for each k > 0 there is a computably categorical structure whose expansion by a constant has computable dimension k. We show that the same is true with k replaced by ω. Our proof uses a version of Goncharov's method of left and right operations.
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  6.  33
    Graphs Realised by R.E. Equivalence Relations.Alexander Gavruskin, Sanjay Jain, Bakhadyr Khoussainov & Frank Stephan - 2014 - Annals of Pure and Applied Logic 165 (7-8):1263-1290.
    We investigate dependence of recursively enumerable graphs on the equality relation given by a specific r.e. equivalence relation on ω. In particular we compare r.e. equivalence relations in terms of graphs they permit to represent. This defines partially ordered sets that depend on classes of graphs under consideration. We investigate some algebraic properties of these partially ordered sets. For instance, we show that some of these partial ordered sets possess atoms, minimal and maximal elements. We also fully describe the isomorphism (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  7.  13
    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 any recursive (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  8.  11
    An Uncountably Categorical Theory Whose Only Computably Presentable Model Is Saturated.Denis R. Hirschfeldt, Bakhadyr Khoussainov & Pavel Semukhin - 2006 - Notre Dame Journal of Formal Logic 47 (1):63-71.
    We build an א₁-categorical but not א₀-categorical theory whose only computably presentable model is the saturated one. As a tool, we introduce a notion related to limitwise monotonic functions.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  9.  4
    Model-Theoretic Complexity of Automatic Structures.Bakhadyr Khoussainov & Mia Minnes - 2009 - Annals of Pure and Applied Logic 161 (3):416-426.
  10.  65
    Linear Orders with Distinguished Function Symbol.Douglas Cenzer, Barbara F. Csima & Bakhadyr Khoussainov - 2009 - Archive for Mathematical Logic 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.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  11.  18
    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 structures, computable dimensions, expansions (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  12.  16
    Decidable Kripke Models of Intuitionistic Theories.Hajime Ishihara, Bakhadyr Khoussainov & Anil Nerode - 1998 - Annals of Pure and Applied Logic 93 (1-3):115-123.
    In this paper we introduce effectiveness into model theory of intuitionistic logic. The main result shows that any computable theory T of intuitionistic predicate logic has a Kripke model with decidable forcing such that for any sentence φ, φ is forced in the model if and only if φ is intuitionistically deducible from T.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  13.  27
    P 0 1 \Pi^0_1 -Presentations of Algebras.Bakhadyr Khoussainov, Theodore Slaman & Pavel Semukhin - 2006 - Archive for Mathematical Logic 45 (6):769-781.
    In this paper we study the question as to which computable algebras are isomorphic to non-computable \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Pi_{1}^{0}$$\end{document}-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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Pi_{1}^{0}$$\end{document}-presentations. On the other hand, many of this structures fail to have non-computable \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Sigma_{1}^{0}$$\end{document}-presentation.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  14.  5
    Recursive Unary Algebras and Trees.Bakhadyr Khoussainov - 1994 - Annals of Pure and Applied Logic 67 (1-3):213-268.
    A unary algebra is an algebraic system A = , where ƒ 0 ,…,ƒ n are unary operations on A and n ∈ ω. In the paper we develop the theory of effective unary algebras. We investigate well-known questions of constructive model theory with respect to the class of unary algebras. In the paper we construct unary algebras with a finite number of recursive isomorphism types. We give the notions of program, uniform, and algebraic dimensions of models, and then we (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  15.  20
    On Some Games Played on Finite Graphs.Bakhadyr Khoussainov - 2002 - Bulletin of the Section of Logic 31 (2):71-79.
  16.  20
    $$\Pi^0_1$$ -Presentations of Algebras.Bakhadyr Khoussainov, Theodore Slaman & Pavel Semukhin - 2006 - Archive for Mathematical Logic 45 (6):769-781.
    In this paper we study the question as to which computable algebras are isomorphic to non-computable $\Pi_{1}^{0}$ -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 $\Pi_{1}^{0}$ -presentations. On the other hand, many of this structures fail to have non-computable $\Sigma_{1}^{0}$ -presentation.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  17.  23
    A Computable ℵ 0 -Categorical Structure Whose Theory Computes True Arithmetic.Bakhadyr Khoussainov & Antonio Montalbán - 2010 - Journal of Symbolic Logic 75 (2):728-740.
    We construct a computable ℵ0-categorical structure whose first order theory is computably equivalent to the true first order theory of arithmetic.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  18.  11
    Randomness, Computability and Algebraic Specifications.Bakhadyr Khoussainov - 1998 - Annals of Pure and Applied Logic 91 (1):1-15.
    This paper shows how the notion of randomness defines, in a natural way, an algebra. It turns out that the algebra is computably enumerable and finitely generated. The paper investigates algebraic and effective properties of this algebra.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  19.  9
    Linear Orders Realized by C.E. Equivalence Relations.Ekaterina Fokina, Bakhadyr Khoussainov, Pavel Semukhin & Daniel Turetsky - 2016 - Journal of Symbolic Logic 81 (2):463-482.
  20.  10
    1995–1996 Annual Meeting of the Association for Symbolic Logic.Tomek Bartoszynski, Harvey Friedman, Geoffrey Hellman, Bakhadyr Khoussainov, Phokion G. Kolaitis, Richard Shore, Charles Steinhorn, Mirna Dzamonja, Itay Neeman & Slawomir Solecki - 1996 - Bulletin of Symbolic Logic 2 (4):448-472.
  21.  6
    On Complexity of Ehrenfeucht–Fraïssé Games.Bakhadyr Khoussainov & Jiamou Liu - 2009 - Annals of Pure and Applied Logic 161 (3):404-415.
    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 (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  22.  5
    Deterministic Automata Simulation, Universality and Minimality.Cristian Calude, Elena Calude & Bakhadyr Khoussainov - 1997 - Annals of Pure and Applied Logic 90 (1):263-276.
    Finite automata have been recently used as alternative, discrete models in theoretical physics, especially in problems related to the dichotomy between endophysical/intrinsic and exophysical/ extrinsic perception . These studies deal with Moore experiments; the main result states that it is impossible to determine the initial state of an automaton, and, consequently, a discrete model of Heisenberg uncertainty has been suggested. For this aim the classical theory of finite automata — which considers automata with initial states — is not adequate, and (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  23.  5
    Erratum to “Computable Isomorphisms, Degree Spectra of Relations, and Scott Families” [Ann. Pure Appl. Logic 93 (1998) 153–193]. [REVIEW]Bakhadyr Khoussainov & Richard A. Shore - 1999 - Annals of Pure and Applied Logic 98 (1-3):297-298.
  24.  4
    Games with Unknown Past.Bakhadyr Khoussainov, Alexander Yakhnis & Vladimir Yakhnis - 1998 - Mathematical Logic Quarterly 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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  25. InlineEquation ID=" IEq4"> EquationSource Format=" TEX"> ImageObject Color=" BlackWhite" FileRef=" 153200613ArticleIEq4. Gif" Format=" GIF" Rendition=" HTML" Type=" Linedraw"/>-Presentations of Algebras. [REVIEW]Bakhadyr Khoussainov, Theodore Slaman & Pavel Semukhin - 2006 - Archive for Mathematical Logic 45 (6):769.
     
    Export citation  
     
    Bookmark  
  26. On Computability Theoretic Properties of Structures and Their Cartesian Products.Bakhadyr Khoussainov - 2000 - Mathematical Logic Quarterly 46 (4):467-476.
    In this paper we show that for any set X ⊆ ω there exists a structure [MATHEMATICAL SCRIPT CAPITAL A] that has no presentation computable in X such that [MATHEMATICAL SCRIPT CAPITAL A]2 has a computable presentation. We also show that there exists a structure [MATHEMATICAL SCRIPT CAPITAL A] with infinitely many computable isomorphism types such that [MATHEMATICAL SCRIPT CAPITAL A]2 has exactly one computable isomorphism type.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark