Authors:S. N. Baranov; V. V. Nikiforov Pages: 479 - 488 Abstract: An approach to estimate feasibility of a real-time multi-task application with various combinations of the scheduling mode and the protocol of access to shared informational resources when run on a multi-core platform is described. The application structure is specified through a simple formalized profile consisting of segments of three types and specifying access to informational resources shared among application tasks, the amount of the required computing resource being estimated for each segment. The approach is based on the notion of application density introduced by the authors which characterizes the use of computational resource by this application and is derived from estimation of the application feasibility for various values of processor performance and the number of its cores in case of a multi-core platform. The overall structure of a simulation tool for estimation of the task response time (and therefore, application feasibility) is described, which provides more exact data compared to the known analytical methods where they are applicable. Two dissimilar implementations of this tool were developed and run on a number of benchmarks, including Liu-Layland configurations specified in the described formalism for application structure; the results in form of charts are presented along with their analysis and interpretation. The suggested approach allows to indentify an optimal combination of the scheduling mode and access protocol for the given multi-task application structure. PubDate: 2017-12-01 DOI: 10.3103/s0146411617070021 Issue No:Vol. 51, No. 7 (2017)

Authors:V. M. Itsykson Pages: 531 - 538 Abstract: The paper considers the specification of the structure and the behavior of software libraries. It describes the existing problems of library specifications. A brief overview of the research field concerned with formalizing the specification of libraries and library functions is presented. The requirements imposed on the formalism designed are established; the formalism based on these requirements allows specification of all the properties of the libraries needed for automation of several classes of problems: defect detection in software, migration of applications into a new environment, and generation of software documentation. Requirements for language tools based on the developed formalism are proposed. The conclusion defines potential directions for further research. PubDate: 2017-12-01 DOI: 10.3103/s0146411617070100 Issue No:Vol. 51, No. 7 (2017)

Authors:D. Yu. Volkanov Pages: 539 - 550 Abstract: We consider the problem of choosing a balanced set of fault-tolerance techniques for distributed computer systems. In this problem, it is necessary to choose a balanced set of versions of the modules of distributed computer systems, during which the reliability of the set must be maximized under cost constraints (on the set of possible versions of distributed computer systems). We describe the fault-tolerance techniques out of which the choice is made and consider a mathematical model in the context of which the formulation of the problem and the method of its solution are given. This problem is widely considered in the literature. A detailed description of the method for choosing a balanced set of fault-tolerance techniques for distributed computer systems is presented. The proposed method represents an evolutionary algorithm using the scheme of fuzzy logic. The scheme of fuzzy logic in the process of operating the algorithm analyzes the results of its operation in each generation and from this information adjusts the parameters of the evolutionary algorithm. The method makes it possible to obtain an efficient solution, as shown in the experimental research. A key feature of the proposed approach is the use of an adaptive scheme. The method has been implemented as software integrated with the DYANA simulation environment. The conclusions of the paper contain a brief description of future research directions. PubDate: 2017-12-01 DOI: 10.3103/s0146411617070239 Issue No:Vol. 51, No. 7 (2017)

Authors:V. A. Bondarenko; A. V. Nikolaev; D. A. Shovgenov Pages: 576 - 585 Abstract: We study the polyhedral properties of three problems of constructing an optimal complete bipartite subgraph (a biclique) in a bipartite graph. In the first problem, we consider a balanced biclique with the same number of vertices in both parts and arbitrary edge weights. In the other two problems we are dealing with unbalanced subgraphs of maximum and minimum weight with non-negative edges. All three problems are established to be NP-hard. We study the polytopes and the cone decompositions of these problems and their 1-skeletons. We describe the adjacency criterion in the 1-skeleton of the polytope of the balanced complete bipartite subgraph problem. The clique number of the 1-skeleton is estimated from below by a superpolynomial function. For both unbalanced biclique problems we establish the superpolynomial lower bounds on the clique numbers of the graphs of nonnegative cone decompositions. These values characterize the time complexity in a broad class of algorithms based on linear comparisons. PubDate: 2017-12-01 DOI: 10.3103/s0146411617070276 Issue No:Vol. 51, No. 7 (2017)

