Sage Journals: Discover world-class research

Abstract

This survey paper summarizes the main results of Professor Victor Selivanov’s research, which together highlight the important advances he achieved in mathematical logic and theoretical computer science.

Keywords

Computability theory numbering theory hierarchies degrees theory of formal languages complexity theory descriptive set theory Wadge degrees domain theory asymmetric topology quasi-Polish spaces computable analysis

Get full access to this article

View all access options for this article.

References

Andretta and

D.A.

Martin, Borel-Wadge degrees. Fund. Math.177(2) (2003), 175–192. doi:10.4064/fm177-2-5.

Andrews and

S.A.

Badaev, On isomorphism classes of computably enumerable equivalence relations, Journal of Symbolic Logic85(1) (2020), 61–86. doi:10.1017/jsl.2019.39.

Andrews and

Sorbi, Effective inseparability, lattices, and preordering relations, Review of Symbolic Logic14(4) (2021), 838–865. doi:10.1017/S1755020319000273.

M.M.

Arslanov, Fixed-point selection functions, Lobachevskii Journal of Mathematics42(4) (2021), 685–692. doi:10.1134/S1995080221040041.

S.A.

Badaev and

S.S.

Goncharov, The theory of numberings: Open problems, in: Computability Theory and Its Applications,

Cholak,

Lempp,

Lerman and

Shore, eds, Contemp. Math., Vol. 257, American Mathematical Society, Providence, 2000, pp. 23–38. doi:10.1090/conm/257/04025.

Barendregt and

S.A.

Terwijn, Fixed point theorems for precomplete numberings, Annals of Pure and Applied Logic170(10) (2019), 1151–1161. doi:10.1016/j.apal.2019.04.013.

Bazhenov,

Downey,

I.S.

Kalimullin and

A.G.

Melnikov, Foundations of online structure theory, Bulletin of Symbolic Logic25(2) (2019), 141–181. doi:10.1017/bsl.2019.20.

Bazhenov,

Harrison-Trainor and

Melnikov, Computable Stone spaces, Ann. Pure Appl. Logic174(9) (2023), Paper No. 103304, 25.

Becher and

Grigorieff, Borel and Hausdorff hierarchies in topological spaces of Choquet games and their effectivization, Math. Structures Comput. Sci.25(7) (2015), 1490–1519. doi:10.1017/S096012951300025X.

10.

V.K.

Bulitko, Reducibility by Zhegalkin-linear tables, Siberian Mathematical Journal21(3) (1980), 332–339. doi:10.1007/BF00968176.

11.

de Brecht, Quasi-Polish spaces, Ann. Pure Appl. Logic164(3) (2013), 356–381. doi:10.1016/j.apal.2012.11.001.

12.

R.G.

Downey and

A.G.

Melnikov, Computably compact metric spaces, Bull. Symb. Log.29(2) (2023), 170–263. doi:10.1017/bsl.2023.16.

13.

Y.L.

Ershov, Theory of Numberings, Nauka, Moscow, 1977(in Russian).

14.

Y.L.

Ershov, Theory of numberings, in: Handbook of Computability Theory,

E.R.

Griffor, ed., Stud. Logic Found. Math., Vol. 140, North-Holland, Amsterdam, 1999, pp. 473–503. doi:10.1016/S0049-237X(99)80030-5.

15.

Faizrahmanov, Numberings, c.e. oracles, and fixed points, Computability12(3) (2023), 271–282. doi:10.3233/COM-210387.

16.

Freivalds,

Karpinski,

C.H.

Smith and

Wiehagen, Learning by the process of elimination, Information and Computation176(1) (2002), 37–50. doi:10.1006/inco.2001.2922.

17.

Gavryushkin,

Khoussainov and

Stephan, Reducibilities among equivalence relations induced by recursively enumerable structures, Theoretical Computer Science612 (2016), 137–152. doi:10.1016/j.tcs.2015.11.042.

18.

S.S.

Goncharov,

V.S.

Harizanov,

J.F.

Knight,

C.F.D.

McCoy,

R.G.

Miller and

Solomon, Enumerations in computable structure theory, Annals of Pure and Applied Logic136(3) (2005), 219–246. doi:10.1016/j.apal.2005.02.001.

