Publications

Surveys

• Foundations of online structure theory, Bull. Symb. Log., 2019, 25:2, 141-181. With Rod Downey, Iskander Kalimullin, and Alexander Melnikov. The preprint version.
• Categoricity spectra of computable structures, Journal of Mathematical Sciences, 2021, 256:1, 34-50. Full-text access. This is the translation of the paper published in 2018.

Editorials

• On the main scientific achievements of Victor Selivanov, Computability, 2023, 12:4, 301-314. With Takayuki Kihara, Svetlana Selivanova, and Dieter Spreen.

Primitive recursive and polynomial-time structures, punctual computability

• Primitive recursive reverse mathematics, Ann. Pure Appl. Logic, 2024, 175:1, article 103354. With Marta Fiori Carones, Lu Liu, and Alexander Melnikov. [arXiv:2210.13080]
• Primitive recursive equivalence relations and their primitive recursive complexity, Computability, 2022, 11:3-4, 187-221. With Keng Meng Ng, Luca San Mauro, and Andrea Sorbi. [arXiv:2109.04055]
• Rogers semilattices of punctual numberings, Math. Struct. Comput. Sci., 2022, 32:2, 164-188. With Manat Mustafa and Sergei Ospichev. This is a journal version of the TAMC-2020 conference paper «Semilattices of punctual numberings»
• Punctual categoricity spectra of computably categorical structures, Algebra Logic, 2021, 60:3, 223-228. With Iskander Kalimullin. Full-text access.
• Online presentations of finitely generated structures, Theor. Comput. Sci., 2020, 844, 195-216. With Iskander Kalimullin, Alexander Melnikov, and Keng Meng Ng. [preprint version].
• Semilattices of punctual numberings, in Proceedings of TAMC-2020 (Lect. Notes Comput. Sci., 12337), 1-12. With Manat Mustafa and Sergei Ospichev. [pdf download] The final authenticated version is available online at https://doi.org/10.1007/978-3-030-59267-7_1
• Definable subsets of polynomial-time algebraic structures, in Proceedings of CSR-2020 (Lect. Notes Comput. Sci., 12159), 142-154. [pdf download] The final authenticated version is available online at https://doi.org/10.1007/978-3-030-50026-9_10
• Automatic and polynomial-time algebraic structures, J. Symb. Log., 2019, 84:4, 1630-1669. With Matthew Harrison-Trainor, Iskander Kalimullin, Alexander Melnikov, and Keng Meng Ng.

Computable topological spaces, and related topics

• Every Δ⁰₂ Polish space is computable topological, Proc. Am. Math. Soc., in press. With Alexander Melnikov and Keng Meng Ng.
• A Lopez-Escobar theorem for continuous domains, J. Symb. Logic, published online. With Ekaterina Fokina, Dino Rossegger, Alexandra Soskova, and Stefan Vatev.
• Computable Stone spaces, Ann. Pure Appl. Logic, 2023, 174:9, article 103304. With Matthew Harrison-Trainor and Alexander Melnikov. [arXiv:2107.01536]

Algorithmic learning

• Learning algebraic structures with the help of Borel equivalence relations, Theor. Comput. Sci., 2023, 951, article 113762. With Vittorio Cipriani and Luca San Mauro. [arXiv:2110.14512]
• Calculating the mind change complexity of learning algebraic structures, in Proceedings of CiE-2022 (Lect. Notes Comput. Sci., 13359), 1-12. With Vittorio Cipriani and Luca San Mauro.
• On the Turing complexity of learning finite families of algebraic structures, J. Log. Comput., 2021, 31:7, 1891-1900. With Luca San Mauro. [arXiv:2106.14515]
• Learning families of algebraic structures from informant, Inf. Comput., 2020, 275, article id 104590. With Ekaterina Fokina and Luca San Mauro. [arXiv:1905.01601]

Equivalence relations, computably enumerable structures, and related topics

