24 found
Order:
Disambiguations
Alexander G. Melnikov [15]Alexander Melnikov [9]
See also
Alexander Melnikov
National Research University Higher School of Economics
  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.  7
    Computable Functors and Effective Interpretability.Matthew Harrison-Trainor, Alexander Melnikov, Russell Miller & Antonio Montalbán - 2017 - Journal of Symbolic Logic 82 (1):77-97.
  3.  15
    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  
  4.  5
    Punctual Categoricity and Universality.Rod Downey, Noam Greenberg, Alexander Melnikov, Keng Meng Ng & Daniel Turetsky - 2020 - Journal of Symbolic Logic 85 (4):1427-1466.
    We describe punctual categoricity in several natural classes, including binary relational structures and mono-unary functional structures. We prove that every punctually categorical structure in a finite unary language is ${\text {PA}}$-categorical, and we show that this upper bound is tight. We also construct an example of a punctually categorical structure whose degree of categoricity is $0''$. We also prove that, with a bit of work, the latter result can be pushed beyond $\Delta ^1_1$, thus showing that punctually categorical structures can (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  5.  14
    On Δ 2 0 -Categoricity of Equivalence Relations.Rod Downey, Alexander G. Melnikov & Keng Meng Ng - 2015 - Annals of Pure and Applied Logic 166 (9):851-880.
  6.  12
    Abelian P-Groups and the Halting Problem.Rodney Downey, Alexander G. Melnikov & Keng Meng Ng - 2016 - Annals of Pure and Applied Logic 167 (11):1123-1138.
  7.  23
    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   2 citations  
  8.  52
    Jump Degrees of Torsion-Free Abelian Groups.Brooke M. Andersen, Asher M. Kach, Alexander G. Melnikov & Reed Solomon - 2012 - Journal of Symbolic Logic 77 (4):1067-1100.
    We show, for each computable ordinal α and degree $\alpha > {0^{\left( \alpha \right)}}$, the existence of a torsion-free abelian group with proper α th jump degree α.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  9.  13
    Computable Abelian Groups.Alexander G. Melnikov - 2014 - Bulletin of Symbolic Logic 20 (3):315-356,.
    We provide an introduction to methods and recent results on infinitely generated abelian groups with decidable word problem.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  10.  3
    Computably Isometric Spaces.Alexander G. Melnikov - 2013 - Journal of Symbolic Logic 78 (4):1055-1085.
  11.  44
    Decidability and Computability of Certain Torsion-Free Abelian Groups.Rodney G. Downey, Sergei S. Goncharov, Asher M. Kach, Julia F. Knight, Oleg V. Kudinov, Alexander G. Melnikov & Daniel Turetsky - 2010 - Notre Dame Journal of Formal Logic 51 (1):85-96.
    We study completely decomposable torsion-free abelian groups of the form $\mathcal{G}_S := \oplus_{n \in S} \mathbb{Q}_{p_n}$ for sets $S \subseteq \omega$. We show that $\mathcal{G}_S$has a decidable copy if and only if S is $\Sigma^0_2$and has a computable copy if and only if S is $\Sigma^0_3$.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  12.  4
    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 (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  13.  11
    Punctual Definability on Structures.Iskander Kalimullin, Alexander Melnikov & Antonio Montalban - 2021 - Annals of Pure and Applied Logic 172 (8):102987.
    We study punctual categoricity on a cone and intrinsically punctual functions and obtain complete structural characterizations in terms of model-theoretic notions. As a corollary, we answer a question of Bazhenov, Downey, Kalimullin, and Melnikov by showing that relational structures are not punctually universal. We will also apply this characterisation to derive an algebraic characterisation of relatively punctually categorical mono-unary structures.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  14. Lempp s Question for Torsion Free Abelian Groups of Finite Rank.Alexander G. Melnikov - 2007 - Bulletin of Symbolic Logic 13 (2):208.
  15.  17
    Categorical Linearly Ordered Structures.Rod Downey, Alexander Melnikov & Keng Meng Ng - 2019 - Annals of Pure and Applied Logic 170 (10):1243-1255.
  16.  12
    Turing Reducibility in the Fine Hierarchy.Alexander G. Melnikov, Victor L. Selivanov & Mars M. Yamaleev - 2020 - Annals of Pure and Applied Logic 171 (7):102766.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  17.  19
    Torsion-Free Abelian Groups with Optimal Scott Families.Alexander G. Melnikov - 2018 - Journal of Mathematical Logic 18 (1):1850002.
    We prove that for any computable successor ordinal of the form α = δ + 2k there exists computable torsion-free abelian group that is relatively Δα0 -categorical and not Δα−10 -categorical. Equivalently, for any such α there exists a computable TFAG whose initial segments are uniformly described by Σαc infinitary computable formulae up to automorphism, and there is no syntactically simpler family of formulae that would capture these orbits. As far as we know, the problem of finding such optimal examples (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  18.  7
    Non-Density in Punctual Computability.Noam Greenberg, Matthew Harrison-Trainor, Alexander Melnikov & Dan Turetsky - 2021 - Annals of Pure and Applied Logic 172 (9):102985.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  19.  15
    Computable Polish Group Actions.Alexander Melnikov & Antonio Montalbán - 2018 - Journal of Symbolic Logic 83 (2):443-460.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  20.  4
    On the Complexity of Classifying Lebesgue Spaces.Tyler A. Brown, Timothy H. Mcnicholl & Alexander G. Melnikov - 2020 - Journal of Symbolic Logic 85 (3):1254-1288.
    Computability theory is used to evaluate the complexity of classifying various kinds of Lebesgue spaces and associated isometric isomorphism problems.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  21.  3
    Computability of Polish Spaces Up to Homeomorphism.Matthew Harrison-Trainor, Alexander Melnikov & Keng Meng Ng - 2020 - Journal of Symbolic Logic 85 (4):1664-1686.
    We study computable Polish spaces and Polish groups up to homeomorphism. We prove a natural effective analogy of Stone duality, and we also develop an effective definability technique which works up to homeomorphism. As an application, we show that there is a $\Delta ^0_2$ Polish space not homeomorphic to a computable one. We apply our techniques to build, for any computable ordinal $\alpha $, an effectively closed set not homeomorphic to any $0^{}$-computable Polish space; this answers a question of Nies. (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  22.  5
    Uniform Procedures in Uncountable Structures.Noam Greenberg, Alexander G. Melnikov, Julia F. Knight & Daniel Turetsky - 2018 - Journal of Symbolic Logic 83 (2):529-550.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  23.  10
    Reviewed Work(S): A New Spectrum of Recursive Models Using an Amalgamation Construction. The Journal of Symbolic Logic, Vol. 73 by Uri Andrews; A Computable N₀-Categorical Structure Whose Theory Computes True Arithmetic. The Journal of Symbolic Logic, Vol. 72 by Bakhadyr Khoussainov; Antonio Montalbán. [REVIEW]Alexander G. Melnikov - forthcoming - Association for Symbolic Logic: The Bulletin of Symbolic Logic.
    Review by: Alexander G. Melnikov The Bulletin of Symbolic Logic, Volume 19, Issue 3, Page 400-401, September 2013.
    Direct download  
     
    Export citation  
     
    Bookmark  
  24.  2
    Uri Andrews. A New Spectrum of Recursive Models Using an Amalgamation Construction. The Journal of Symbolic Logic, Vol. 73 (2011), No. 3, Pp. 883–896. - Bakhadyr Khoussainov and Antonio Montalbán. A Computable ℵ 0 -Categorical Structure Whose Theory Computes True Arithmetic. The Journal of Symbolic Logic, Vol. 72 (2010), No. 2, Pp. 728–740. [REVIEW]Alexander G. Melnikov - 2013 - Bulletin of Symbolic Logic 19 (3):400-401.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark