Vol 233, No 1 (2018)
- Year: 2018
- Articles: 12
- URL: https://journals.rcsi.science/1072-3374/issue/view/14941
Article
Indexing and Querying Character Sets in One- and Two-Dimensional Words
Abstract
We give a detailed review of results obtained for a relatively new problem of finding, indexing, and querying character sets, which are called fingerprints in fragments of one- and two-dimensional words, and explain basic ideas used for obtaining these results.
Semirings of Continuous (0,∞]-Valued Functions
Abstract
The semiring C∞(X) of all continuous functions on an arbitrary topological space X with values in the topological semiring (0,∞] is studied. General properties of semirings C∞(X) are considered. Properties of lattices of ideals and congruences of semirings C∞(X) over the P-spaces X, the F-spaces X, and the finite discrete spaces are proved.
Graded Quotient Rings
Abstract
This survey is based on the PhD Thesis that was defended at the Dissertation council of the Faculty of Mechanics and Mathematics of Moscow State University on December 6, 2013. This paper is devoted to the study of quotient rings of rings graded by a group. Graded analogs of the Faith–Utumi theorem of orders of matrix rings and Goldie’s theorems of orders of completely reducible rings are proved, and the orthogonal graded completion, which is an analog of the quotient ring underlying the orthogonal completion theory of Beidar–Mikhalev, is constructed.
Complexity and Structure of Circuits for Parity Functions
Abstract
The paper is devoted to circuits implementing parity functions. A review of results establishing exact values of the complexity of parity functions is given. The structure of optimal circuits implementing parity functions is described for some bases. For one infinite basis, an upper bound for the complexity of parity functions is given.
On the Depth of k-Valued Logic Functions Over Arbitrary Bases
Abstract
The behavior of the Shannon function of the depth of k-valued logic functions realized by circuits over an arbitrary complete basis is examined. For all k, k ≥ 3, for an arbitrary basis of k-valued logic functions, the existence of the asymptotic behavior of the Shannon function of the depth is established. The asymptotic behavior is linear for finite bases and it is constant or logarithmic for infinite bases. Thus, the complete picture of asymptotic behavior of the Shannon function of the depth is obtained for all k, k ≥ 2.
On Bellman’s and Knuth’s Problems and their Generalizations
Abstract
Various generalizations of the classical problem of the fastest raising to a power (or the so-called problem on addition chains) are studied in the asymptotic sense. Under weak restrictions, we demonstrate asymptotically tight solutions of the two best known generalizations, namely, Bellman’s problem on the computational complexity (on the minimal number of multiplication operations) of a normed monomial of several variables and Knuth’s problem on the computational complexity of a power system of one variable. We also briefly review some results on the computational complexity for three problems, namely, the computation of p-element systems of normed monomials in q variables, additive computations for systems of p integer linear forms over q variables, and the computation of p-element systems of the free Abelian group with q generators.
On Independent Families of Normal Subgroups in Free Groups
Abstract
Consider a presentation \( \mathcal{P}=\left\langle \mathrm{X}\left|\underset{i=1}{\overset{n}{\cup }}{\mathrm{r}}_i\right.\right\rangle \) . Let Ri be the normal closure of the set ri in the free group F with basis x, \( {\mathcal{P}}_i=\left\langle \mathrm{X}\left|{\mathrm{r}}_i\right.\right\rangle, {\mathrm{N}}_i=\prod \limits_{j\ne i}{\mathbf{R}}_j \). In this paper, using geometric techniques of pictures, generators for \( \frac{{\mathbf{R}}_i\cap {\mathbf{N}}_i}{\left[{\mathbf{R}}_i,{\mathbf{N}}_i\right]},i=1 \), . . . , n, are obtained from a set of generators over \( \left\{{\mathcal{P}}_i\left|i=1\right.,\dots n\right\} \) for \( {\pi}_2\left(\mathcal{P}\right) \). As a corollary, we get a sufficient condition for the family {R1,…,Rn} to be independent.
Groups in Which the Normal Closures of Cyclic Subgroups Have Bounded Finite Hirsch–Zaitsev Rank
Abstract
In this paper, we study generalized soluble groups with restriction on normal closures of cyclic subgroups. A group G is said to have finite Hirsch–Zaitsev rank if G has an ascending series whose factors are either infinite cyclic or periodic and if the number of infinite cyclic factors is finite. It is not hard to see that the number of infinite cyclic factors in each of such series is an invariant of a group G. This invariant is called the Hirsch–Zaitsev rank of G and will be denoted by rhz(G). We study the groups in which the normal closure of every cyclic subgroup has the Hirsch–Zaitsev rank at most b (b is some positive integer). For some natural restrictions we find a function k1(b) such that rhz([G/Tor(G),G/Tor(G)]) ≤ k1(b).
The Leibniz Differential and the Perron–Stieltjes Integral
Abstract
We implement Leibniz’s idea about the differential as the length of an infinitesimally small elementary interval (a monad) in a form satisfying modern standards of rigor. The concept of sequential differential introduced in this paper is shown to be in good alignment with the standard convention of the integral calculus. As an application of this concept we simplify and generalize the construction of the Perron–Stieltjes integral.