• Computably enumerable equivalence relations via primitive recursive reductions, J. Log. Comput., published online. With Birzhan Kalmurzayev and Alibek Iskakov.
• On diagonal functions for equivalence relations, Arch. Math. Logic, 2024, 63:3-4, 259-278. With Serikzhan Badaev, Birzhan Kalmurzayev, and Manat Mustafa. Full-text access.
• A note on joins and meets for positive linear preorders, Siberian Electronic Mathematical Reports, 2023, 20:1, 1-16. With Birzhan Kalmurzayev and Maxim Zubkov.
• On universal positive graphs, Sib. Math. J., 2023, 64:1, 83-93. With Birzhan Kalmurzayev and Daryn Alish.
• Well-orders realized by c.e. equivalence relations, in Proceedings of CiE-2022 (Lect. Notes Comput. Sci., 13359), 13-23. With Maxim Zubkov.
• Computable reducibility for computable linear orders of type ω, Journal of Mathematical Sciences, 2022, 267:4, 429-443. With Aknur Askarbekkyzy and Birzhan Kalmurzayev.
• Index sets for classes of positive preorders, Algebra Logic, 2022, 61:1, 30-53. With Birzhan Kalmurzayev and Mariya Torebekova.
• Computable embeddability for algebraic structures, Asian-European J. Math., 2022, 15:7, article id 2250126. With Manat Mustafa.
• On the computational content of the theory of Borel equivalence relations, Oberwolfach Preprint OWP-2021-06. With Benoit Monin, Luca San Mauro, and Rafael Zamora.
• The structure of computably enumerable preorder relations, Algebra Logic, 2020, 59:3, 201-215. With Serikzhan Badaev and Birzhan Kalmurzaev. Full-text access.
• Classifying equivalence relations in the Ershov hierarchy, Arch. Math. Logic, 2020, 59:7-8, 835-864. With Manat Mustafa, Luca San Mauro, Andrea Sorbi, and Mars Yamaleev.
• Minimal equivalence relations in hyperarithmetical and analytical hierarchies, Lobachevskii J. Math., 2020, 41:2, 145-150. With Manat Mustafa, Luca San Mauro, and Mars Yamaleev. Full-text access.
• Weakly precomplete equivalence relations in the Ershov hierarchy, Algebra Logic, 2019, 58:3, 199-213. With Birzhan Kalmurzaev. Full-text access.
• Computable isomorphisms of distributive lattices, in Proceedings of TAMC-2019 (Lect. Notes Comput. Sci., 11436), 28-41. With Manat Mustafa and Mars Yamaleev.
• On dark computably enumerable equivalence relations, Sib. Math. J., 2018, 59:1, 22-30. With Birzhan Kalmurzaev. Full-text access.
• Boolean algebras realized by c.e. equivalence relations, Siberian Electronic Mathematical Reports, 2017, 14, 848-855. With Manat Mustafa, Frank Stephan, and Mars Yamaleev.

The theory of numberings, and related topics

• Isomorphism types of Rogers semilattices in the analytical hierarchy, in Aspects of Computation and Automata Theory with Applications (Lect. Notes Ser., Inst. Math. Sci., Natl. Univ. Singapore, vol. 42, 2023), 97-114. With Sergei Ospichev and Mars Yamaleev. [arXiv:1912.05226]
• Complexity of Σ⁰_n-classifications for definable subsets, Arch. Math. Logic, 2023, 62:1-2, 239-256. With Svetlana Aleksandrova and Maxim Zubkov. Full-text access.
• Minimal generalized computable numberings and families of positive preorders, Algebra Logic, 2022, 61:3, 188-206. With Assylbek Issakhov, Birzhan Kalmurzayev, and Fariza Rakymzhankyzy.
• On two types of concept lattices in the theory of numberings, in Proceedings of TAMC-2022 (Lect. Notes Comput. Sci., 13571), 79-92. With Manat Mustafa and Anvar Nurakunov.
• Rogers semilattices of limitwise monotonic numberings, Math. Log. Q., 2022, 68:2, 213-226. With Manat Mustafa and Zhansaya Tleuliyeva.
• Theories of Rogers semilattices of analytical numberings, Lobachevskii J. Math., 2021, 42:4, 701-708. With Manat Mustafa and Zhansaya Tleuliyeva. Full-text access.
• On universal pairs in the Ershov hierarchy, Sib. Math. J., 2021, 62:1, 23-31. With Manat Mustafa and Sergei Ospichev. Full-text access.
• Numberings in the analytical hierarchy, Algebra Logic, 2020, 59:5, 404-407. With Manat Mustafa, Sergei Ospichev, and Mars Yamaleev. Full-text access.
• Bounded reducibility for computable numberings, in Proceedings of CiE-2019 (Lect. Notes Comput. Sci., 11558), 96-107. With Manat Mustafa and Sergei Ospichev.
• Elementary theories and hereditary undecidability for semilattices of numberings, Arch. Math. Logic, 2019, 58:3-4, 485-500. With Manat Mustafa and Mars Yamaleev. Full-text access.
• Rogers semilattices for families of equivalence relations in the Ershov hierarchy, Sib. Math. J., 2019, 60:2, 223-234. With Birzhan Kalmurzayev. Full-text access.