Authors:E. A. Timofeev Pages: 586 - 591 Abstract: Let Ω = AN be a space of right-sided infinite sequences drawn from a finite alphabet A = {0,1}, N = {1,2,…}. Let ρ(x, y)Σk=1∞ x k − y k 2−k be a metric on Ω = AN, and μ the Bernoulli measure on Ω with probabilities p0, p1 > 0, p0 + p1 = 1. Denote by B(x,ω) an open ball of radius r centered at ω. The main result of this paper \(\mu (B(\omega ,r))r + \sum\nolimits_{n = 0}^\infty {\sum\nolimits_{j = 0}^{{2^n} - 1} {{\mu _{n,j}}} } (\omega )\tau ({2^n}r - j)\) , where τ(x) = 2min {x,1 − x}, 0 ≤ x ≤ 1, (τ(x) = 0, if x < 0 or x > 1 ), \({\mu _{n,j}}(\omega ) = (1 - {p_{{\omega _{n + 1}}}})\prod _{k = 1}^n{p_{{\omega _k}}} \oplus {j_k}\) , \(j = {j_1}{2^{n - 1}} + {j_2}{2^{n - 2}} + ... + {j_n}\) . The family of functions 1, x, τ(2 n r − j), j = 0,1,…, 2 n − 1, n = 0,1,…, is the Faber–Schauder system for the space C([0,1]) of continuous functions on [0, 1]. We also obtain the Faber–Schauder expansion for Lebesgue’s singular function, Cezaro curves, and Koch–Peano curves. Article is published in the author’s wording. PubDate: 2017-12-01 DOI: 10.3103/s014641161707032x Issue No:Vol. 51, No. 7 (2017)

Authors:S. A. Kashchenko Pages: 592 - 605 Abstract: For singularly perturbed second-order equations, the dependence of the eigenvalues of the first boundary-value problem on a small parameter at the highest derivative is studied. The main assumption is that the coefficient at the first derivative in the equation is the sign of the variable. This leads to the emergence of so-called turning points. Asymptotic expansions with respect to a small parameter are obtained for all eigenvalues of the considered boundary-value problem. It turns out that the expansions are determined only by the behavior of the coefficients in the neighborhood of the turning points. PubDate: 2017-12-01 DOI: 10.3103/s0146411617070112 Issue No:Vol. 51, No. 7 (2017)

Authors:V. F. Butuzov; N. N. Nefedov; L. Recke; K. R. Schneider Pages: 606 - 613 Abstract: For a singularly perturbed parabolic problem with Dirichlet boundary conditions, the asymptotic decomposition of a solution periodic in time and with boundary layers near the ends of the segment where the degenerate equation has a double root is constructed and substantiated. The construction algorithm for the asymptotics and the behavior of the solution in the boundary layers turn out to differ significantly as compared to the case of a simple root of a degenerate equation. The stability of the periodic solution and its region of attraction are also studied. PubDate: 2017-12-01 DOI: 10.3103/s0146411617070045 Issue No:Vol. 51, No. 7 (2017)

Authors:S. D. Glyzin; S. A. Kashchenko; A. O. Tolbey Pages: 627 - 633 Abstract: This work is devoted to investigating the dynamic properties of the solutions to the boundaryvalue problems associated with the classic Fermi–Pasta–Ulam (FPU) system. We analyze these problems for an infinite-dimensional case where a countable number of roots of characteristic equations tend to an imaginary axis. Under these conditions, we build a special nonlinear partial differential equation that acts as a quasi-normal form, i.e., determines the dynamics of the original boundary-value problem with the initial conditions in a sufficiently small neighborhood of the equilibrium state. The modified Korteweg–deVries (KdV) equation and the Korteweg–de Vries–Burgers (KdVB) equation act as quasi-normal forms depending on the parameter values. Under some additional assumptions, we apply the renormalization procedure to the boundary-value problems obtained. This procedure leads to an infinite-dimensional system of ordinary differential equations. We describe a method for folding this system into a special boundary- value problem, which is an analog of the normal form. The main contribution of this work is investigating the interaction of the waves moving in different directions in the FPU problem by using analytical methods of nonlinear dynamics. It is shown that the mutual influence of the waves is asymptotically small, does not affect their shape, and contributes only to a shift in their speeds, which does not change over time. PubDate: 2017-12-01 DOI: 10.3103/s0146411617070070 Issue No:Vol. 51, No. 7 (2017)

