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.
• On learning for families of algebraic structures, Lobachevskii J. Math., 2024, 45:4, 1789-1799. Full-text access. This is the translation of the paper published in 2023.
• 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 Polish spaces, and related topics

• Computably and punctually universal spaces, Ann. Pure Appl. Logic, 2025, 176:1, article 103491. With Ramil Bagaviev, Ilnur Batyrshin, Dmitry Bushtets, Marina Dorzhieva, Heer Tern Koh, Ruslan Kornev, Alexander Melnikov and Keng Meng Ng.
• Every Δ⁰₂ Polish space is computable topological, Proc. Am. Math. Soc., 2024, 152:7, 3123-3136. 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. [arXiv:2301.09940]
• Computable Stone spaces, Ann. Pure Appl. Logic, 2023, 174:9, article 103304. With Matthew Harrison-Trainor and Alexander Melnikov. [arXiv:2107.01536]

Algorithmic learning

• On learning down-sets in quasi-orders, and ideals in Boolean algebras, Theory Comput. Syst., 2025, 69:1, article 1. With Manat Mustafa. This is a journal version of the TAMC-2024 conference paper «On learning families of ideals in lattices and Boolean algebras». Full-text access.
• Learning families of algebraic structures from text, in Proceedings of CiE-2024 (Lect. Notes Comput. Sci., 14773), 166-178. With Ekaterina Fokina, Dino Rossegger, Alexandra Soskova, and Stefan Vatev. [arXiv:2402.05744]
• On learning families of ideals in lattices and Boolean algebras, in Proceedings of TAMC-2024 (Lect. Notes Comput. Sci., 14637), 1-13. With Manat Mustafa.
• 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

• On the theory of computably enumerable linear preorders with concatenation, Sib. Math. J., 2025, 66:2, 235-247. With Daryn Alish and Birzhan Kalmurzayev. Full-text access.
• Computably enumerable equivalence relations via primitive recursive reductions, J. Log. Comput., 2025, 35:2, article id exad082. 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 Daryn Alish and Birzhan Kalmurzayev.
• 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

• Elementary theories of Rogers semilattices in the analytical hierarchy, in: Higher Recursion Theory and Set Theory (Lect. Notes Ser., Inst. Math. Sci., Natl. Univ. Singapore, vol. 44, 2025), 1-18. With Manat Mustafa.
• On arithmetical numberings in reverse mathematics, in Proceedings of CiE-2024 (Lect. Notes Comput. Sci., 14773), 126-138. With Marta Fiori Carones and Manat Mustafa.
• On concept lattices for numberings, Tsinghua Sci. Technol., 2024, 29:6, 1642-1650. With Manat Mustafa and Anvar Nurakunov. This is a journal version of the TAMC-2022 conference paper «On two types of concept lattices in the theory of numberings».
• 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

• Degrees of relations on canonically ordered natural numbers and integers, Arch. Math. Logic, 2025, 64:1-2, 299-331. With Dariusz Kalociński and Michał Wrocławski. This is a journal version of the STACS-2022 conference paper «Intrinsic complexity of recursive functions on natural numbers with standard order».
• 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)

• Decidable categoricity spectra for almost prime models, Algebra Logic, 2023, 62:4, 291-302. With Margarita Marchuk.
• 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 mathematical logic

• Undecidability of the degree structure of primitive recursive m-reducibility, J. Log. Comput., published online. With Birzhan Kalmurzayev and Alibek Iskakov.
• 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: March 23, 2025.