Degree spectra of relations

• Degree spectra, and relative acceptability of notations, in Proceedings of CSL 2023 (LIPIcs – Leibniz Int. Proc. Inform., 252), 11:1-11:20. With Dariusz Kalociński.
• Intrinsic complexity of recursive functions on natural numbers with standard order, in Proceedings of STACS-2022 (LIPIcs – Leibniz Int. Proc. Inform., 219), 8:1-8:20. With Dariusz Kalociński and Michał Wrocławski.

Computable groups

• Decompositions of decidable abelian groups, Int. J. Algebra Comput., 2020, 30:1, 49-90. With Sergey Goncharov and Alexander Melnikov.
• The index set of the groups autostable relative to strong constructivizations, Sib. Math. J., 2017, 58:1, 72-77. With Sergey Goncharov and Margarita Marchuk. Full-text access.

HKSS-Universal classes of structures

• Computable Heyting algebras with distinguished atoms and coatoms, J. Logic Lang. Inf., 2023, 32:1, 3-18. This is a journal version of the ICLA-2021 conference paper «On computability-theoretic properties of Heyting algebras». Full-text access.
• On the effective universality of mereological theories, Math. Log. Q., 2022, 68:1, 48-66. With Hsing-Chien Tsai.
• HKSS-Completeness of modal algebras, Siberian Electronic Mathematical Reports, 2021, 18:2, 923-930.
• On computability-theoretic properties of Heyting algebras, in Proceedings of ICLA-2021, 25-29.
• Computable contact algebras, Fundam. Inform., 2019, 167:4, 257-269.
• Categoricity spectra for polymodal algebras, Studia Logica, 2016, 104:6, 1083-1097. Full-text access.

Bi-embeddable structures

• On bi-embeddable categoricity of algebraic structures, Ann. Pure Appl. Logic, 2022, 173:3, article id 103060. With Dino Rossegger and Maxim Zubkov. [arXiv:2005.07829]
• Degrees of bi-embeddable categoricity, Computability, 2021, 10:1, 1-16. With Ekaterina Fokina, Dino Rossegger, and Luca San Mauro. [arXiv:1907.03553]
• Degrees of bi-embeddable categoricity of equivalence structures, Arch. Math. Logic, 2019, 58:5-6, 543-563. With Ekaterina Fokina, Dino Rossegger, and Luca San Mauro. Full-text access.
• Computable bi-embeddable categoricity, Algebra Logic, 2018, 57:5, 392-396. With Ekaterina Fokina, Dino Rossegger, and Luca San Mauro. Full-text access.
• Computable bi-embeddable categoricity of equivalence structures, in Proceedings of the 11th Panhellenic Logic Symposium (Delphi, Greece, July 12-16, 2017), 126-132. With Ekaterina Fokina, Dino Rossegger, and Luca San Mauro.

Computable embeddings for classes of structures

