YSYuriy Shablya

Yuriy Shablya

Tomsk State University of Control Systems and Radio-Electronics
See Latest Publications
See Most Cited Publications
SciProfiles
ORCID Profile
Google Scholar

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Yuriy Shablya has a total of 13 co-authors. Here are the top co-authors by number of shared publications:

Latest Publications

  • Website
    Google Scholar

    Combinatorial generation algorithms based on AND/OR tree structures for a class of algebraic generating functions

    by Yuriy V. Shablya

    This paper proposes a systematic approach to developing combinatorial generation algorithms for sets of discrete structures whose cardinality is determined by the coefficients of algebraic generating functions and their powers. The study is based on the relationship between operations on generating functions and combinatorial sets. It uses the mathematical apparatus of AND/OR trees as a foundation, which allows combining combinatorial generation algorithms for simple substructures into complex combinatorial objects. The main theoretical result of the work is the derivation of new efficient recurrence formulas for calculating the values of the coefficients of algebraic generating functions and their powers with polynomial computational complexity $O((n_1 + \ldots + n_m + m) \cdot n^2)$ for time and $O(n^2)$ for memory. Based on proven theorems on recurrence formulas, the proposed approach enables the construction of algorithms with polynomial computational complexity estimates, making them applicable to solving practical problems in applied discrete mathematics and theoretical computer science. Moreover, the use of coefficients of generating function powers expands the generation capabilities, since it allows us to construct not only objects of the original combinatorial set associated with the generating function, but also tuples of such objects. Validation of the proposed approach is demonstrated using examples of deriving recurrence formulas and generation algorithms based on them for classical numerical sequences, such as the Fibonacci, Pell, Catalan, Motzkin, and Schroder numbers. The proposed approach opens up new possibilities for solving problems of optimization, modeling, and coding complex discrete structures, for example, in fields such as bioinformatics and cryptography.

    Cited by 1
  • Website
    Google Scholar

    Algorithms for ranking and unranking the combinatorial set of RNA secondary structures

    by Yuriy Shablya, Dmitry Kruchinin

    In this paper, we study the combinatorial set of RNA secondary structures. The main contribution of this paper is the developed ranking and unranking algorithms for the combinatorial set of pseudoknot-free RNA secondary structures of length [ ] with [ ] base-pairs. The developed algorithms are based on a bijection between the set of RNA structures and the variants of the corresponding AND/OR tree structure. Assuming a unit-cost RAM model, the developed algorithms have polynomial time complexity [ ] for [ ] and [ ] for [ ]. In contrast to the existing algorithms, the new algorithms do not require preprocessing steps and have better overall time complexity.

    Cited by 1
  • Website
    Google Scholar
    Open Access

    Combinatorial Generation Algorithms for Directed Lattice Paths

    by Yuriy Shablya, Arsen Merinov, Dmitry Kruchinin

    Graphs are a powerful tool for solving various mathematical problems. One such task is the representation of discrete structures. Combinatorial generation methods make it possible to obtain algorithms that can create discrete structures with specified properties. This article is devoted to issues related to the construction of such combinatorial generation algorithms for a wide class of directed lattice paths. The main method used is based on the representation of a given combinatorial set in the form of an AND/OR tree structure. To apply this method, it is necessary to have an expression for the cardinality function of a combinatorial set that satisfies certain requirements. As the main result, we have found recurrence relations for enumerating simple directed lattice paths that satisfy the requirements of the applied method and have constructed the corresponding AND/OR tree structure. Applying the constructed AND/OR tree structure, we have developed new algorithms for ranking and unranking simple directed lattice paths. Additionally, the obtained results were generalized to the case of directed lattice paths.

    Cited by 1
  • Website
    Google Scholar
    Open Access

    Method for Obtaining Coefficients of Powers of Multivariate Generating Functions

    by Dmitry Kruchinin, Vladimir Kruchinin, Yuriy Shablya

    There are several general concepts that allow obtaining explicit formulas for the coefficients of generating functions in one variable by using their powers. One such concept is the application of compositae of generating functions. In previous studies, we have introduced a generalization for the compositae of multivariate generating functions and have defined basic operations on the compositae of bivariate generating functions. The use of these operations helps to obtain explicit formulas for compositae and coefficients of generating functions in two variables. In this paper, we expand these operations on compositae to the case of generating functions in three variables. In addition, we describe a way of applying compositae to obtain coefficients of rational generating functions in several variables. To confirm the effectiveness of using the proposed method, we present detailed examples of its application in obtaining explicit formulas for the coefficients of a generating function related to the Aztec diamond and a generating function related to the permutations with cycles.

    Cited by 5
  • Website
    Google Scholar
    Open Access

    Combinatorial Generation Algorithms for Some Lattice Paths Using the Method Based on AND/OR Trees

    by Yuriy Shablya

    Methods of combinatorial generation make it possible to develop algorithms for generating objects from a set of discrete structures with given parameters and properties. In this article, we demonstrate the possibilities of using the method based on AND/OR trees to obtain combinatorial generation algorithms for combinatorial sets of several well-known lattice paths (North-East lattice paths, Dyck paths, Delannoy paths, Schroder paths, and Motzkin paths). For each considered combinatorial set of lattice paths, we construct the corresponding AND/OR tree structure where the number of its variants is equal to the number of objects in the combinatorial set. Applying the constructed AND/OR tree structures, we have developed new algorithms for ranking and unranking their variants. The performed computational experiments have confirmed the obtained theoretical estimation of asymptotic computational complexity for the developed ranking and unranking algorithms.

    Cited by 1
  • Website
    Google Scholar
    Open Access

    Combinatorial generation algorithms for the set defined by central polygonal numbers

    by Georgiy Filippov, Dmitry Kruchinin, Yuriy Shablya, Victor Rulevskiy

    In this paper, we study the combinatorial set of pieces formed when slicing a disk with a given number of straight cuts. The cardinality function of this combinatorial set is described by the central polygonal numbers. Using the obtained cardinality function, we construct the corresponding AND/OR tree structure and determine a bijection between the set of variants of the AND/OR tree and the considered combinatorial set. In addition, we develop ranking and unranking algorithms for the combinatorial set.

  • Website
    Google Scholar
    Open Access

    Unranking Small Combinations of a Large Set in Co-Lexicographic Order

    by Vladimir Kruchinin, Yuriy Shablya, Dmitry Kruchinin, Victor Rulevskiy

    The presented research is devoted to the problem of developing new combinatorial generation algorithms for combinations. In this paper, we develop a modification of Ruskey’s algorithm for unranking m-combinations of an n-set in co-lexicographic order. The proposed modification is based on the use of approximations to make a preliminary search for the values of the internal parameter k of this algorithm. In contrast to the original algorithm, the obtained algorithm can be effectively applied when n is large and m is small because the running time of this algorithm depends only on m. Furthermore, this algorithm can be effectively used when n and m are both large but n−m is small, since we can consider unranking (n−m)-combinations of an n-set. The conducted computational experiments confirm the effectiveness of the developed modification.

    Cited by 6
  • Website
    Google Scholar

    On some properties of generalized Narayana numbers

    by Dmitry Kruchinin, Vladimir Kruchinin, Yuriy Shablya

    In this paper, we consider a three-parameter generalization of the Narayana numbers that is related to the powers of the generating function for the Narayana numbers. We find a multivariate generat...

    Cited by 7
  • Website
    Google Scholar
    Open Access

    Method for Obtaining Coefficients of Powers of Bivariate Generating Functions

    by Dmitry Kruchinin, Vladimir Kruchinin, Yuriy Shablya

    In this paper, we study methods for obtaining explicit formulas for the coefficients of generating functions. To solve this problem, we consider the methods that are based on using the powers of generating functions. We propose to generalize the concept of compositae to the case of generating functions in two variables and define basic operations on such compositae: composition, addition, multiplication, reciprocation and compositional inversion. These operations allow obtaining explicit formulas for compositae and coefficients of bivariate generating functions. In addition, we present several examples of applying the obtained results for getting explicit formulas for the coefficients of bivariate generating functions. The introduced mathematical apparatus can be used for solving different problems that are related to the theory of generating functions.

    Cited by 11
  • Website
    Google Scholar
    Open Access

    Algorithms for ranking and unranking the combinatorial set of closed questionnaire answers

    by P P Shcheglov, G A Filippov, Y V Shablya, D V Kruchinin

    In this paper, we study the combinatorial set of closed questionnaire answers with a specified minimum number of correct answers. For this combinatorial set, we obtain an explicit formula for its cardinality function. Using the obtained cardinality function, we construct the corresponding AND/OR tree structure and determine the bijecion rules for this AND/OR tree and the considered combinatorial set. In addition, we develop ranking and unranking algorithms for the combinatorial set.

Show all