Open Access Open Access  Restricted Access Access granted  Restricted Access Subscription Access

Vol 30, No 2 (2019)

I. Discrete Models of Information Systems

A Flattening Algorithm for Hierarchical Timed Automata

Podymov V.V.

Abstract

We propose a coherent algorithm for the translation of hierarchical timed automata into networks of (planar) timed automata. This kind of translation is called flattening. The two types of timed automata are used in formal verification of real-time systems: systems of parallel interacting components whose execution essentially depends not only on the order of the events in the system, but also on the real time of these events. The concept of hierarchical timed automaton covers the syntactic variations that are used in existing studies and are non-comparable by their expressive power. The number of states in a flattened network of time automata is of the least order among the flattening results of existing studies.

Computational Mathematics and Modeling. 2019;30(2):99-106
pages 99-106 views

Article

On the Structure of the Lattice of Classes of Partial Monotone Many-Valued Logic Functions

Dudakova O.S.

Abstract

We construct an infinite family of closed classes of partial monotone many-valued logic functions that include the class of everywhere defined functions monotone with respect to partially ordered sets of a special type.

Computational Mathematics and Modeling. 2019;30(2):107-114
pages 107-114 views

Optimal Two-Sided Embeddings of Complete Binary Trees in Rectangular Grids

Vysotskiy L.I., Lozhkin S.A.

Abstract

The article considers the construction of optimal-area homeomorphic embeddings of complete binary trees in rectangular grids such that the leaf images are on the opposite sides of the grid and the edge images intersect only at node images. The minimum grid area that admits the embedding of a complete binary tree of depth n is shown to be asymptotically equal to \( \frac{n}{3}{2}^n \). An algorithm to construct an asymptotically optimal embedding of such a tree is proposed; the complexity of the algorithm is O(n2n) bit operations.

Computational Mathematics and Modeling. 2019;30(2):115-128
pages 115-128 views

Asymptotic Bounds of the Shannon Function for a Depth Model of Functional-Element Networks with Capacity Parameters for Element Outputs

Danilov B.R., Lozhkin S.A.

Abstract

The article proposes a synthesis method for amplifying networks of functional elements (ANFE) that establishes the asymptotic behavior of the Shannon function for the ANFE generalized depth, i.e., the depth of the “worst” Boolean function of n given variables, in a special basis (the depth model) where the element depth is determined both by its type and by its fan-out in the network. The asymptotic behavior of the Shannon function is established apart from a term logarithmic in n.

Computational Mathematics and Modeling. 2019;30(2):129-136
pages 129-136 views

A Numerical Method for Determining Two Sorbent Characteristics in Case of Decreasing Porosity

Tuikina S.R.

Abstract

For a mathematical model that incorporates internal-diffusion kinetics and sorbent swelling, we consider the inverse problem of determining the sorption isotherm and the porosity coefficient from two output dynamic curves. A gradient-type iterative method utilizing the conjugate problem technique is proposed and results of numerical experiments are reported. The results are used to investigate the features of the proposed method.

Computational Mathematics and Modeling. 2019;30(2):155-163
pages 155-163 views

A Variational Method of Wavefront Reconstruction from Local Slope Measurements Using a Fractional Order of Smoothness Stabilizer

Razgulin A.V., Kuzhamaliyev Y.Z., Iroshnikov N.G., Larichev A.V.

Abstract

Wavefront reconstruction from local slope estimates is performed by a family of variational methods with a fractional order stabilizer designed to ensure best uniform reconstruction of the front on the entire frequency spectrum. Analytical and numerical investigation of the space-frequency characteristic of the family and numerical experiments with reconstruction of regular and turbulent wavefronts have demonstrated the advantage of the proposed method over the common Simpson method.

Computational Mathematics and Modeling. 2019;30(2):164-176
pages 164-176 views

Computing Observability of Gates in Combinational Logic Circuits by Bit-Parallel Simulation

Telpukhov D.V., Nadolenko V.V., Gurov S.I.

Abstract

The article considers vector computation methods (bit-parallel simulation) for determining the observability of combinational logic gates. The computations produce an ODC (observability don’t care) set of all gates for a given set of circuit states. These results make it possible to evaluate the probability of logical masking of a random circuit fault. The methods are compared by accuracy and time costs using testing results for ISCAS ’85 benchmark circuits.

Computational Mathematics and Modeling. 2019;30(2):177-190
pages 177-190 views

II. Mathematical Modeling

Investigation of a Mathematical Model Linking GDP Growth with Changes in National Debt

Dmitriev V.I., Kurkina E.S.

Abstract

The article proposes a mathematical model linking GDP growth with changes in national debt. The model is based on a system of two linear ordinary differential equations. The rate of GDP growth is defined in the model as the difference between aggregate revenues and aggregate expenses, including debt service expenses. Possible types of GDP and national debt dynamics are investigated as a function of parameters. External investments increasing national debt may accelerate economic growth, whereas without new external loans GDP either does not grow or grows slowly. An equation describing the variation of relative external debt has been derived and fully investigated. It is shown that the external debt is never fully repaid, which is consistent with other models. Conditions of stable economic growth are derived, when GDP grows faster than or at the same rate as national debt, whereas the relative debt approaches a constant value. We investigate conditions that preclude a Ponzi game, so that a country cannot use new external debt to build a financial pyramid to repay old debt. The model features are demonstrated in application to statistical data from a number of countries. The model parameters are determined and growth trajectories are calculated for GDP and national debt.

Computational Mathematics and Modeling. 2019;30(2):137-154
pages 137-154 views