Русский язык
2020 year, volume 24, issue 4 (PDF)
The paper considers the problem of testing the possibility of a user of an information system gaining access to the selected object with a given attribute-based security policy. It is shown that under some restrictions on information system model and policy rules, this task is reduced to the task of automated planning. There is a tree structure determined, the construction of which corresponds to planning in the space of plans and allows to take into account the specifics of the problem when constructing heuristic algorithms for checking access. It is proved that the existence of such a structure is a necessary and sufficient condition for the possibility of getting an access to the target.
Keywords: ABAC, access control, automated planning.
In this article we present the results of a discussion on the problems and prospects of artificial intelligence, held at the Chair of Mathematical Theory of Intelligent Systems on October 14, 2020. The topic of the discussion goes back to the classic works of Alan Turing “Can machines think?” and John von Neumann “The Computer and the Brain”, which emerged at the dawn of Cybernetics as a science. Since then, the discussion on the topic “Can machines think?” appeared and faded, but they did not bring much clarity in the understanding of this issue. In recent years, due to the development of the technological base of computing systems, the topic has become relevant again. Together with the scientific base developed in the theory of artificial intelligence and applications in this area, a lot of speculative works have emerged that are ready to declare any device with trivial algorithmic additions “an artificial intelligence system”. This paper attempts to separate the wheat from the chaff by presenting several points of view on this issue.
Keywords: artificial intelligence, machine learning, neural networks.
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.
Keywords: cellular automata, homogeneous structures.
For a class of piecewise-parallel functions implemented by schemes of linear elements and Heaviside functions, an algorithm for checking the completeness of finite subsets supplemented by single functions is obtained. Thus, for this class solved the Slupetski problem.
Keyword: The piecewise-linear function piecewise-parallel function, the completeness problem, the Slupetski criterion.
If we remove symbols of a state diagram, then we get a directed graph. The inverse operation, when this information is restored, is called graph labeling. This article estimates the number of graph labelings that lead to a group automata.
Keywords: group automata, transition graph, state diagram, permanent, matrix decomposition.
We consider a family of quantum LDPC codes with weight- 6 stabilizer generators and two logical qubits, where some logical operators have a fractal structure. These codes can be considered as local quantum codes on the \[\textit{L} \times \textit{L} \times \textit{L} \] cubic lattice with periodic boundary conditions. We prove that the minimum distance of codes from this family is bounded below by \[\Omega (L^\alpha) \], where \[\alpha = \log_2 (2(\sqrt{5}-1)) \approx \textit{1.306} \].
Keywords: quantum LDPC code, local quantum code, minimum distance, linear cellular automaton, fractal dimension.
We consider the order problem with respect to the superposition operation for linear automata over rational numbers. An upper bound of automata orders is proved.
Keywords: linear automata, order in semigroup.
2020 year, volume 24, issue 3 (PDF)
The adoption of effective management decisions in the field of healthcare and disease prevention can increase the duration and quality of life. The process of making such decisions takes place in conditions of limited completeness and reliability of the available information and has a significant expert component. The paper presents one of the approaches that allow making informed decisions in the field of preventive medicine.
Keywords: reventive medicine, process evaluation and monitoring, hybrid intelligence.
The question of whether a word belongs to a given regular language finds its application in areas where it is relevant to search for certain patterns in data of different nature. Growth of the deterministic finite automaton (DFA) states number which is exponential in number of regular expressions of the given language is still a real problem. In this article, we take a look at modifying a finite automaton by using compression algorithms. These approaches modify the finite automaton without changing the language and without adding additional structural elements.
Keywords: DFA, NDF, regular language, exponential blowup, compression algorithm.
The dynamic system of field and bugs - colony - them is considered. Bugs live on the field that is modeled by integer lattice in each sell of which there are the same count of the food for bugs at the first moment. Bugs must move around field or eat food or divide or dye according to the some algorithm moreover all activities spending energy. This system is modeled by cellular automaton. The colony whose linearized population size infinite number of times crossing line from some class built in this work.
Keywords: automaton modelling of biological system, growth rate of homogeneous structures, cellular automaton.
This paper is concerned with the learning complexity of Boolean fixed-weight functions using membership queries, comparation queries, equivalence queries, and extended equivalence queries. Moreover, it is allowed to use only one type of queries during learning. This paper gives exact values of learning complexity for all the types of queries besides comparation queries. The paper presents the upper bound on learning complexity for comparation queries. In addition, the paper demonstrates that the upper bound is equal to the lower bound for the 1-, 2-, 3-weight functions.
Keywords: Boolean fixed-weight functions, membership queries, comparation queries, equivalence queries, extended equivalence queries, exact learning.
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).
Keywords: cellular automata, homogeneous structures,the closest neighbour search problem.
In the present paper, we find the lattice of 1-traces of closed classes of piecewise linear functions.
Keywords: piecewise linear functions, continuous piecewise linear functions, finite-parallel functions, continuous finite- parallel functions, continuous finite linear functions, piecewise parallel functions, finite linear functions, parallel finite linear functions, 1-trace lattice, Heaviside function, 2-precomplete class.
2020 year, volume 24, issue 2 (PDF)
In this article the problem of planning personal learning strategy is set and results of applying various approaches to its solution are presented.
Keywords: computer education system, sequence elements prediction, neural network, recurrent neural network, compact prediction tree.
Using the technology of training neural networks, the knowledge distillation, models were obtained that solve the binary classification problem with the productivity that is about five times higher than the performance of the teacher network with an insignificant drop in quality. The convolutional neural network ResNet-18 was trained in two ways by this technology (using the pre-trained network ResNet-50) and by the classical method. The concept of the degree of uncertainty of the model on objects’ set is introduced as the quantity of the deviation of the neural network predictions from the values accepted for the answer. The experiments on the recursive application of the knowledge distillation technology were also conducted.
Keywords: knowledge distillation, binary classification, residual neural network, convolutional neural network, degree of uncertainty of the model on objects’ set, recursive training of neural networks.
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.
Keywords: image code, image encoding, affine equivalence.
The present paper considers the cooperative game about the transport delivery on the rectangular grid. The concepts of congestion and cars collision on it, as well as the automata as the agents in the traffic lights of the grid regulating movement of transport, are introduced. It’s proved that there exists a structure of the automata with local area of visibility leading to the self-organization of the system of traffic lights ensuring an arbitrarily long, correct transport delivery without any congestions and cars collisions for any number of grid’s outputs.
Keywords: cooperative game, delivery, traffic organization, agent, homogeneous structure, automaton.
Relationship between the problem of minimization of the number of states of fuzzy automata and the problem of mining of interval pattern concepts with maximum extent is considered. The clustering method based on interval pattern concept mining combines states of a fuzzy automaton into subsets with similar patterns of confidence of transition into other states, where patterns are considered close to each other if the distance between them is bounded by a predetermined parameter σ. It is shown that for a certain type of fuzzy transition matrices the behavior of the original fuzzy automaton, as well as the behavior of the minimized one, eventually stabilizes. Moreover, it is proved that the membership value of each word recognized by the fuzzy automaton does not decrease after minimization. This fact allows comparing the fuzzy language recognized by the original automaton and the language recognized by the minimized automaton.
Keywords: fuzzy automata, interval pattern concepts, fuzzy languages.
This article introduce new type of math object — cellular automaton with locators. It was created by implementing new functionality for automaton - broadcasting “on-air” signals and retrieving generalized “on-air” signal from all elementary automata. This article highlights some tasks whose solution will be greatly simplified by using cellular automaton with locators instead of traditional cellular automata.
Keywords: cellular automata, homogeneous structures, firing squad problem, motion picture design, constructing the shortest path.
The automaton predicts the character of the input sequence, if it outputs this character at the previous time. The paper introduces the concept of the degree of prediction on a superword segments. The question of the relationship between prediction on superword segments and prediction on superwords is investigated. We obtained results that allow us to judge the degree of prediction on superword segments if we know degree of prediction on superword and vice versa.
Keywords: predicting automaton, prediction of superwords with automatons, prediction degree on finite subsequency.
We consider the order problem for linear automata. A finite order criterion for linear automata is presented that provides an algorithm solving this problem. An upper bound of linear automata orders is proved.
Keywords: finite automata, linear automata, order in semigroup.
2020 year, volume 24, issue 1 (PDF)
An algorithm for verification of formalized mathematical proofs is considered. Its main part is described in the framework of some production system with metavariables. Theorems of soundness and completeness are proved.
Keywords: automated theorem proving, system for automated deduction, first order language, predicate calculus, production system, artificial intelligence.
In the paper we introduce graphical objects (called state diagrams) related to functional programs. It is shown that the state diagrams can be used to solve problems of verification of functional programs. The proposed approach is illustrated by an example of verification of a sorting program.
Keywords: program verification, functional programs, state diagrams.
Interpretability of the solution, the possibility of unsupervised learning, scalability made topic modeling one of the most popular tools for statistical text analysis. Topic models make it possible to reduce the dimension of the data space, since they describe each document as a probabilistic mixture of abstract topics, each topic as distribution over the vocabulary words of a collection. The transition from the space of words into the space of topics leads to a natural solution of the problems of synonymy and polysemy of terms. However, there are a number of disadvantages caused by the dependence of the solution on the initialization. The instability of topic models is a well-known fact, but the problem of completeness related to it is still not studied in the literature. To solve this problem, the article explores a new algorithm for finding a complete set of topics based on the building of the convex hull. Experimentally confirmed the effectiveness of this algorithm. In practice, a complete set of topics was used as the initialization of the ARTM (additive regularization for topic modeling) model. Compared with the randomized initial approximation, the basis topics allows to increase stability, perplexity by more than 10%, coherence by several times.
Keywords: probabilistic topic modeling, stability of topic models, complete set of topics of topic models, latent Dirichlet allocation, LDA, regularization, ARTM, BigARTM.
A semantics of the arithmetical realizability based on hyperarithmetical sorts for formulas of the language of set theory is introduced. It is proved that constructive set theory without the extensionality axiom is sound with this semantics.
Keywords: constructive semantics, realizability, arithmetical realizability, axiomatic set theory, hyperarithmetical sorts.
The paper considers one-dimensional convolutional schemes in the McCulloch-Pitts basis. It is shown that the considered schemes can be implemented by a scheme from the a priori and dynamic parts, in which the calculations in the a priori part are independent of the input data. In this case, the a priori and dynamic parts have a nonlinear depth equal to 2.
Keywords: convolutional neural network, neural scheme, nonlinear complexity, McCulloch-Pitts model.
This paper is devoted to the study of relationship between proper families of Boolean functions and unique sink orientations of cubes. A one-to-one correspondence between these two objects is established, a number of properties are carried over from unique sink orientations to proper families. These results include an upper bound for the number of proper families of given size and coNP-completeness of the problem of recognizing properness.
Keywords: proper families of Boolean functions, unique sink orientations.
The machine predicts the next character of the input sequence if it outputs that character the moment before. The paper considers the machine class contraction for the task of predicting an arbitrary general regular super-event in the multivalued alphabet. The class of machine sufficient for the predicting problem is obtained in this paper. In addition, the transition from the estimations of simple super-events to the estimations of the complex super-events is proved with the help of the class aforementioned.
Keywords: predicting machine, prediction of superwords by a machine, general regular super-events.
For coefficients of polynomials of functions over finite fields Fq , we consider the problem of finding a lower bound for the maximum minimum of the number of nonzero coefficients in the polynomial, where the maximum is taken over all functions and the minimum is taken from their transformations corresponding to various field assignments. Moreover, various types of such transformations are considered. The main results of the paper relate to two types of transformations, the description of which is given in the first section of the paper. The paper estimates L(q) ≥ q − 2 for the maximum minimum of the number of nonzero coefficients in the polynomial for the certain type of transformations that leave the zero field element in place.
Keywords: coefficients of polynomials, Boolean functions, polynomial of a Boolean function, table of values of a function, sagemath.
This work is devoted to describing the change in the dimension of periodic subsets of the natural series with seemingly insignificant operations like removal/addition to the set of one number. The case is investigated when the dimension of the initial set is equal to 1 or 2. By the dimension of the set is meant the minimum number of disjoint arithmetic progressions that give this set in the union. For sets of dimension 2 the result is obtained only in cases of pairs of general position progressions. In this paper we give the results on how the dimension changes depending on whether the number x is deleted/added to.
Keywords: arithmetic progression, natural series, progressive set.
We prove that almost any Boolean function on n variables can be implemented by an irredundant two-pole contact circuit allowing a single diagnostic test of length 8 regarding breaks and closures of contacts.
Keywords: contact circuit, Boolean function, contact break, contact closure, single diagnostic test.