Русский язык
2021 year, volume 25, issue 4 (PDF)
Cluster analysis has a very wide range of applications; its methods are used in medicine, chemistry, archeology, marketing, geology and other disciplines. Clustering consists of grouping similar objects together, and this task is one of the fundamental tasks in the field of data mining. Usually, clustering is understood as a partition of a given set of points of a certain metric space into subsets in such a way that close points fall into one group, and distant points fall into different ones. In this paper, we offer a local averaging method for calculating the distribution density of data as points in a metric space. Choosing further sections of the set of points at a certain level of density, we get a partition into clusters. The proposed method offers a stable partitioning into clusters and is free from a number of disadvantages inherent in known clustering methods.
Keywords: cluster, algorithm, density, averaging method.
This paper tells about the scientific school of Professor Valery Borisovich Kudryavtsev and the department of the mathematical theory of intelligent systems created by him.
Keywords: Automata theory, theory of intelligent systems, pattern recognition.
Many combinatorial problems, such as graph coloring and solving of linear equations, can be expressed as the constraint satisfaction problem for some constraint language. Some of these problems are solvable in polynomial time, while others are NP-complete. In 2017 the complexity of the constraint satisfaction problem was described for any constraint language on a finite set, but there are many other variants of this problem whose complexity is still not known. For instance, we could allow to use both universal and existential quantifiers, or require the solution to be surjective or balanced. Another variant is to require the input to satisfy an additional condition. As an example we could consider the problem of coloring a graph in 100 colors if we know that the graph is colorable in 3 colors. In the paper we discuss the usual constraint satisfaction as well as the complexity of these and other variants of the constraint satisfaction problem.
Keywords: constraint satisfaction problem, computational complexity, CSP, quantified CSP.
The human brain is obviously a “generic“ object for determining, including artificial “intelligent systems“. However, the mechanisms of the actual intellectual activity of the brain still remain undiscovered in their most essential part. To a large extent, this is due to the also obvious fact that natural intelligence in a broad sense has the property of a subjective representation of reality, the operational architectonics of which, its formats and completeness of description are unknown to us. In this regard, and taking into account the absence of a “general theory of the brain“, it becomes problematic to create neuromorphic artificial intelligence systems based on analogies. The level of such “neuromorphism“ will be entirely determined by the boundaries of our understanding of how the human brain works. Meanwhile, the neuromorphic property of artificial intelligence systems can be achieved not so much by building brain-like structural and functional architectonics of these systems (artificial neuron networks, deep learning algorithms, etc. D.), how much through their training of two-way communication with natural intelligence. We believe that the channels of brain-artificial intelligence information interaction for launching the learning processes of “communication“ can be built on the basis of technologies of non-invasive brain-computer interfaces (BCI) of a new generation. The key link of these technologies will be feedback loops, within which artificial intelligence modules connected to EEG analysis will demonstrate to a person through natural sensory channels their hypotheses regarding the belonging of specific EEG patterns to certain mental acts of a person. In the interactive process, these hypotheses will be refined to full convergence, thus forming interaction trajectories in the memory of the human and machine brains to an acceptable level of “mutual understanding“. The report will discuss in detail the neurophysiological and neurotechnological grounds for creating “brain-artificial intelligence“ interfaces.
Keywords: human brain, electroencephalogram, brain-computer interfaces artificial intelligence, neuromorphic systems.
The paper briefly describes the main ideas of the algebraic theory of automata and its connection with the algebraic theory of semigroups. An automaton is considered as a polygon over a semigroup. The main directions to develop polygon theory are indicated.
Keywords: automaton, semigroup, polygon over a semigroup, algebraic theory of automata.
This paper describes a series of experiments on finite automata and identifies classes of potentially simple and potentially complex regular expressions leading to an exponential explosion in the number of states.
Keywords: finite automata, regular expressions, exponential explosion, computational experiments.
The simplest system of viral dynamics equations (cite covid) was studied. An analytical solution to the system was derived. Also, formulas for peak viral load and times for reaching the maximum and safe values of viral load were derived.
Keywords: differential equations, Lotka-Volterra, COVID-19.
We study closed classes of the functional system of rational functions with rational coefficients that play the key role in deciding completeness.
Keywords: functional system, completeness, closed classes, rational function.
The present paper is concerned with graded quasi-Frobenius rings and modules. The connection between different definitions is established, a series of equivalent characteristics are obtained.
Keywords: graded rings and modules, quasi-Frobenius rings, quasi-Frobenius modules, Frobenius algebra.
This paper presents an automata model for learning neural networks, implemented using the high-level programming language python and tested on the problem of binary classification. Also, within the system under consideration, a procedure for automating the neural network training by choosing a training strategy from the point of view of "best practices" is implemented.
Keywords: artificial neural networks, finite automata, non-finite automata, system for working with neural networks, automated machine learning, autoML, hyperparameter optimization via best practices, computer vision, CV, binary classification.
There exists a way to calculate the amount of regions of a hyperplane arrangement using its characteristic polynomial. This allows using hyperplane arrangements in solutions of combinatorial problems. This paper considers a hyperplane arrangement constructed with a subset of a set of all simple paths in a graph. Results in this paper connect this arrangement to the maximum matching problem and allow to calculate its characteristic polynomial for specific cases of the initial graph.
Keywords: hyperplane arrangement, graphical arrangement, maximum mathcing problem.
This paper describes a cellular automaton with locators which solves the closest neighbor search problem. The problem itself is about finding the closest point from a given finite set to the so-called central cell. Unlike the classic cellular automaton model, cellular automata with locators allow fast signal transmission to any distance. It is proven that such a possibility allows us to solve the problem in a constant time which is fundamentally different from the one dimensional case: the lower complexity estimate for this case is proven to be logarithmic.
Keywords: cellular automaton with locators, homogeneous structures, the closest neighbour search.
An algorithm for calculating the Belyi functions via modular functions is described. A Belyi function with the monodromy group M24 calculated using this method is presented.
Keywords: dessins d’enfants, Belyi functions, modular functions.
The paper describes the use of deep neural networks and the method of moving separation of mixtures to construct models for analyzing the foreign exchange market and choosing trading strategies. The architecture of a neural network and methods of statistical extension of the feature space are considered. The results of a trading model demonstrating the advantages of the proposed approach are presented.
Keywords: deep neural networks, LSTM, moving separation of mixtures, currency pairs.
Switchable power of flat automatic schema without inputs implementation by periodical sequence is recieved in this work. A scheme is given that implements arbitrary pre-defined sequence of length \[ 2^n \] for positive integer n with switchable power no more than \[ \frac{2^{n/2}}{n} \].
Keywords: plain circuits, switchable power, upper bounds, Shannon function.
We show that the problem of deciding properness of a family of functions specified by a circuit is coNP-complete, and propose procedures for generation of all proper families of a given order and of uniform distribution on the set of proper families.
Keywords: proper families of functions, Markov chains.
We describe an algorithm that decides the presence of n- subquasigroups, estimate temporal and spatial complexity of this algorithm and investigate practical efficiency.
Keywords: n-quasigroup, n-subquasigroup.
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.
Keywords: Cellular automata with locators, key-value databases.
In this paper, we consider automata that traverse connected plane simple undirected graphs in order to establish their properties. An algorithm is presented, using which an automaton with two colors can determine whether the graph it traverses is a tree or a pseudotree, and upper bounds are determined for the number of steps that the automaton must make.
Keywords: Automata, graphs, trees, pseudotrees.
In this paper, volumetric circuits are researched. They are the embedding of Boolean circuts of logic gates in space. A class of volumetric circuits implementing partial Boolean operators was explored. Define the potential — a measure of power equal to the number of circuit elements issuing a one on a given input. For this class of volumetric circuits, a lower estimate of the potential is obtained. The order of the Shannon function of the potential for a class Boolean operators for volumetric circuits without constraints and Boolean circuits with near outputs is obtained.
Keywords: Boolean circuits consisting of logic gates, volumetric circuits, power of Boolean circuits, potential.
The work is concentrated on the study of deep neural network architectures with implementation of mixtures of normal distributions in hidden layers for solving clustering and regression problems. The model with different sets of hyperparameters was compared to classical methods: k-means, linear regression, Gaussian mixture models (GMM), etc.
Keywords: deep neural networks, mixtures of normal distributions, EM algorithm.
The author investigates the number of possible labelings of the edges of a strongly connected directed graph so that the resulting Moore diagram corresponds to some abelian automaton. It is proved that in the case of an alphabet of two elements, such a labeling is unique (except for the extreme case), and the algorithm for such a labeling is given. In the case of an alphabet with a larger number of elements the exponential dependence of the maximum number of labelings on the number of vertices is proved.
Keywords: abelian automata, automation diagramm, transition graph, labelings of automation graph, structure of automation graph.
Growth rate is a function defined for an arbitrary finite set A with a set of operations M defined on it. Its order characterizes the strength of given operations. We show that if there is only a finite number of important essential predicates among all predicates that are preserved by each function from M then the growth rate order of the (A, M) pair is logarithmic.
Keywords: growth rate, finite sets, constraint language, logarithmic growth rate.
For non-adaptive group testing, a method is proposed to accelerate the computing of the test function when assessing the quality of the threshold decision rule for making a decision on the positivity of a set of samples. Acceleration is achieved by using, along with dual blocks, a combinatorial block diagram of its blocks corresponding to the elements of the analyzed set.
The correspondence between Grothendieck dessins d’enfants and Belyi pairs on reducible curves is discussed. Much attention is paid for the applications.
Keywords: dessin d’enfants, embedded graphs, Belyi pairs.
The paper considers the implementation of various motion laws of a point on an infinite screen by a cellular automaton. Algorithms for constructing images for three classes of motion laws are found. It is shown that for modeling these motion laws of a point on a ray, the minimum number of a cellular automaton states is 4.
Keywords: cellular automaton, number of states, infinite screen, bidirectional motion, image construction.
In this work we consider the problem of secure union of systems with take-grant models from the point of view of adding new accesses and corresponding of subjects. Union of systems is considered secure if the set of accesses did not change for each individual system. We obtain the criteria of secure union for each union type.
Keywords: formal secutity models, take-grant model, secure union.
The paper considers the author’s algorithm, which allows obtain a hardware implementation of an arbitrary system of m Boolean functions from n variables and its application to balanced S-blocks. This is followed by a comparison of hardware implementations of S- blocks obtained in terms of complexity.
Keywords: S-box, hardware implementation, circuit complexity optimization, stream ciphers, block ciphers.
The paper establishes the order of growth of the Shannon function of the length of the checking test relative to the source of faults, which can arbitrarily swap any k of consecutive inputs of the circuit.
Keywords: checking test, tests on circuit inputs, Shannon function, permutations.
It is proved that, in any complete basis, any Boolean function can be realized by an irredundant circuit that admits a diagnostic test of length no more than 3 in case of inverse faults at the outputs of gates.
Keywords: Boolean circuit, single fault diagnostic test set, inverse fault at output of gate, Shannon function, easily testable circuit.
It is proved that any Boolean function can be realized by a k-irredundant Boolean circuit over an special finite complete basis such that the circuit admits a multiple fault k-diagnostic test set of cardinality at most 2 under inverse faults at outputs of gates.
Keywords: Boolean circuit, test set, inverse fault at output of gate, Shannon function.
In AI applications, one has to work not only with features, but also metric descriptions of objects. This requires the development of a special set of methods for constructing, converting, correcting and using metric descriptions. We provide a systematization of the methods. In particular, a new approach to the problem of part matching is considered. First, we propose to use the ’universal graph’ as a way to enrich an individual matching problem with general information about the domain. This reduces the part matching problem to the graph matching problem. Second, we propose a fast graph matching method based on metric learning. At the same time, we generally avoid the quadratic assignment problem, which allows us to achieve high computational efficiency. Experiments demonstrate good performance compared to conventional methods.
Keywords: metric descriptions of objects, composite objects, part matching, graph matching, graph convolutional networks, distance metric learning.
Algorithms for primitive elements are realised (in the system of computer algebra SageMath). In particular, we have calculated the number of primitive elements of free non-associative algebras over finite fields for some cases.
Keywords: free non-associative algebra, primitive element, computer algebra.
Partially ordered algebraic systems such as linear spaces over partially ordered skew fields, pseudo-ordered rings and algebras over partially ordered fields are considered. This order of a ring (an algebra) is similar to a partial order of a Lie algebra, which was introduced by Kopytov. Those orders are induced onto nonassociative rings (algebras) (Lie rings, Jordan rings, for example) by partial orders of their additive groups. Second and third theorems of order isomorphisms for interpolation ordered systems are proved.
Keywords: partially ordered linear spaces, rings and algebras, interpolation groups, order homomorphisms.
The task of appointing a commander is as follows. At the initial moment of time, each cell of a two-dimensional cellular automata can be white or black. The black cells together make up a connected figure. It is necessary that in the final configuration, exactly one black cell passes into the special “commander” state. An upper bound is obtained for the time required to solve the problem.
Keywords: Plane cellular automata, connected figure, appointment of a commander.
In this work it is shown that there exists an asymptotically good family of quantum LDPC codes, which proves the qLDPC conjecture. We also show that there exists an asymptotically good family of classical locally testable codes with constant query and soundness parameters, which also gives a positive solution of a well-known conjecture in the field of classical locally testable codes.
Keywords: locally testable codes, quantum LDPC codes, asymptotically good codes.
A new low-complexity heuristic method for generation of real-valued test matrices with required condition number is proposed. It makes practical selection of methods for solving linear algebra problems easier.
Keywords: systems of linear equations, condition number, matrix spectrum, test matrices.
This paper discusses the issues of computer modeling of problem solving processes and automatic creation of solver techniques. The architecture of the process of transitionfrom theorems to techniques (algorithmization of knowledge), which has developed in the process of processing numerous examples, is described. A computer system has been created that allows solving problems from various branches of mathematics and is able to update its database of techniques.
Keywords: computer problem solver, logical system, artificial intelligence.
A regular graph of the ring of matrices over a field is a graph on the set of invertible matrices. Two matrices are connected with an edge if and only if their sum is singular. One of the questions in this field is whether the chromatic number of this graph is finite or not. This question was first formulated in 2009 at the 22nd British Conference on Combinatorics. It remains open for the fields of the characteristic 0. To investigate this issue in the article [4] was introduced a definition of a regular graph of a set. The regular graph of a set generalizes the concept of the regular graph of the matrix ring. There is a close connection between these concepts. For example, if the chromatic number of a regular graph of a circle on the Euclidean plane is infinite, then so will be the chromatic number of a regular graph of the matrix ring of order higher than two. In this paper, we investigate the structure of regular graphs of sets of three elements and classify the graphs up to isomorphism.
Keywords: regular graph of the matrix ring, classification of graphs up to isomorphism.
Conditions for K-completeness and A-completeness for linear automata systems, functioning over the field of rational numbers are described.
Keywords: finite state automata, linear automata, rationals, K- completeness, A-completeness.
The paper investigates the problem of finding deviations from the known scenarios of typical use of web applications. The modification of existing formal problem is considered, for which the recursive method for checking trace matching to a pattern is proposed. An algorithm for detecting anomalies in trace is developed, which is effective with respect to the trace length and the pattern size.
Keywords: anomaly detection, DAG, sequence analysis.
The paper provides an algorithm for obtaining a simple quasigroup from a given one in isotopic way, proves that the algorithm has quadratic complexity and that the result doesn’t contain proper subquasigroups. Python implementation of the algorithm is given.
Keywords: quasigroup, simplicity of quasigroup, subquasigroup, isotropy of quasigroups, Latin square.
All precomplete classes are found for classes of linear automata over finite fields with superposition operations.
Keywords: finite automaton, linear automaton, operation of superposition, completeness, maximum subclass, finite field.
We formulate the problem of shelf space allocation with various product position options (side orientation, cappings and nestings). A method for linearizing nonlinear constraints arising in this model is presented. This technique allows finding the optimal solution to the problem, including the large instances of input data.
The present paper considers online learning problem where training data becomes available in a sequential order. "Stripe" algorithm proposed by V.A. Yakubovich is used for online learning. Its applicability for online machine learning is confirmed by comparison with a traditional model trained using stochastic gradient descent.
Keywords: online machine learning, linear models, "Stripe" algorithm.
The work considers the task of establishing of optimal transport planning zones for several objects. The proposed new algorithm is based on graph traversal, which uses hexagonal grid generation over a map to speed up the computations. Commonly used algorithms for solving the task are also discussed in our work: for one object – isochrones that generalise in case of objects’ multiplicity; for several objects – the Voronoi diagram. These approaches and their modifications are compared with the new algorithm.
Keywords: Big Data mining, geospatial analysis, optimal transport planning zones.
An approach to automatic extraction of terms from an individual scientific text is reported, which combines known methods: linguistic patterns, statistical terminological measures, methods of graph ranking. The combined methods and stages for extracting, selection and ranking of terms are described, which are implemented for processing documents in Russian. The results of experiments on extracting terms from educational texts in mathematics and programming are presented. The scores of extraction efficiency (74% of average accuracy) show that the described approach is promising.
Keywords: natural language processing, automatic term extraction, linguistic templates, graph ranking methods.
NEREL is a Russian publicly available dataset for solving named entity recognition problem and relation extraction problem. The dataset contains more than 56K tagged entities and more than 39K relationships. An important difference between NEREL and previous datasets is the presence of markup for nested named entities. The methods of extracting nested named entities differ from the methods of extracting ”flat” named entities primarily by the architecture of the solution. Since NEREL provides annotations for nested entities, the article compared various approaches to solving this problem with the transfer to Russian language domain.
Keywords: NER, nested NER, named entity recognition, nested named entity recognition, dataset.
The paper considers the application of the developed method based on the use of meta-vector representations of words for automated (using annotators) enrichment of a domain taxonomy. The information security domain is considered, which is used to enrich the Ontology of Natural Sciences and Technologies (OENT).
Keywords: taxonomy, meta-embedding, vector representation, interface.
Existing pruning algorithms can achieve good quality on sparse neural networks. But the recieved sparse architectures, when training from scratch, often can’t achive the same quality as pruning (especially for very sparse networks). In this work the weights restoring method to improve training from scratch quality is described.
Keywords: neural networks, pruning, sparse architectures, "the lottery ticket" hypothesis.
This work is devoted to road pavement cracks segmentation problem. Proposed a Unet-like network with a pre-trained ResNet18 as an encoder (without two last classification layers) and a standard decoder is proposed. It is shown that this architecture, together with a strong augmentation system and a well-chosen loss function, is capable of surpassing state-of-the-art solutions in terms of various quality metrics.
Keywords: machine learning, neural networks, crack detection.
In this paper we propose Gradient Mask, which helps the network to filtering out noisy or unimportant features while training. We propose a new criterion for gradient quality which can be used as a measure during training of various convolutional neural networks (CNNs). We demonstrate analytically how lateral inhibition in artificial neural networks improves the quality of propagated gradients. Finally, we conduct several different experiments to study how Gradient Mask improves the performance of the network both quantitatively and qualitatively.
Keywords: lateral inhibition, gradient masking, convolutional neural networks.
This work continues series of works in neural networks architectures estimatons approximating some classes of functions. The following paper considers the problem of improving upper-bound estimation of neural network closely approximating particle-linear dependences.
Keywords: schema of functional elements, neural networks, functions approximation, particle-linear functions.
The paper proposes a method for constructing a distributed controller of a special type for the stabilization of a system with a delay, based on the use of genetic algorithms. Numerical modeling and analysis of the obtained results are carried out.
Keywords: time-delay systems, stabilization, genetic algorithms.
Considered the experience of the educational robotic project implemented by the staff of Faculty of Computational Mathematics and Cybernetics of the Lomonosov State University of Moscow on the basis of the University Gymnasium (boarding school) of MSU. The paper provides a description of the project and its current state. Presented the interim results of pedagogical activity. Considered questions about the complexity of running projects in robotics and their compliance with the level of education of senior students.
Keywords: research educational project, robotics, educational model.
This paper deals with nonlinear programming problems, in which the cost function and constraints are relatively small expressions containing variables with indices. Analysis of problem expressions dependence on indices gives sparsity structure of Jacobian and Hessian of the Lagrangian. This allows to get general formulas for calculating their non-zero elements and leads to effective numerical solving the nonlinear programming problem.
Keywords: trajectory planning, nonlinear programming, sparse Jacobian and Hessian of the Lagrangian, IpOpt, SymPy.
Parameters of activation functions contribute a lot to the performance of differential neural network-based identifiers. An approach to optimize these parameters is proposed and demonstrated for the problem of identification of platform dynamics.
Keywords: differential neural networks, global optimization, simulated annealing algorithm.
We consider a notion of relative degree for hyperoutput systems (i.e. the systems that has more outputs than inputs). Relative degree conditions are restrictive (the same is true for a square systems — the systems that have the same number of inputs and outputs), furthermore, these conditions are not invariant under output change. We consider a problem of reducing a hyperoutput system to a form with relative degree. To solve the problem we indroduce generalizations of relative degree, similar to the square-system’s case. Using these generalization we solve the problem.
Keywords: relative degree, hyperoutput systems.
The aim of the research is to develop algorithms for constructing digital stabilizers for switchable systems operating under parametric uncertainty. To solve this problem, it is proposed to use the following methods: exact discretization of continuous controlled systems, the theory of superstabilization, the theory of linear matrix inequalities and intelligent computing.
Keywords: switchable systems, interval uncertainty, stabilization, robust stability, digital control systems, intelligent computing.
The electrical activity of the brain was detected in tasks on the perception and pronunciation of individual phonemes and syllables of the Russian language under various conditions of initiation of the pronunciation process. The conditions for initiation were visual presentation (a letter was shown), auditory presentation, and also auditory presentation of conditioned stimuli (words in an unfamiliar language to the subject, previously associated with the corresponding phonemes). EPs were obtained for a group of 25 subjects for perception and internal pronunciation of 7 phonemes and 10 syllables for each of the initiation conditions. As a result, it was shown that the averaged evoked potential for the signal of pronouncing phonemes and syllables depends on the initialization method. This is important to consider when developing methods for decoding internal speech and automatic classifiers.
Keywords: EEG, EP, internal pronunciation, syllables, phonemes, words, conditioned stimuli, non-existent words, Japanese.
This study is devoted to short-term dynamics of establishing of cognitive maps of a novel environment in the hippocampus of freely behaving mice. The average time required for stable spatial neuronal representations to establish was evaluated and spatial selectivity of these cognitive maps was characterized. It was shown how these parameters evolved on further days of the experiment and a population analysis of neuronal activity was performed to verify these results.
Keywords: place cells, place fields, cognitive map, hippocampus.
The brain functioning is based on the parallel synchronous work of the neural networks, the architecture of which determines the properties of the cognitive processes. To construct functional connectomes of the human brain, data from non-invasive methods are usually used: electroencephalography (EEG), magnetic encephalography (MEG), and functional magnetic resonance imaging (fMRI), obtained in stimulus cognitive tasks or at resting state. For each combination of the above experimental methods and the studied cognitive process, there are features in the methods of constructing functional connectomes. Of particular interest is the study of neural network interaction at resting state, as a basic level of consciousness, based on the use of data from the fMRI method. With a bad spatial resolution (about 2 mm) and temporal signal resolution (0.5 Hz), fMRI is the only modern method for the simultaneous registration of physiological signals from the cortex and deep structures of the brain. In this work, using the fMRI data of the brain resting state as an example, we describe the characteristic features of the construction of functional connectomes.
Keywords: neural networks, fMRI, functional connectome, global signal, functionally homogeneous regions, stationarity, autocorrelation, functional atlas, resting state.
A binary classifier based on a convolutional and recurrent neural network, showed accuracy equal to 60% on average, with a maximum value of 78.9% when classifying EEG data from people who have undergone SARS-CoV-2 (COVID-19) and people who did not meet the SARS criteria. The data obtained support the hypothesis about the presence of the brain electrical activity patterns in people who have undergone SARS-CoV-2 (COVID-19).
Keywords: COVID-19, EEG, neural network, SARS-CoV-2.
In applied machine learning, the problem of sample heterogeneity is often encountered. For example, the sample heterogeneity leads to serious difficulties in solving the problem of brain electrical activity patterns recognition when developing a brain-computer interface for people of different social characteristics. In this work, we proposed a new criterion of clustering quality based on the features selection, which has low computing needs and is based not on the proximity / remoteness of the sampled objects, but on the ability of an algorithm to recognize hidden patterns, that is, to select groups that are similar in features. We have shown the areas of practical application of the algorithm, in particular, in the task of brain electrical activity patterns recognition when pronouncing 8 words by people with different social characteristics.
Keywords: clustering, criterion of clustering quality, brain- computer interface.
The paper promotes a synthetic approach to the formal representation of reasoning in artificial intelligence. The basis of this approach is the provisions of the dual process theory, which make it possible to distinguish between elementary, fast, intuitive basic reasoning and controlled, conscious, slow reasoning based on reflection. Another source of my approachi are developed in logic and formal argumentation ideas of the representation of meta-reasoning as a transformation of the original reasoning.
Keywords: human compatible artificual intellegence, metareasoning, transformation of reasoning.
We consider the joint logic of problems and propositions QHC suggested by S. A. Melikhov. We prove that this logic is complete with respect to Kripke models obtained by enrichment of Kripke models with audit set for a propositional part HC of this logic. We also show that this logic conservatively extends the predicate version of intuitionistic epistemic logic IEL+ constructed by S. Artemov and T. Protopopesku.
Keywords: non-classical logics, modal logic, Kripke semantic.
The computer-assisted proof of Four Colour Map theorem published by Kenneth Appel, Wolfgang Haken and John Koch back in 1977 prompted a continued philosophical discussion on the epistemic value of computer-assisted mathematical proofs. We show, developing the approach proposed by O.B. Brassler in 2006, how the Univalent Foundations of Mathematics (UF) meets some earlier stressed epistemological concerns about computer-assisted proofs and thus offers a new possibility to fill the gap between computer-assisted and traditional mathematical proofs. We demonstrate the argument with a simple computer-assisted proof from Algebraic Topology.
Keywords: Univalent Foundations, Computer-Assisted Proof, Spatial Intuition.
In the paper, one analyzes knowledge representation in S. Jaśkowski’s discussive (discursive) logic D2 which is one of the pioneering paraconsistent logics. One shows an opportunity to simplify its axiomatization and suggests some decision of the axioms’ independence problem.
Keywords: discussive logic, discursive logic, paraconsistent logic, knowledge representation.
2021 year, volume 25, issue 3 (PDF)
A combinatorial approach to the strict consensus ranking problem for a given set of nonstrict orderings of alternatives is considered. A concept of light score matrix (skew-symmetric) is introduced providing more simple and clear optimization process and its result. Some heuristic search procedures are formulated allowing optimal strict consensus rankings (including multiple) to be found in different cases.
Keywords: rankings, Kemeny median, skew-symmetric matrices, parallel generation of permutations, Julia language, OpenCL.
The Fermat—Steiner problem is to find a point in the metric space \[ Y \] such that the sum of the distances from it to the points of some finite fixed subset \[ A \subset Y \], called the boundary, is minimal. We will call the minimal sum of distances the length of the minimum astronet. We consider this problem in the hyperspace \[ Y = H(X) \] of nonempty, closed and bounded subsets of the proper metric space \[ X \]; moreover, the Hausdorff metric is introduced on \[ H(X) \]. Since \[ X \] is proper space, all elements of \[ H(X) \] are compact. Each solution of the Fermat—Steiner problem will be called the Steiner astrocompact; its set is divided into classes with equal weight, each of which corresponds to its own vector of distances to the boundary compact sets. In this article, we prove three sufficient conditions for the given compact set to be a Steiner astrocompact for a given boundary. Also, these conditions guarantee the uniqueness of the class of Steiner astrocompact spaces with equal weight. This theory is used to completely solve the Fermat—Steiner problem for some symmetric convex three-element boundaries in \[ \mathbb {R}^2 \], and this is demonstrated by examples.
Keywords: Fermat-Steiner problem, star network, minimal astronet, Steiner astrocompact, hyperspace, Hausdorff distance, metric projection, point-to-set distance function, first variation.
It is proved that the Shannon function for the test length with respect to a read-once alternative in the elementary basis augmented with all weakly read-multiple unate functions does not exceed \[ 3n − 2 \].
Keywords: read-once functions, checking test, weakly read-multiple functions.
The paper studies one special type of interaction of automata collectives in labyrinths. The following problem is considered for a given class of labyrinths: for which pairs of collective types there is a collective of the first type and a collective of the second type that will certainly meet, if at the starting moment they are placed in any two vertices of any labyrinth of the given class. We call this the problem of the ‘type meeting’ for automata in the given class of labyrinths. Here the problem is completely solved both for the case of the class of all finite plane mosaic labyrinths and for the case of the class of all finite plane rectangular labyrinths. The problem remains unsolved so far for the case of all (finite and non finite) mosaic labyrinths for some pairs of collective types, whereas for the case of the class of all plane rectangular labyrinths, the problem of type meeting is completely unexplored.
Keywords: collective of automata, collective type, plane rectangular labyrinth, plane mosaic labyrinth, type meeting.
The paper presents a number of formulas for the characteristic function of the Boolean solution linear equation with integer coefficients. The function arguments are binary expansions of these coefficients.
Keywords: linear equation, Boolean solution, characteristic function.
For a finite system of piecewise parallel functions implemented by schemes of linear elements and Heaviside functions, the criterion for the expressiveness of piecewise constant functions is obtained, supplemented by all single linear functions. Thus, the criterion of expressiveness of the binary classifier implemented by the McCulloch-Pitts neural scheme is obtained.
Keywords: Piecewise constant function, piecewise parallel function, completeness problem, expressibility problem, McCulloch-Pitts neural circuits.
There is a function \[ d_{(A,M )} (n) \] called growth rate that is defined for an arbitrary finite set \[A\] with a set of operations \[M\] defined on it. It characterizes the strength of given operations. It has been proved that growth rate is either \[ O(n^k) \] for some \[ k \in \mathbb {N} \], either \[ 2^{\Theta(n)} \]. We research classes of exponential growth rates that appear after splitting the class with asymptotic bound in the exponent to classes with outward asymptotic bounds. We show that there exists a pair \[(A, M)\] with the growth rate \[ d_{(A,M)}(n) \in \Theta (n^k \cdot c^n)\] for arbitrary predefined natural numbers \[k\] and \[c\]. In addition, if \[c > k + 1\] then there exists a pair \[(A, M)\] with the growth rate \[d_{(A,M)}(n) \in \Theta (\log n \cdot n^k \cdot c^n)\].
Keywords: growth rate, generating sets, finite sets, EGP.
In this paper, we examined the computational complexity (minimum possible number of operations) of systems of monomials by circuits using two-input composition operation, which can be considered as a generalization of multiplication operation. We found that growth asymptotic of the Shannon function, characterizing the maximum complexity among systems of \[p\] monomials of \[q\] variables with exponents no more than \[K\], given that \[pq \log K \rightarrow \infty\] and some additional restrictions, has the form \[ \min(p,q) \log_2 K + \frac{pq}{\log_2(pq)}\].
Keywords: set of monomials, computation complexity, circuit complexity, composition circuit, Shannon function.
The work schematically proves an intuitive fact on the correspondence of the polynomial complexity of the SFE in the basis of the Schaeffer prime polynomial number of steps of the Turing machine. Numerical estimates are given.
Keywords: circuit complexity, Schaeffer’s stroke, Turing machine.
This work concerns property of being finitely generated by operations of \[A\]-closing of found earlier maximum subclasses in the class of linear automata over the ring of dyadic rationals. We present the proof of the fact that two of them are not finitely generated, while others are finitely generated.
Keywords: finite state automata, linear automata, dyadic rationals, \[A\]-completeness, maximum subclasses, finitely generated.
2021, volume 25, issue 2 (PDF)
The paper considers the problem of moving a three-link chain with one fixed edge from the initial position to the position in which the second edge is placed in a given point. The initial position is the position at which all chain links lie on the abscissa axis. Moreover, each chain link has a fixed length, but it can bend at an angle of 90 degrees at any point. The paper proposes an algorithm that minimizes the distance between the initial and final positions of the chain, and the distance measure is based on the metric of taxicab geometry.
Keywords: Manhattan chains, Manhattan distance, algorithm, taxicab geometry.
The adverse events in the medical care providing process occurs in 10-15% of hospitalized patients. Even a few percent reducing of such events will save thousands of lives. One of the ways to solve this crucial problem is the usage of intelligent information technologies that allow the predicting of an unfavorable clinical outcome risk in patients. The paper presents the study results carried out jointly by the scientist of the National Research Center for Therapy and Preventive Medicine of the Ministry of Health of the Russian Federation and the the scientist of Faculty of Mechanics and Mathematics of the Lomonosov Moscow State University, showing the applicability of data analysis methods in this important problem solving.
Keywords: preventive medicine, adverse clinical outcome, in-depth data analysis.
An absolute L-realizability of predicate formulas is introduced for all countable extensions L of the language of arithmetic. It is proved that the basic logic is sound with this semantics.
Keywords: constructive semantics, realizability, absolute realizability, formal arithmetic, basic logic.
Multifunctions are functions that are defined on a finite set and return subsets of the considered set as their values. This paper deals with the closure of multifunctions that can be obtained using the operations of adding dummy variables, composition operator, and operator with the equality predicate branching. We obtain nine precomplete closed classes of multifunctions of rank two and prove the completeness criterion. A classification of multifunctions based on belonging to precomplete classes is presented, and all types of bases are described.
Keywords: closure, equality predicate, multioperation, closed set, composition.
The Fermat—Steiner problem is to find a point in the metric space Y (which we will call the Steiner astrovertex) such that the sum of the distances from it to the points of some finite fixed subset \[ A \subset Y \], called the boundary, is minimal. We will call the minimal sum of distances the length of the minimal astronet. We consider this problem in the hyperspace \[ Y = H(X) \] of nonempty, closed, and bounded subsets of the proper space X, which are compact in this space. This article describes a wide class of deformations of boundary compact sets that do not increase the length of the minimal astronet. Averaging in the sense of the Minkowski sum of a finite number of boundaries consisting of an equal number of elements is also considered, and it is shown that such averaging also does not increase the length of the minimal astronet.
Keywords: Fermat—Steiner problem, Steiner minimal tree, minimal parametric network, minimal astronet, Steiner astrocompact, hyperspace, Hausdorff distance.
In this paper, we investigate the use of automata with erasable colors to determine the properties of connected planar undirected simple graphs. The following facts are proved: two erasable colors are enough for automata to determine whether the graph is a tree or a pseudo-tree.
Keywords: Automata, graphs, trees, pseudotrees.
The paper presents a formula for the Shannon function for schemes in the basis of the Schaeffer stroke.
Keywords: Schaeffer’s stroke, schema of functional elements, Shannon function.
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 \left(\frac{2^n}{n}, \frac{2^n (1 - \lambda)}{\log k} \right)\] 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.
Keywords: multilayer circuits, multidimensional circuits, Shannon function asymptotics, circuit complexity, graph separators.
All precomplete classes are found for classes of linear automata over simple finite fields with superposition operations.
Keywords: finite automaton, linear automaton, operation of superposition, completeness, closed class, maximum subclass, finite field.
2021 year, volume 25, issue 1 (PDF)
The article is a continuation of the article [1]. An algorithm for verifying formalized mathematical proofs for first-order predicate logic with equality is considered. Theorems about its correctness and completeness are proved.
Keywords: automated theorem proving, system for automated deduction, first order language, predicate calculus, production system, artificial intelligence.
The thesis about the necessary and sufficient requirement for the presence of artificial intelligence in smart systems for various purposes is formulated and substantiated. Necessity is the presence of redundant readings of the first signaling system or the primary sensorium of smart systems. Sufficiency is the presence of a second signaling system or language of communication of smart systems as a linguistic superstructure, a linguistic sensorium of the conscious part of the primary sensorium. The problems of creation and safe operation of smart systems are discussed. The article was written for the purpose of active participation in the current discussion of highly respected specialists of the M.V. Lomonosov on the topic “Artificial Intelligence: Problems and Prospects” [1].
Keywords: artificial intelligence, smart system, radical, language, internet of things, interface, natural intelligence, information and system security of intelligence.
The paper considers the problem of the equilibrium mutual arrangement of two triangles and proposes a solution to this problem based on the method of Lagrange multipliers. Two-time iteration of this method gives analytical solution.
Keywords: Lagrange method, transformation on a plane, similarity, rotation, shift, triangle.
This article is devoted to the construction of an algorithm for reducing the problem of predicting sports results to the problem of binary classification. At the same time, the optimality of this algorithm has been substantiated from the point of view of the application of forecasting results in the game against bookmakers.
Keywords: machine learning, predicting sports results, binary classification.
The work is focused on development of the distributed algorithm for search of companion-trajectories. We call two trajectories as companion-trajectories if they both contain section of required duration on which at any time moment distance between two objects is no larger than specified threshold. It’s assumed that search is performed on database that is so big that it cannot be stored and processed on a single work station. Such tasks are usually called big-data tasks. We define trajectory quantization procedure, introduce cell index data structure, define similar trajectories. Then we build effective algorithm for search of similar trajectories. Based on this algorithm we develop effective local and distributed algorithms for search of companion trajectories. Asymptotic complexity of these algorithms is estimated.
Keywords: big-data, geo-spatial data analysis, trajectory analysis, companion-trajectory search, similar trajectory search, traffic analysis.
The locally recoverable codes (LRC codes) are linear codes with an important for applications property that every symbol of a codeword can be recovered from a small set of other symbols. Codeword symbols can be interpreted as servers with information. It is natural to define a topology of these servers as a graph so that every server can be recovered using neighborhood servers in this graph. The paper provides LRC code constructions for some topologies and bounds on the rate of such codes.
Keywords: erasure coding, locally recoverable codes, codes on graphs.
In this paper we consider \[ \Lambda \]-expressions constructed from universal functions for functional classes of the Grzegorczyk hierarchy. We will find a sufficient condition such that a given \[ \Lambda \]-expression determines a primitive recursive function from some level of the Grzegorczyk hierarchy.
Keywords: Grzegorczyk hierarchy, primitive recursive functions, strictly primitive recursive realizability.
The paper considers the implementation of one class of laws of motion by a cellular automaton on an infinite screen. It is shown that the minimum number of states of a cellular automaton simulating the bidirectional movement of a point on a ray at which the point does not make 2 movements to the right in a row is 5.
Keywords: cellular automaton, number of states, infinite screen, bidirectional motion, image construction.
This work concerns questions of A-completeness of finite systems of linear automata over the ring of dyadic rationals. Condition of completeness of linear automata system, which includes automaton that models addition in the first step is described. For the formulated set of maximum subclasses in the class of linear automata over the ring of dyadic rationals decidability of a problem of finite set inclusion into these classes is proven.
Keywords: finite state automata, linear automata, dyadic rationals, A-completeness, maximum subclasses, decidability.