• Computable embeddings for pairs of linear orders, Algebra Logic, 2021, 60:3, 163-187. With Hristo Ganchev and Stefan Vatev. Full-text access. This is a journal version of the CiE-2019 conference paper «Effective embeddings for pairs of structures»
• A note on computable embeddings for ordinals and their reverses, in Proceedings of CiE-2020 (Lect. Notes Comput. Sci., 12098), 1-13. With Stefan Vatev.
• Effective embeddings for pairs of structures, in Proceedings of CiE-2019 (Lect. Notes Comput. Sci., 11558), 84-95. With Hristo Ganchev and Stefan Vatev.
• Turing computable embeddings, computable infinitary equivalence, and linear orders [pdf download], in Proceedings of CiE-2017 (Lect. Notes Comput. Sci., 10307), 141-151. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-58741-7_15

Effective categoricity

• On categoricity spectra for locally finite graphs, Sib. Math. J., 2021, 62:5, 796-804. With Margarita Marchuk. Full-text access.
• Strong degrees of categoricity and weak density, Lobachevskii J. Math., 2020, 41:9, 1630-1639. With Iskander Kalimullin and Mars Yamaleev. Full-text access.
• Linear orders and categoricity spectra, in Proceedings of the 14th and 15th Asian Logic Conferences. Singapore: World Scientific, 2019. P. 35-52.
• Degrees of categoricity and spectral dimension, J. Symb. Log., 2018, 83:1, 103-116. With Iskander Kalimullin and Mars Yamaleev.
• Degrees of autostability for prime Boolean algebras, Algebra Logic, 2018, 57:2, 98-114. With Margarita Marchuk. Full-text access.
• Degrees of categoricity for prime and homogeneous models, in Proceedings of CiE-2018 (Lect. Notes Comput. Sci., 10936), 40-49. With Margarita Marchuk.
• Computability of distributive lattices, Sib. Math. J., 2017, 58:6, 959-970. With Andrey Frolov, Iskander Kalimullin, and Alexander Melnikov. Full-text access.
• Effective categoricity for distributive lattices and Heyting algebras, Lobachevskii J. Math., 2017, 38:4, 600-614. Full-text access.
• Degrees of categoricity of rigid structures, in Proceedings of CiE-2017 (Lect. Notes Comput. Sci., 10307), 152-161. With Mars Yamaleev.
• A note on effective categoricity for linear orderings, in Proceedings of TAMC-2017 (Lect. Notes Comput. Sci., 10185), 85-96.
• Degrees of autostability for linear orders and linearly ordered abelian groups, Algebra Logic, 2016, 55:4, 257-273. Full-text access.
• Degrees of categoricity vs. strong degrees of categoricity, Algebra Logic, 2016, 55:2, 173-177. With Iskander Kalimullin and Mars Yamaleev. Full-text access.
• The branching theorem and computable categoricity in the Ershov hierarchy, Algebra Logic, 2015, 54:2, 91-104. Full-text access
• Autostability spectra for Boolean algebras, Algebra Logic, 2014, 53:6, 502-505. Full-text access.
• Δ⁰₂-categoricity of Boolean algebras, J. Math. Sci., 2014, 203:4, 444-454. Full-text access.
• Hyperaritmetical categoricity of Boolean algebras of type B(ω^α×η), J. Math. Sci., 2014, 202:1, 40-49. Full-text access
• Degrees of categoricity for superatomic Boolean algebras, Algebra Logic, 2013, 52:3, 179-187. Full-text access

Effective categoricity for decidable structures (autostability relative to strong constructivizations)

