VLDB 2026 Research / reviewers in the wild / expert
Serikzhan A. Badaev
dblp:69/7976
· DBLP profile ↗
7ranked-venue papers
4as first author
1since 2021 · last 2025
0000-0003-0444-2394ORCID · verified
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 7 · 4 first-author · 1 since 2021Artificial intelligence and machine learning · 1 · 1 first-author
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2025 | A non-computable c.e. closed subset of [0,1]abstractAbstract We prove that there exists a $\varSigma ^{0}_{1}$ closed subset of $[0,1]$ which is not homeomorphic to any computably compact space. We show that the index set of c.e. subspaces of $[0,1]$ that admit a computably compact presentation is not arithmetical, as witnessed by subsets of $[0,1]$. The index set result is new for computable Polish spaces in general, not only for those realised as c.e. closed subsets of $[0,1]$. Serikzhan A. Badaev, Nikolay Bazhenov 0001, Sergey Goncharov 0002, Birzhan S. Kalmurzayev, Alexander G. Melnikov |
J. Log. Comput. | 1 |
| 2020 | On Isomorphism Classes of computably Enumerable Equivalence RelationsabstractAbstract We examine how degrees of computably enumerable equivalence relations (ceers) under computable reduction break down into isomorphism classes. Two ceers are isomorphic if there is a computable permutation of ω which reduces one to the other. As a method of focusing on nontrivial differences in isomorphism classes, we give special attention to weakly precomplete ceers. For any degree, we consider the number of isomorphism types contained in the degree and the number of isomorphism types of weakly precomplete ceers contained in the degree. We show that the number of isomorphism types must be 1 or ω, and it is 1 if and only if the ceer is self-full and has no computable classes. On the other hand, we show that the number of isomorphism types of weakly precomplete ceers contained in the degree can be any member of $[0,\omega ]$ . In fact, for any $n \in [0,\omega ]$ , there is a degree d and weakly precomplete ceers ${E_1}, \ldots ,{E_n}$ in d so that any ceer R in d is isomorphic to ${E_i} \oplus D$ for some $i \le n$ and D a ceer with domain either finite or ω comprised of finitely many computable classes. Thus, up to a trivial equivalence, the degree d splits into exactly n classes. We conclude by answering some lingering open questions from the literature: Gao and Gerdes [11] define the collection of essentially FC ceers to be those which are reducible to a ceer all of whose classes are finite. They show that the index set of essentially FC ceers is ${\rm{\Pi }}_3^0$ -hard, though the definition is ${\rm{\Sigma }}_4^0$ . We close the gap by showing that the index set is ${\rm{\Sigma }}_4^0$ -complete. They also use index sets to show that there is a ceer all of whose classes are computable, but which is not essentially FC, and they ask for an explicit construction, which we provide. Andrews and Sorbi [4] examined strong minimal covers of downwards-closed sets of degrees of ceers. We show that if $\left( {{E_i}} \right)$ is a uniform c.e. sequence of non universal ceers, then $\left\{ {{ \oplus _{i \le j}}{E_i}|j \in \omega } \right\}$ has infinitely many incomparable strong minimal covers, which we use to answer some open questions from [4]. Lastly, we show that there exists an infinite antichain of weakly precomplete ceers. Uri Andrews, Serikzhan A. Badaev |
J. Symb. Log. | 2 |
| 2011 | Inductive inference and computable numberings
Klaus Ambos-Spies, Serikzhan A. Badaev, Sergey Goncharov 0002 |
Theor. Comput. Sci. | 2 |
| 2009 | A decomposition of the Rogers semilattice of a family of d.c.e. setsabstractAbstract Khutoretskii's Theorem states that the Rogers semilattice of any family of c.e. sets has either at most one or infinitely many elements. A lemma in the inductive step of the proof shows that no Rogers semilattice can be partitioned into a principal ideal and a principal filter. We show that such a partitioning is possible for some family of d.c.e. sets. In fact, we construct a family of c.e. sets which, when viewed as a family of d.c.e. sets, has (up to equivalence) exactly two computable Friedberg numberings μ and ν, and μ reduces to any computable numbering not equivalent to ν. The question of whether the full statement of Khutoretskii's Theorem fails for families of d.c.e. sets remains open. Serikzhan A. Badaev, Steffen Lempp |
J. Symb. Log. | 1 |
| 2008 | On a Question of Frank Stephan
Klaus Ambos-Spies, Serikzhan A. Badaev, Sergey Goncharov 0002 |
TAMC | 2 |
| 2006 | On Rogers Semilattices
Serikzhan A. Badaev |
TAMC | 1 |
| 2003 | Computable Numberings
Serikzhan A. Badaev |
LPAR | 1 |