Open Access
Access granted
Subscription Access
Vol 43, No 4 (2019)
- Year: 2019
- Articles: 7
- URL: https://journals.rcsi.science/0278-6419/issue/view/10819
Article
On Bilinear Complexity of Multiplying 2 × 2-Matrix by 2 × m-Matrix over Finite Field
Abstract
The problem of the least number of multiplications required to compute the product of a 2 × 2-matrix X and a 2 × m-matrix Y over an arbitrary finite field is considered by assuming that the elements of the matrices are independent variables. No commutativity of elements of matrix X with elements of matrix Y is assumed (i.e., bilinear complexity is considered). Upper bound \(\frac{{7m}}{2}\) for this problem over an arbitrary field is known. For two-element field, this bound is exact. Lower bound (3 + \(\frac{3}{{{K^2} + 2}}\)) m is obtained for the least number of multiplications in this problem over an arbitrary finite field with K elements.
149-155
Exact Solutions to One Nonlinear Sobolev Equation
Abstract
Several families of exact solutions expressed in terms of elementary and special functions are constructed for one nonlinear Sobolev-type equation. The qualitative behavior of these solutions is analyzed.
156-165
Problem of Stabilizing a Switching System Using a Piecewise-Linear Control System
Abstract
The problem of stabilizing a mathematical hybrid system with switchings between the operating modes is solved. Each of these modes is associated with nonlinear differential equations that have control parameters. The switching instances (conditions) are control components. A stabilizer must be designed in positional form that allows the trajectory of the entire nonlinear system to reach the target set in the phase space for a (prescribed) finite time. To solve the problem, k]an apparatus of continuous piecewise-linear Lyapunov functions is used along with the corresponding piecewise-linear control functions. A theorem concerning the sufficient conditions for the stabilizability of a hybrid system in the considered class of controls is proved. An algorithm for constructing the Lyapunov functions and the stabilizer is given.
166-176
Depth of Schemes Embedded in a Unit Cube and Implementing Typical Boolean Functions
Abstract
A class of schemes of functional elements in the standard basis of conjunction, disjunction, and negation elements is considered. For each scheme Σ from this class, in addition to depth D(Σ), its dimension R(Σ) is determined and found to be equal to the minimum dimension of the unit (Boolean) cube that allows isomorphic embedding Σ. In addition to results obtained earlier, it is proved that within the considered model inequality \(D({\Sigma _f}) \ge n + \frac{n}{{{{\log }_2}n}} - O(\frac{n}{{{{({{\log }_2}n)}^2}}})\) is satisfied for typical function f of n variables and for any scheme of functional elements Σf implementing it, such that R(Σf) = O(n), n = 1,2,.... New and more accurate lower estimates of the depth of the schemes implementing the typical functions and having linear dimensions are thus obtained.
177-180
Efficient Equivalence-Checking Algorithms for Procedural Programs in Progressive Semigroup Gateway Models
Abstract
The problem of program equivalence, checking whether programs have the same (equivalent) behavior in a given model, is investigated. The considered models of programs with “gateway” procedures were proposed somewhat recently, and almost nothing is known about solving the problem of equivalence for them. An approach is proposed to solving the problem of the consistent halting of programs without procedures. Based on known results, it allows to state decidability and polynomial decidability for the equivalence problem with procedures in many gateway models, and the corresponding decision algorithms to be constructed.
181-187
Queue Length in a Queuing System with Dependent Service Times
Abstract
A single-server queuing system with infinite capacity and a recurrent input flow is considered. Service times of the customer units have an exponential distribution with random parameter. The current value of the parameter is chosen from a finite set with given probabilities at the time the service of a certain customer is completed. Sequential values of the parameters form a special kind of Markov chain. The nonstationary behavior of the queue length is studied.
188-195
196-197