Authors:E. A. Timofeev Pages: 634 - 638 Abstract: Recall that Lebesgue’s singular function L(t) is defined as the unique solution to the equation L(t) = qL(2t) + pL(2t − 1), where p, q > 0, q = 1 − p, p ≠ q. The variables M n = ∫01t n dL(t), n = 0,1,… are called the moments of the function The principal result of this work is \({M_n} = {n^{{{\log }_2}p}}{e^{ - \tau (n)}}(1 + O({n^{ - 0.99}}))\) , where the function τ(x) is periodic in log2x with the period 1 and is given as \(\tau (x) = \frac{1}{2}1np + \Gamma '(1)lo{g_2}p + \frac{1}{{1n2}}\frac{\partial }{{\partial z}}L{i_z}( - \frac{q}{p}){ _{z = 1}} + \frac{1}{{1n2}}\sum\nolimits_{k \ne 0} {\Gamma ({z_k})L{i_{{z_k} + 1}}( - \frac{q}{p})} {x^{ - {z_k}}}\) , \({z_k} = \frac{{2\pi ik}}{{1n2}}\) , k ≠ 0. The proof is based on poissonization and the Mellin transform. PubDate: 2017-12-01 DOI: 10.3103/s0146411617070203 Issue No:Vol. 51, No. 7 (2017)

Authors:A. A. Kashchenko Pages: 639 - 644 Abstract: In this paper, we consider a singularly perturbed system of two differential equations with delay, simulating two coupled oscillators with a nonlinear feedback. The feedback function is assumed to be compactly supported and piecewise-continuous and it is assumed that its sign is constant. In this paper, we prove the existence of relaxation periodic solutions and make conclusions about their stability. Using a special large-parameter method, we construct asymptotics of all solutions of the considered system under the assumption that the initial-value conditions belong to a certain class. Using this asymptotics, we construct a special mapping principally describing the dynamics of the original model. It is shown that the dynamics changes fundamentally as the coupling coefficient decreases: we have a stable homogeneous periodic solution if the coupling coefficient is on the order of unity and the dynamics become more complex as the coupling coefficient decreases (it is described by a special map). For small values of the coupling, we show that there are values of the parameters such that several different stable relaxation periodic regimes coexist in the original problem. PubDate: 2017-12-01 DOI: 10.3103/s0146411617070124 Issue No:Vol. 51, No. 7 (2017)

Authors:S. D. Glyzin; A. Yu. Kolesov; E. A. Marushkina Pages: 658 - 665 Abstract: In this paper, we consider a mathematical model of synaptic interaction between two pulse neuron elements. Each of the neurons is modeled by a singularly perturbed difference-differential equation with delay. Coupling is assumed to be at the threshold with the time delay being taken into account. The problems of existence and stability of relaxation periodic movements for the systems derived are considered. It turns out that the critical parameter is the ratio between the delay caused by internal factors in the single-neuron model and the delay in the coupling link between the oscillators. The existence and stability of a uniform cycle for the problem are proved in the case where the delay in the link is less than the period of a single oscillator, which depends on the internal delay. As the delay grows, the in-phase regime becomes more complex; specifically, it is shown that, by choosing an adequate delay, we can obtain more complex relaxation oscillations and, during a period, the system can exhibit more than one high-amplitude splash. This means that the bursting effect can appear in a system of two synaptically coupled neuron-type oscillators due to the delay in the coupling link. PubDate: 2017-12-01 DOI: 10.3103/s0146411617070082 Issue No:Vol. 51, No. 7 (2017)

Authors:Y. A. Belov; S. I. Vovchok Pages: 678 - 681 Abstract: It is planned to create a method of clustering a social network graph. To test the method, it is necessary to generate a graph similar in structure to existing social networks. The article presents an algorithm for the graph-distributed generation. We take into account basic properties such as the power-law distribution of the number of user communities, the dense intersections of social networks, and others. This algorithm also considers the problems that are present in similar works of other authors, for example, the multiple edges problem in the generation process. A special feature of the created algorithm is the implementation depending on the number of communities, rather than on the number of connected users, as is done in other works. This is connected with a peculiarity of the development of the existing social network structure. The properties of its graph are described in the paper. We describe a Table 1 containing the variables needed for the algorithm. A step-by-step generation algorithm is compiled. Appropriate mathematical parameters are calculated for it. The generation is performed in a distributed way by the Apache Spark framework. It is described in detail how the division of tasks with the help of this framework operates. The Erdos–Renyi model for random graphs is used in the algorithm. It is the most suitable and easiest one to implement. The main advantages of the created method are the small amount of resources and faster execution speed in comparison with other similar generators. Speed is achieved through distributed work and the fact that at any time, the network users have their own unique numbers and are ordered by these numbers so that there is no need to sort them out. The designed algorithm will not only promote the creation of an efficient clustering method, but can also be useful in other development areas connected, for example, with social network search engines. PubDate: 2017-12-01 DOI: 10.3103/s0146411617070264 Issue No:Vol. 51, No. 7 (2017)

Authors:V. A. Bondarenko; A. V. Nikolaev; D. A. Shovgenov Pages: 682 - 688 Abstract: We consider the polyhedral properties of two spanning tree problems with additional constraints. In the first problem, it is required to find a tree with a minimum sum of edge weights among all spanning trees with the number of leaves less or equal a given value. In the second problem, an additional constraint is the assumption that the degree of all vertices of the spanning tree does not exceed a given value. The decision versions of both problems are NP-complete. We consider the polytopes of these problems and their 1-skeletons. We prove that in both cases it is a NP-complete problem to determine whether the vertices of 1-skeleton are adjacent. Although it is possible to obtain a superpolynomial lower bounds on the clique numbers of these graphs. These values characterize the time complexity in a broad class of algorithms based on linear comparisons. The results indicate a fundamental difference in combinatorial and geometric properties between the considered problems and the classical minimum spanning tree problem. PubDate: 2017-12-01 DOI: 10.3103/s0146411617070033 Issue No:Vol. 51, No. 7 (2017)

Authors:V. A. Zakharov; S. R. Jaylauova Pages: 689 - 700 Abstract: First-order program schemata represent one of the most simple models of sequential imperative programs intended for solving verification and optimization problems. We consider the decidable relation of logical-thermal equivalence on these schemata and the problem of their size minimization while preserving logical-thermal equivalence. We prove that this problem is decidable. Further we show that the first-order program schemata supplied with logical-thermal equivalence and finite-state deterministic transducers operating over substitutions are mutually translated into each other. This relationship makes it possible to adapt equivalence checking and minimization algorithms developed in one of these models of computation to the solution of the same problems for the other model of computation. In addition, on the basis of the discovered relationship, we describe a subclass of first-order program schemata such that minimization of the program schemata from this class can be performed in polynomial time by means of known techniques for minimization of finite-state transducers operating over semigroups. Finally, we demonstrate that in the general case the minimization problem for finite state transducers over semigroups may have several non-isomorphic solutions. PubDate: 2017-12-01 DOI: 10.3103/s0146411617070288 Issue No:Vol. 51, No. 7 (2017)

Authors:M. S. Komar Pages: 701 - 708 Abstract: In this paper, modern CPU architecture with several different cache levels is described and current CPU performance limitations such as frequency increase bounds are discussed. As changes to the currently existing architecture are usually proposed as a way of increasing CPU performance, data rates of the internal and external CPU interfaces must be known. This information would help to assess the applicability of proposed solutions and to optimize them. This paper is aimed at obtaining real values of traffic on an L2–L3 cache interface inside a CPU and a CPU–RAM bus load, as well as showing the dependences of the total traffic on the studied interfaces on the number of active cores, CPU frequency, and test type. A measurement methodology using an Intel Performance Counter Monitor is provided and the equations used to obtain data rates from the internal CPU counters are explained. Both real-life and synthetic tests are described. The dependence of total traffic on the number of active cores and the dependence of total traffic on CPU frequency are provided as plots. The dependence of total traffic on test type is provided as a bar plot for multiple CPU frequencies. PubDate: 2017-12-01 DOI: 10.3103/s014641161707029x Issue No:Vol. 51, No. 7 (2017)

Authors:A. A. Mitsyuk; I. A. Lomazova; W. M. P. van der Aalst Pages: 709 - 723 Abstract: During the life-cycle of an Information System (IS) its actual behavior may not correspond to the original system model. However, to the IS support it is very important to have the latest model that reflects the current system behavior. To correct the model the information from the event log of the system may be used. In this paper, we consider the problem of process model adjustment (correction) using the information from event log. The input data for this task is the initial process model (a Petri net) and an event log. The result of correction should be a new process model, better reflecting the real IS behavior than the initial model. The new model could be also built from scratch, for example, with the help of one of the known algorithms for automatic synthesis of the process model from an event log. However, this may lead to crucial changes in the structure of the original model, and it will be difficult to compare the new model with the initial one, hindering its understanding and analysis. Then it is important to keep the initial structure of the model as much as possible. In this paper we propose a method for process model correction based on the principle of “divide and conquer”. The initial model is decomposed into several fragments. For each of the fragments its conformance to the event log is checked. Fragments, which do not match the log, are replaced by newly synthesized ones. The new model is then assembled from the fragments via transition fusion. The experiments demonstrate that our correction algorithm gives good results when it is used for correcting local discrepancies. The paper presents the description of the algorithm, the formal justification for its correctness, as well as the results of experimental testing on artificial examples. PubDate: 2017-12-01 DOI: 10.3103/s0146411617070306 Issue No:Vol. 51, No. 7 (2017)

Authors:Aleksandr Tvardovskii; Khaled El-Fakih; Maxim Gromov; Nina Yevtushenko Pages: 724 - 730 Abstract: The behavior of many systems can be properly described by taking into account time constraints, and this motivates the adaptation of existing Finite State Machine (FSM)-based test derivation methods to timed models. In this paper, we propose a method for deriving conformance tests with the guaranteed fault coverage for a complete possibly nondeterministic FSM with a single clock; such Timed FSMs (TFSMs) are widely used when describing the behavior of software and digital devices. The fault domain contains every complete TFSM with the known upper bounds on the number of states and finite boundary of input time guards. The proposed method is carried out by using an appropriate FSM abstraction of the given TFSM; the test is derived against an FSM abstraction and contains timed input sequences. Shorter test suites can be derived for a restricted fault domain, for instance, for the case when the smallest duration of an input time guard is larger than two. Moreover, the obtained test suites can be reduced while preserving the completeness, when all input time guards of the specification and an implementation under test are right closed (or all guards are left-closed). Experiments are conducted to study the length of test suites constructed by different methods. PubDate: 2017-12-01 DOI: 10.3103/s0146411617070318 Issue No:Vol. 51, No. 7 (2017)

Authors:E. A. Timofeev Pages: 731 - 735 Abstract: The Takagi function is a simple example of a continuous yet nowhere differentiable function and is given as T(x) = Σk=0∞ 2−n ρ(2 n x), where \(\rho (x) = \mathop {\min }\limits_{k \in \mathbb{Z}} x - k \) . The moments of the Takagi function are given as M n = ∫01x n T(x)dx. The estimate \({M_n} = \frac{{1nn - \Gamma '(1) - 1n\pi }}{{{n^2}1n2}} + \frac{1}{{2{n^2}}} + \frac{2}{{{n^2}1n2}}\phi (n) + O({n^{ - 2.99}})\) , where the function \(\phi (x) = \sum\nolimits_{k \ne 0} \Gamma (\frac{{2\pi ik}}{{1n2}})\zeta (\frac{{2\pi ik}}{{1n2}}){x^{ - \frac{{2\pi ik}}{{1n2}}}}\) is periodic in log2x and Γ(x) and ζ(x) denote the gamma and zeta functions, is the principal result of this work. PubDate: 2017-12-01 DOI: 10.3103/s0146411617070197 Issue No:Vol. 51, No. 7 (2017)

Authors:A. A. Kashchenko Pages: 753 - 756 Abstract: In this paper we consider the nonlocal dynamics of the model of two coupled oscillators with delayed feedback. This model has the form of a system of two differential equations with delay. The feedback function is non-linear, compactly supported and smooth. The main assumption in the problem is that the coupling between the generators is sufficiently small. With the help of asymptotic methods we investigate the existence of relaxation periodic solutions of a given system. For this purpose, a special set is constructed in the phase space of the original system. Then we build an asymptotics of the solutions of the given system with initial conditions from this set. Using this asymptotics, a special mapping is constructed. Dynamics of this map describes the dynamics of the original problem in general. It is proved that all solutions of this mapping are non-rough cycles of period two. As a result, we formulate conditions for the coupling parameter such that the initial system has a two-parameter family of non-rough inhomogeneous relaxation periodic asymptotic (with respect to the residual) solutions. PubDate: 2017-12-01 DOI: 10.3103/s0146411617070343 Issue No:Vol. 51, No. 7 (2017)

Authors:M. V. Nevskii; A. Yu. Ukhalov Pages: 757 - 769 Abstract: Let n ∈N, and Q n = [0,1] n let be the n-dimensional unit cube. For a nondegenerate simplex S ⊂ R n , by σ S we denote the homothetic image of with center of homothety in the center of gravity of S and ratio of homothety σ. We apply the following numerical characteristics of a simplex. Denote by ξ(S) the minimal σ > 0 with the property Q n ⊂ σS. By α(S) we denote the minimal σ > 0 such that Q n is contained in a translate of a simplex σS. By d i (S) we mean the ith axial diameter of S, i. e., the maximum length of a segment contained in S and parallel to the ith coordinate axis. We apply the computational formulae for ξ(S), α(S), d i (S) which have been proved by the first author. In the paper we discuss the case S ⊂ Q n . Let ξ n = min{ξ(S): S ⊂ Q n }. Earlier the first author formulated the conjecture: if ξ(S) = ξ n , then α(S) = ξ(S). He proved this statement for n = 2 and the case when n + 1 is an Hadamard number, i. e., there exist an Hadamard matrix of order n + 1. The following conjecture is more strong proposition: for each n, there exist γ ≥ 1, not depending on S ⊂ Q n , such that ξ(S) − α(S) ≤ γ(ξ(S) − ξ n ). By ϰ n we denote the minimal γ with such a property. If n + 1 is an Hadamard number, then the precise value of ϰ n is 1. The existence of ϰ n for other n was unclear. In this paper with the use of computer methods we obtain an equality ϰ2 = \(\frac{{5 + 2\sqrt 5 }}{3}\) = 3.1573... Also we prove the new estimate ξ4 ≤ \(\frac{{19 + 5\sqrt {13} }}{9}\) = 4.1141..., which improves the earlier result ξ4 ≤ \(\frac{{13}}{3}\) = 4.33... Our conjecture is that ξ4 is precisely \(\frac{{19 + 5\sqrt {13} }}{9}\) . Applying this value in numerical computations we achive the value ϰ4 = \(\frac{{4 + \sqrt {13} }}{5}\) =1.5211... Denote by θ n the minimal norm of interpolation projector onto the space of linear functions of n variables as an operator from C(Q n ) in C(Q n ). It is known that, for each PubDate: 2017-12-01 DOI: 10.3103/s0146411617070355 Issue No:Vol. 51, No. 7 (2017)