• A note on decidable categoricity and index sets, Siberian Electronic Mathematical Reports, 2020, 17, 1013-1026. With Margarita Marchuk.
• Constructing decidable graphs from decidable structures, Algebra Logic, 2019, 58:5, 369-382. With Matthew Harrison-Trainor. Full-text access.
• Degrees of autostability relative to strong constructivizations of graphs, Sib. Math. J., 2018, 59:4, 565-577. With Margarita Marchuk. Full-text access
• Autostability spectra for decidable structures, Math. Struct. Comput. Sci., 2018, 28:3, 392-411.
• Degrees of autostability relative to strong constructivizations for Boolean algebras, Algebra Logic, 2016, 55:2, 87-102. Full-text access.
• The index set of linear orderings that are autostable relative to strong constructivizations [in Russian], Vestnik Novosibirsk. Gos. Univ., Ser. Mat. Mekh. Inform., 2015, 15:3, 51-60. With Sergey Goncharov and Margarita Marchuk. English translation: Index set of linear orderings that are autostable relative to strong constructivizations, J. Math. Sci., 2017, 221:6, 840-848. Full-text access.
• Index sets of autostable relative to strong constructivizations constructive models for familiar classes, Dokl. Math., 2015, 92:2, 525-527. With Sergey Goncharov and Margarita Marchuk. Full-text access.
• Prime model with no degree of autostability relative to strong constructivizations [pdf download], in Proceedings of CiE-2015 (Lect. Notes Comput. Sci., 9136), 117-126.
  The final publication is available at link.springer.com, DOI 10.1007/978-3-319-20028-6_12 .
• The index set of Boolean algebras autostable relative to strong constructivizations, Sib. Math. J., 2015, 56:3, 393-404. With Sergey Goncharov and Margarita Marchuk. Full-text access.

Other works on computability theory

• Cantor-Bendixson ranks for almost prime models, in Aspects of Computation and Automata Theory with Applications (Lect. Notes Ser., Inst. Math. Sci., Natl. Univ. Singapore, vol. 42, 2023), 79-95. With Margarita Marchuk.
• How to approximate fuzzy sets: mind-changes and the Ershov hierarchy, Synthese, 2023, 201:2, article 55. With Manat Mustafa, Sergei Ospichev, and Luca San Mauro. This is a journal version of the LORI-2021 conference paper «Approximating approximate reasoning: Fuzzy sets and the Ershov hierarchy»
• Approximating approximate reasoning: Fuzzy sets and the Ershov hierarchy, in Proceedings of LORI 2021 (Lect. Notes Comput. Sci., 13039), 1-13. With Manat Mustafa, Sergei Ospichev, and Luca San Mauro. [arXiv:2107.10033].
• A note on computable distinguishing colorings, Lobachevskii J. Math., 2021, 42:4, 693-700. With Noam Greenberg, Alexander Melnikov, Russell Miller, and Keng Meng Ng. Full-text access.

The theory of lists

• On decidability of list structures, Sib. Math. J., 2019, 60:3, 377-388. With Svetlana Aleksandrova. Full-text access.
• Automatic structures and the theory of lists, Siberian Electronic Mathematical Reports, 2015, 12, 714-722.

Boolean algebras with distinguished endomorphisms

• Boolean algebras with distinguished endomorphisms and generating trees [in Russian], Vestnik Novosibirsk. Gos. Univ., Ser. Mat. Mekh. Inform., 2015, 15:1, 29-44. English translation: Boolean algebras with distinguished endomorphisms and generating trees, J. Math. Sci., 2016, 215:4, 460-474. Full-text access.
• D.c.e. degrees of categoricity for Boolean algebras with a distingushed automorphism [in Russian], Vestnik Novosibirsk. Gos. Univ., Ser. Mat. Mekh. Inform., 2014, 14:1, 19-27. English translation: 2-computably enumerable degrees of categoricity for Boolean algebras with distinguished automorphisms, J. Math. Sci., 2015, 211:6, 738-746. Full-text access.
• Computable numberings of the class of Boolean algebras with distinguished endomorphisms, Algebra Logic, 2013, 52:5, 355-366. Full-text access.
• Computable categoricity of the Boolean algebra B(ω) with a distinguished automorphism, Algebra Logic, 2013, 52:2, 89-97. With Regina Tukhbatullina. Full-text access.
• Constructivizability of the Boolean algebra B(ω) with a distinguished automorphism, Algebra Logic, 2012, 51:5, 384-403. With Regina Tukhbatullina. Full-text access.

Publications listed in the reverse chronological order [pdf].

Last updated: April 10, 2024.