19 found
Order:
Disambiguations
Nikolay Bazhenov [18]Nikolay A. Bazhenov [1]
  1.  15
    Foundations of online structure theory.Nikolay Bazhenov, Rod Downey, Iskander Kalimullin & Alexander Melnikov - 2019 - Bulletin of Symbolic Logic 25 (2):141-181.
    The survey contains a detailed discussion of methods and results in the new emerging area of online “punctual” structure theory. We also state several open problems.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  2.  16
    Automatic and polynomial-time algebraic structures.Nikolay Bazhenov, Matthew Harrison-Trainor, Iskander Kalimullin, Alexander Melnikov & Keng Meng Ng - 2019 - Journal of Symbolic Logic 84 (4):1630-1669.
    A structure is automatic if its domain, functions, and relations are all regular languages. Using the fact that every automatic structure is decidable, in the literature many decision problems have been solved by giving an automatic presentation of a particular structure. Khoussainov and Nerode asked whether there is some way to tell whether a structure has, or does not have, an automatic presentation. We answer this question by showing that the set of Turing machines that represent automata-presentable structures is ${\rm{\Sigma (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  3.  25
    Degrees of categoricity and spectral dimension.Nikolay A. Bazhenov, Iskander Sh Kalimullin & Mars M. Yamaleev - 2018 - Journal of Symbolic Logic 83 (1):103-116.
    A Turing degreedis the degree of categoricity of a computable structure${\cal S}$ifdis the least degree capable of computing isomorphisms among arbitrary computable copies of${\cal S}$. A degreedis the strong degree of categoricity of${\cal S}$ifdis the degree of categoricity of${\cal S}$, and there are computable copies${\cal A}$and${\cal B}$of${\cal S}$such that every isomorphism from${\cal A}$onto${\cal B}$computesd. In this paper, we build a c.e. degreedand a computable rigid structure${\cal M}$such thatdis the degree of categoricity of${\cal M}$, butdis not the strong degree of categoricity (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  4.  23
    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 \, or \. We furthermore obtain results (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  5. Degrees of bi-embeddable categoricity.Luca San Mauro, Nikolay Bazhenov, Ekaterina Fokina & Dino Rossegger - 2021 - Computability 1 (10):1-16.
    We investigate the complexity of embeddings between bi-embeddable structures. In analogy with categoricity spectra, we define the bi-embeddable categoricity spectrum of a structure A as the family of Turing degrees that compute embeddings between any computable bi-embeddable copies of A; the degree of bi-embeddable categoricity of A is the least degree in this spectrum (if it exists). We extend many known results about categoricity spectra to the case of bi-embeddability. In particular, we exhibit structures without degree of bi-embeddable categoricity, and (...)
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  6.  22
    Categoricity Spectra for Polymodal Algebras.Nikolay Bazhenov - 2016 - Studia Logica 104 (6):1083-1097.
    We investigate effective categoricity for polymodal algebras. We prove that the class of polymodal algebras is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations. In particular, this implies that every categoricity spectrum is the categoricity spectrum of a polymodal algebra.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  7.  9
    Classifying equivalence relations in the Ershov hierarchy.Nikolay Bazhenov, Manat Mustafa, Luca San Mauro, Andrea Sorbi & Mars Yamaleev - 2020 - Archive for Mathematical Logic 59 (7-8):835-864.
    Computably enumerable equivalence relations received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility \. This gives rise to a rich degree structure. In this paper, we lift the study of c-degrees to the \ case. In doing so, we rely on the Ershov hierarchy. For any notation a for a non-zero computable ordinal, we prove several algebraic properties of the degree structure induced by \ on the \ equivalence relations. (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  8. Computable bi-embeddable categoricity.Luca San Mauro, Nikolay Bazhenov, Ekaterina Fokina & Dino Rossegger - 2018 - Algebra and Logic 5 (57):392-396.
    We study the algorithmic complexity of isomorphic embeddings between computable structures.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  9.  6
    Primitive recursive equivalence relations and their primitive recursive complexity.Luca San Mauro, Nikolay Bazhenov, Keng Meng Ng & Andrea Sorbi - forthcoming - Computability.
    The complexity of equivalence relations has received much attention in the recent literature. The main tool for such endeavour is the following reducibility: given equivalence relations R and S on natural numbers, R is computably reducible to S if there is a computable function f:ω→ω that induces an injective map from R-equivalence classes to S-equivalence classes. In order to compare the complexity of equivalence relations which are computable, researchers considered also feasible variants of computable reducibility, such as the polynomial-time reducibility. (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  10.  5
    Calculating the mind-change complexity of learning algebraic structures.Luca San Mauro, Nikolay Bazhenov & Vittorio Cipriani - 2022 - In Ulrich Berger, Johanna N. Y. Franklin, Florin Manea & Arno Pauly (eds.), Revolutions and Revelations in Computability. Cham, Svizzera: pp. 1-12.
    This paper studies algorithmic learning theory applied to algebraic structures. In previous papers, we have defined our framework, where a learner, given a family of structures, receives larger and larger pieces of an arbitrary copy of a structure in the family and, at each stage, is required to output a conjecture about the isomorphism type of such a structure. The learning is successful if there is a learner that eventually stabilizes to a correct conjecture. Here, we analyze the number of (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  11.  7
    On the effective universality of mereological theories.Nikolay Bazhenov & Hsing-Chien Tsai - 2022 - Mathematical Logic Quarterly 68 (1):48-66.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark  
  12.  3
    On the Turing complexity of learning finite families of algebraic structures.Luca San Mauro & Nikolay Bazhenov - 2021 - Journal of Logic and Computation 7 (31):1891-1900.
    In previous work, we have combined computable structure theory and algorithmic learning theory to study which families of algebraic structures are learnable in the limit (up to isomorphism). In this paper, we measure the computational power that is needed to learn finite families of structures. In particular, we prove that, if a family of structures is both finite and learnable, then any oracle which computes the Halting set is able to achieve such a learning. On the other hand, we construct (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  13.  3
    Rogers semilattices of limitwise monotonic numberings.Nikolay Bazhenov, Manat Mustafa & Zhansaya Tleuliyeva - 2022 - Mathematical Logic Quarterly 68 (2):213-226.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  14.  11
    Elementary theories and hereditary undecidability for semilattices of numberings.Nikolay Bazhenov, Manat Mustafa & Mars Yamaleev - 2019 - Archive for Mathematical Logic 58 (3-4):485-500.
    A major theme in the study of degree structures of all types has been the question of the decidability or undecidability of their first order theories. This is a natural and fundamental question that is an important goal in the analysis of these structures. In this paper, we study decidability for theories of upper semilattices that arise from the theory of numberings. We use the following approach: given a level of complexity, say \, we consider the upper semilattice \ of (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  15.  2
    Computable Heyting Algebras with Distinguished Atoms and Coatoms.Nikolay Bazhenov - forthcoming - Journal of Logic, Language and Information:1-16.
    The paper studies Heyting algebras within the framework of computable structure theory. We prove that the class K containing all Heyting algebras with distinguished atoms and coatoms is complete in the sense of the work of Hirschfeldt et al. :71-113, 2002). This shows that the class K is rich from the computability-theoretic point of view: for example, every possible degree spectrum can be realized by a countable structure from K. In addition, there is no simple syntactic characterization of computably categorical (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  16.  2
    Complexity of $$\Sigma ^0_n$$-classifications for definable subsets.Svetlana Aleksandrova, Nikolay Bazhenov & Maxim Zubkov - 2023 - Archive for Mathematical Logic 62 (1):239-256.
    For a non-zero natural number n, we work with finitary $$\Sigma ^0_n$$ -formulas $$\psi (x)$$ without parameters. We consider computable structures $${\mathcal {S}}$$ such that the domain of $${\mathcal {S}}$$ has infinitely many $$\Sigma ^0_n$$ -definable subsets. Following Goncharov and Kogabaev, we say that an infinite list of $$\Sigma ^0_n$$ -formulas is a $$\Sigma ^0_n$$ -classification for $${\mathcal {S}}$$ if the list enumerates all $$\Sigma ^0_n$$ -definable subsets of $${\mathcal {S}}$$ without repetitions. We show that an arbitrary computable $${\mathcal {S}}$$ (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  17.  2
    Approximating Approximate Reasoning: Fuzzy Sets and the Ershov Hierarchy.Nikolay Bazhenov, Manat Mustafa, Sergei Ospichev & Luca San Mauro - 2021 - In Sujata Ghosh & Thomas Icard (eds.), Logic, Rationality, and Interaction: 8th International Workshop, Lori 2021, Xi’an, China, October 16–18, 2021, Proceedings. Springer Verlag. pp. 1-13.
    Computability theorists have introduced multiple hierarchies to measure the complexity of sets of natural numbers. The Kleene Hierarchy classifies sets according to the first-order complexity of their defining formulas. The Ershov Hierarchy classifies Δ20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varDelta ^0_2$$\end{document} sets with respect to the number of mistakes that are needed to approximate them. Biacino and Gerla extended the Kleene Hierarchy to the realm of fuzzy sets, whose membership functions range in a complete lattice L. In (...)
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark  
  18.  1
    Learning families of algebraic structures from informant.Luca San Mauro, Nikolay Bazhenov & Ekaterina Fokina - 2020 - Information And Computation 1 (275):104590.
    We combine computable structure theory and algorithmic learning theory to study learning of families of algebraic structures. Our main result is a model-theoretic characterization of the learning type InfEx_\iso, consisting of the structures whose isomorphism types can be learned in the limit. We show that a family of structures is InfEx_\iso-learnable if and only if the structures can be distinguished in terms of their \Sigma^2_inf-theories. We apply this characterization to familiar cases and we show the following: there is an infinite (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  19.  3
    On bi-embeddable categoricity of algebraic structures.Nikolay Bazhenov, Dino Rossegger & Maxim Zubkov - 2022 - Annals of Pure and Applied Logic 173 (3):103060.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark