English language
2021 год, том 25, выпуск 5 (PDF)
The article introduces an image encoding function which is invariant with respect to affine transform. The properties of the encoding funciton are investigated. Necessary and sufficient conditions are found for a given set of numbers to be a code of nonsingulari image.
Ключевые слова: image code, image encoding, affine equivalence.
This article introduces a new mathematical object called a cellular automaton with locators. It was created by implementing new functionality for an automaton to broadcast broadcasting signals and to receive summarized broadcasting signal of all elementary automata. This article highlights several problems which solution is greatly simplified by using cellular automata with locators instead of traditional cellular automata.
Ключевые слова: cellular automata, homogeneous structures, firing squad problem, motion picture design, constructing the shortest path.
The paper considers applying the locator cellular automaton model to the closest neighbour search problem. The locator cellular automaton model assumes the possibility for each cell to translate a signal through any distance using ether. It is proven in this paper that such possibility allows to decrease the problem complexity from linear to logarithmic (against the classic cellular automaton model).
Ключевые слова: cellular automaton, homogeneous structures,the closest neighbour search problem.
In [1], a cellular automaton with locators is defined. In this paper we indicate some inaccuracies and issues of this definition and clarify it to get rid of these issues. We also give examples of cellular automata classes with locators that have good properties in a certain sense.
Ключевые слова: cellular automata, homogeneous structures.
In this paper we research a model of multilayer circuits with a single logical layer. We consider \[\lambda \]-separable graphs as a support for circuits. We establish the Shannon function lower bound \[ \max ( \frac{2^n}{n}, \frac{2^n (1-\lambda)}{\log k} )\] for this type of circuits where k is the number of layers. For d-dimensional graphs, which are \[\lambda \]-separable for \[\lambda = \frac{d-1}{d}\] , this gives the Shannon function lower bound \[\frac{2^n}{\min (n,d \log k)}\]. For multidimensional rectangular circuits the proved lower bound asymptotically matches to the upper bound.
Ключевые слова: multilayer circuits, multidimensional circuits, Shannon function asymptotics, circuit complexity, graph separators.
This article describes a cellular automaton with locators that solves the problem of finding the nearest neighbour. The problem is to find from a finite set of points the one closest to a predetermined "central"point. In contrast to the classical model of a cellular automaton, in the model under consideration, instantaneous transmission of signals through the ether at an arbitrary distance is allowed. It is shown that this possibility makes it possible to solve the problem in constant time, which is strikingly different from the one-dimensional case, where a logarithmic lower complexity estimate by the minimal distance is obtained.
Ключевые слова: cellular automata, homogeneous structures, the closest neighbour search problem.
In this paper, it is shown that key-value databases can be implemented by cellular automata with locators in such a way that the execution time of basic operations, such as search, insert, delete, will not depend on the size of the database and will be equal to the total length of the key and value.
Ключевые слова: Cellular automata with locators, key-value databases.