19.

Harrison-Trainor,

Melnikov and

K.M.

Ng, Computability of Polish spaces up to homeomorphism, J. Symb. Log.85(4) (2020), 1664–1686. doi:10.1017/jsl.2020.67.

20.

Hertling, Topologische Komplexitätsgrade von Funktionen mit endlichem Bild, Informatik-Berichte, Vol. 152, FernUniversität in Hagen, Hagen, 1993.

21.

C.G.

JockuschJr. and

R.A.

Shore, Pseudo-jump operators. II: Transfinite iterations, hierarchies and minimal covers, Journal of Symbolic Logic49(4) (1984), 1205–1236. doi:10.2307/2274273.

22.

I.S.

Kalimullin,

A.G.

Melnikov and

K.M.

Ng, Algebraic structures computable without delay, Theoretical Computer Science674 (2017), 73–98. doi:10.1016/j.tcs.2017.01.029.

23.

Kihara and

Montalbán, On the structure of the Wadge degrees of bqo-valued Borel functions, Trans. Amer. Math. Soc.371(11) (2019), 7885–7923. doi:10.1090/tran/7621.

24.

K.I.

Ko, Complexity Theory of Real Functions, Progress in Theoretical Computer Science, Birkhäuser, Boston, 1991.

25.

M.V.

Korovina and

O.V.

Kudinov, The Rice–Shapiro theorem in computable topology, Logical Methods in Computer Science13(4) (2017).

26.

Lupini,

Melnikov and

Nies, Computable topological Abelian groups, J. Algebra615 (2023), 278–327. doi:10.1016/j.jalgebra.2022.10.003.

27.

A.I.

Mal’tsev, Completely numbered sets, Algebra and Logic2(2) (1963) (in Russian).

28.

A.G.

Melnikov, New degree spectra of Polish spaces, Sib. Math. J.62(5) (2021), 882–894. Translation of Sibirsk. Mat. Zh. 62(5) (2021), 1091–1108. doi:10.33048/smzh.2021.62.511.

29.

Motto Ros, Borel-amenable reducibilities for sets of reals, J. Symbolic Logic74(1) (2009), 27–49. doi:10.2178/jsl/1231082301.

30.

Normann, Recursion on the Countable Functionals, Lecture Notes in Mathematics, Vol. 811, Springer, Berlin, 1980.

31.

Park,

Brauße,

Collins,

Kim,

Konečný,

Lee,

Müller,

Neumann,

Preining and

Ziegler, Foundation of computer (algebra) analysis systems: Semantics, logic, programming, verification, 2020. https://arxiv.org/abs/1608.05787.

32.

Pequignot, A Wadge hierarchy for second countable spaces, Arch. Math. Logic54(5–6) (2015), 659–683. doi:10.1007/s00153-015-0434-y.

33.

Selivanova, Computational complexity of classical solutions of partial differential equations, in: Proceedings of Computability in Europe (CiE 2022), Lecture Notes in Computer Science, Vol. 13359, 2022, pp. 299–312.

34.

Spreen, Life and work of Victor L. Selivanov, in: Logic, Computation, Hierarchies,

Brattka,

Diener and

Spreen, eds, 2014, pp. 1–8.

35.

van Engelen,

A.W.

Miller and

Steel, Rigid Borel sets and better quasi-order theory, in: Logic and Combinatorics (Arcata, Calif., 1985), Contemp. Math., Vol. 65, Amer. Math. Soc., Providence, RI, 1987, pp. 199–222. doi:10.1090/conm/065/891249.

36.

R.A.

Van Wesep, Subsystems of Second-Order Arithmetic, and Descriptive Set Theory Under the Axiom of Determinateness, ProQuest LLC, Ann Arbor, MI, 1977. Thesis (Ph.D.)–University of California, Berkeley.

37.

W.W.

Wadge, Reducibility and Determinateness on the Baire Space, ProQuest LLC, Ann Arbor, MI, 1983. Thesis (Ph.D.)–University of California, Berkeley.

38.

Weihrauch, Computable Analysis, Springer, Berlin, 2000.

On the main scientific achievements of Victor Selivanov

Abstract

Keywords

Get full access to this article

References