Русский язык
2018 year, volume 22, issue 4 (PDF)
The paper sets out a system of requirements and principles that determine the methodological aspects of creating domestic hardware-software platforms for automated systems in the protected execution as the basis of the critical information infrastructure of the Russian Federation, describes the experience of creating a protected hardware-software platform "Sintez-HSP"that fully satisfies the most strict requirements for information security, reliability, scalability, ensuring the independence of critical information infra the structure of foreign technologies and software.
Keywords: automated systems in the protected execution, hardware-software platform, information security, critical information infrastructure, Sintez-HSP
The methods of external penalty functions, internal penalty functions and quasi-barrier functions for solving problems of mathematical programming are considered. New quasi-barrier functions are proposed. The theorems of convergence of the indicated methods to the solution of mathematical programming problems are proved. The properties of these functions are considered for their transformations: differentiation, integration, construction of functions inverse to them.
Keywords: external penalty functions, internal penalty functions, barrier penalty functions, inverse functions, quasi-barrier functions, mathematical programming problem, differential barriers, power differential barriers, entropy differential barriers, convergence of differential barriers methods to solving mathematical programming problems.
The problem of the recovering of an erased fragment of a musical composition based on the Viterbi algorithm, namely, the method based only on the Viterbi algorithm, the method using the Viterbi algorithm and also shifted height and shifted duration, the method based on the Viterbi algorithm and the principles of musical harmony are obtained. The method with the best result was found (Viterbi algorithm combined with the method of musical harmony), the method for estimating of the similarity of fragments was introduced, examples of melodies, the tacts of which were best recovered, are given. All methods are written into the program in the Java language, which solves the given task, in addition, the program GuitarPro is used, which helps to translate all the necessary information about the melody into a text format.
Keywords: the Viterbi algorithm, shifted height, shifted duration, chord harmonization.
In this paper we consider the problem of fuzzy user concepts personalization using the action of modifiers on certain fuzzy sets. The existing algorithm of personalization was investigated and modified; for its new version the number of iterations performed was estimated.
Keywords: fuzzy sets, personalization.
Authentication protocols are distributed algorithms designed to provide authentication of agents and the transfer of confidential information (cryptographic keys, etc.) in an insecure environment. They are used, for example, in electronic payments, electronic voting procedures, database access systems, etc. On the reason of the large financial and social damage in the case of the incorrect execution of such protocols, it is necessary to use mathematical methods to justify their correctness and security. In the present work, a new mathematical model of such authentication protocols is introduced, which provides a possibility to describe both the protocols and their properties. It is shown a possibility to solve problems of verification of authentication protocols.
Keywords: authentication protocols, distributed algorithms, verification.
A computationally efficient method for generation the ensemble of discrete orthogonal polynomials of complex variable is motivated and proposed. The ensemble keeps orthogonality at a given arbitrary separate node set with unitary weight function. The detailed algorithm implementation for coefficient computation and polynomial sampling is presented in GNU Octave/Mathworks Matlab language. The complexity estimate is the least attainable.
Keywords: digital signal processing, robust interpolation, orthogonal polynomials of discrete complex variable, arbitrary nodes, coefficient computation, optimal algorithm, computational complexity.
The complexity of learning functions with respect to the number of monotone conjunctions in their representation is studied in the paper “Learning of arithmetic sum of monotone conjunctions” by Z. A. Niyazova. In particular, lower and upper bounds on the number of queries one needs to learn the function, having no more than 2 conjunctions, are presented there. Here, we show that this result can be improved upon by one query.
Keywords: exact learning, sum of monotone conjunctions, membership queries.
It is proved that every absolute arithmetically realizable predicate formula is classically true, but there is a classically true predicate formula that is not absolute arithmetically realizable.
Keywords: constructive semantics, realizability, arithmetic realizability, absolute realizability, formal arithmetic.
The sets of all precomplete classes in the classes of linear automata over finite fields are found, which are reduced criteria systems in these classes.
Keywords: finite automaton, linear automaton, composition operations, superposition operations, feedback, completeness problem, precomplete class, criterial system, reduced criterial system, adder, delay.
The report outlines the work to create a discrete-control system learning algorithm for acting and achieving goals. Learning is based on trials and misses. The entire experience of the system is stored in the Database. The algorithm is optimized by two criteria: the accuracy of achieving the goals and the maximum reduction in training time. The reduction in training time is implemented mainly by reducing the number of trials using prediction methods and interpolation by experimental data.
Keywords: positioning, learning algorithm, robot, interpolation, approximation.
The article is devoted to the drop and paste operations, which have been promoted by V.I. Levenshtein. Closure operators are introduced for these operations. For the paste operator the existence, finiteness and uniqueness of the basis in closed classes are proved, and for the drop operator, non-existence for the infinite class and existence, finiteness and uniqueness for the finite are proved. The automata complexity of closed classes is investigated. The problems of completeness,precompleteness,expressibility are solved.
Keywords: drop and paste operations; closed class; regular language; basis; automata complexity; problems of completeness,precompleteness,expressibility.
2018 year, volume 22, issue 3 (PDF)
In the framework of the Ilyushin’s theory of elastoplastic processes, in [3] for mathematical modeling of complex loading processes we use special type quasilinear equation with three state functionals. The functionals was calibrated using the experimental results [4] (R.A.Vasin, etc.) for 3D- helical trajectories of deformations. It turned out that the response on a helical trajectory of deformation takes a completely definite loading form, not exactly, but after the exhaustion of some trace of retard. On the helical trajectories of deformations the form of loading is the same: helical trajectory of deformations is becoming to helical trajectory of loading there and back. The used map preserves the geometry of space. This correspondence by Ilyushin is called as isomorphism theorem. All new theories use as the basis the directing vector of stresses and vectors constructed on the base of Frenet basis. For high-dimensional processes, the number of state functionals increases, so and the methods of their identification become more complicated. All models are completly verified. The results are given below.
Keywords: plasticity, plastic deformations, complex loading, state functional, identification of functionals, isomorphism theorem.
This paper is devoted to estimation of SSD write amplification dependency on R — overprovision and N — number of sectors in a block. Garbage collector uses greedy algorithm. More precise formula than in[1] is obtained because it does not depend on N → ∞ assumption. Proved that for fixed overprovisioning the write amplification is monotonic increasing function of N .
Keywords: Write amplivication, overprovision, SSD, garbage collector.
An absolute L-realizability of predicate formulas is introduced for all countable extensions L of the language of arithmetic. It is proved that the intuitionistic logic is not sound with this semantics.
Keywords: constructive semantics, realizability, absolute realizability, formal arithmetic, intuitionistic logic.
The paper considers the task of designing a program which would perform semantic analysis of a juridical document in Russian language. For each entity described in a text, the program must construct a scheme which computes the value of this entity. The paper contains rules which allow to construct such schemes if morphological information about all words of the text is provided.
Keywords: semantic analysis, syntactic analysis, juridical document, logical formula, rule.
CUDA libraries supporting multiple-precision integer arithmetic are considered. Features and performance of such open-source libraries are compared.
Keywords: multiple-precision arithmetic, GPU, CUDA.
The thickness of a graph G is the minimum number of planar graphs whose union is G. In this paper, we consider an upper bound for the chromatic number of graphs depending on thickness k and girth g, where k ≥ 1 and g ≥ 3. In particular, for biplanar graphs with girth at least 10 we obtain 5-colorability.
Keywords: chromatic number, girth, thickness, planar graph, biplanar graph.
A model of motion of a dot on the screen is considered. The screen is a semi-infinite one-dimensional cellular automaton. A particular subset of states of the screen is called the image of the dot. A rule of motion is defined by an infinite sequence of zeros and ones, corresponding respectively to the "stop"and "go"commands. For a broad class of motion rules, an algorithm for implementing the given rule is described. A Bernoulli probability measure of realizable motion rules is explored. It is shown that almost all motion rules are realizable. Also it is shown that the set of realizable motion rules is meager with respect to the product topology.
Keywords: cellular automaton, universal screen, motion of the dot, rule of motion, Bernoulli measure, product topology, Baire category.
Let L be an extension of the language of arithmetic, V a class of number-theoretical functions. A notion of the V-realizability for Lformulas is defined in such a way that indexes of functions in V are used for interpreting the implication and the universal quantifier. It is proved that the semantics for L based on the V-realizability coincides with the classical semantics iff V contains all L-definable functions.
Keywords: constructive semantics, realizability, generalized realizability, formal arithmetic.
The following assertions are proved: for each natural k and each Boolean constant p, there exists a basis consisting of a Boolean function on max(k + 1; 3) variables and negation of one variable (there exists a basis consisting of a Boolean function on not more than 2,5k + 2 variables and negation of this function), in which one can implement any Boolean function except a Boolean constant p by a logic network which is irredundant and allows a fault detection test (a diagnostic test, respectively) with a length not exceeding 2 under not more than k stuck-at-p faults at inputs and outputs of gates. It is shown that, when considering only stuck-at-p faults at inputs of gates, one can reduce the mentioned bounds on lengths of tests to 1.
Keywords: logic network, one-type stuck-at fault, fault detection test, diagnostic test.
2018 year, volume 22 issue 2 (PDF)
The paper considers the possibilities of applying the technology of assessment and monitoring of complex processes of ensuring information security in the task of sustainable development of the critical infrastructure of the Russian Federation. The structure of the critical infrastructure stability model, the possible scenarios for the system of information security assessment and monitoring, the analytical capabilities of the system are discussed.
Keywords: information security, critical infrastructure, technology for assessment and monitoring of complex processes, sustainable development.
In the framework of the Ilyushin’s theory of elastoplastic processes, in [3] for mathematical modeling of complex loading processes we use special type quasilinear equation with three state functionals. The functionals was calibrated using the experimental results [4] (R.A.Vasin, etc.) for 3D- helical trajectories of deformations. It turned out that the response on a helical trajectory of deformation takes a completely definite loading form, not exactly, but after the exhaustion of some trace of retard. On the helical trajectories of deformations the form of loading is the same: helical trajectory of deformations is becoming to helical trajectory of loading there and back. The used map preserves the geometry of space. This correspondence by Ilyushin is called as isomorphism theorem. All new theories use as the basis the directing vector of stresses and vectors constructed on the base of Frenet basis. For high-dimensional processes, the number of state functionals increases, so and the methods of their identification become more complicated. All models are completly verified. The results are given below.
Keywords: plasticity, plastic deformations, complex loading, state functional, identification of functionals, isomorphism theorem
The article is devoted to the drop and paste operations, which have been promoted by V.I. Levenshtein. The following two questions are asked and answered. What is the class of regular languages that are stable to the drop/paste operations? Are there any irregular languages that are stable to these operations?
Keywords: drop and paste operations, closed class, regular language.
The paper I.B. Kazakov, “Encoding in a covert channel of packet permutations” introduced a number of error models for codes over sets of permutations. Such error models induce graph structure on sets of permutations. Our research is focused on properties of these graphs. We show that the graphs consist of layers of independent sets; the layer that contains the given permutation is determined by the number of edges in the characteristic graph of the permutation. We estimate vertex degrees in the layers of the graph \[(S_n)^2\] and use this estimate to bound the cardinality of an error-correcting kayer-based code. After that we develop a number of aids that allow to obtain upper bounds of code cardinality. We introduce the notions of symmetric layers and graph partitions and decompose \[S_n\] for some values of n into prisms and into graph products, i.e. generalised prisms. We also embed the graph \[S_n\] into \[E_{\frac{n(n−1)}{2}}\]. Finally establish a connection between sizes of subgroups H ⊂ \[S_n\] and presence of n-step permutations in these subgroups.
Keywords: permutations, graph structure, error-correcting code.
This paper describes the lattice of all clones on the three-element set that contain all constant functions 0, 1, 2 and functions min, max. The clones are characterized as sets of predicates being preserved by them.
Keywords: clone theory, lattice of clones, three-valued logic.
A hyperautomatа is a finite automatа whose states are the sets of states of some finite automata. A hyperautomatа is called a group hyperautomatа if the semigroup of the automatа on which it is based is a finite group. In this paper, we study the question of the maximum number of regular languages that can be recognized by group hyperautomata.
Keywords: finite automata, hyperautomata, regular languages, finite groups.
The paper presents description the main problems of the development of systems evaluation and monitoring of processes in socio-technical systems. The tasks and technologies associated with them are considered, too. Solutions of the problems are discussed. The perspective directions of personalization of human interaction with the digital world and augmented intelligence are considered in the paper. The article is prepared based on the results of the author’s speech at the cathedral seminar of the Department of Mathematical Theory of Intelligence Systems of the Faculty of Mechanics and Mathematics of the Lomonosov Moscow State University «Theory of Automata» under the supervision of Professor V B. Kudryavtsev on March 21, 2018.
Keywords: Socio-technical systems, evaluation and monitoring of complex processes, fuzzy sets, personalization.
Flash memory in the last decade became dominant technology for storing data both for personal electronic devices and enterprise products: servers, network storages and data centers. Initially flash memory technology assumed storing only one data bit in flash cell (SLC-memory). Further development of production technology of flash memory and inegration of more powerfull error correction codes in flash memory modules made it possible to store 2 bits (MLC-memory) and even 3-bits (TLC-memory) of data. Increase of number of bits stored in each cell leads to significant increase of probability of error during read operation. Furthermore whith increase of programm-erase cycles electric charges stored in flash memory cells have tendency to decrease. This process also leads to increase of probability of error during read operation. Finally this process of charge decrease leads to flash memory failure when error correction code cannot fix all read errors. Rank method of storing data in flash cells is resilient to process of graduate decrease of cell charges. Moreover this method theoretiacally has higher area efficiency in comparison with conventional SLC/MLC/TLC memory. First in this paper brief description of conventional flash memory is given. Read operation is analyzed, basic model of read errors is described. Then rank method of storing data is presented. Estimated amount of memory stored by this method in comparison with conventional flash memory. Introduced Kendall-Tau distance between permutations. By means of this distance estimated area of rank memory taking in account technological limitations. Finally it’s analyzed area efficiency of rank flash memory in comparison with conventional flash memory. Explicitly described cases when rank memory has higher area efficiency than conventional SLC/MLC/TLC memory.
Keywords: rank flash memory, SLC/MLC/TLC flash memory, flash memory area efficiency.
Classes of linear automata over finite fields with composition operations (superposition and feedback) are considered. Previously an algorithm for checking the completeness of finite subsets was obtained for these classes. In the case of a simple field, all precomplete classes whose set is a countable reduced criterial system are found. Previously in the general case the set of closed classes was constructed, which is a criterial system, including the family of classes generated by maximal subfields in the transcendental extension of the finite field under consideration. For simple fields, all classes of this family were absorbed by other classes from the reduced criterial system. Therefore, in the present paper the family is being investigated in the case of finite fields that are not simple. It turned out that part of the elements of the family is also absorbed in this case, but also among its elements there are precomplete classes that are finitely generated and not contained among the precomplete classes of other families.
Keywords: linear automaton, adder, delay, feedback, composition operations, completeness check algorithm, precomplete class.
2018 year, volume 22, issue 1 (PDF)
The paper deals with a class of neural piecewise-parallel functions with binary-rational coefficients. It is proved that for any function in the class of piecewise-parallel functions there exists a function in the class of piecewise-parallel functions with binary-rational coefficients that approximates it with a predetermined accuracy. Also, for the class of functions under consideration, it is shown that there exist bases consisting of arbitrary number of elements, in particular, a Scheffer function is found.
Keywords: class of piecewise-parallel functions, class of neural functions with binary-rational coefficients, superposition operations, Scheffer function, bases.
We analyze all Latin squares of order 4 generated by proper families of Boolean functions. It turns out that all these Latin squares define polynomially incomplete quasigroups. We propose a generalization of the construction based on proper families. As a result, the number of generated Latin squares grows four times, and an essential number of the corresponding quasigroups becomes polynomially complete.
Keywords: Quasigroup, Latin square, parametric assignment, polynomial completeness, proper families of functions
Realtime pushdown transducer saves the set of periodic sequences. Earlier the author found upper and lower bounds for max period of output for transducer without input as a function from parameters of transducer. There are upper and lower bounds for max period of output in general case in current paper. The max period of transducer output has been studied as function from period of input sequence.
Keywords: realtime pushdown transducer, deterministic function, periodic sequences.
In this paper we consider the relationship between the area and the maximum potential of plain circuits realizing Boolean operators. The maximal potential is a complexity measure of plain circuits, reflecting the power consumption of the circuit in the worst case, it is also often called activity. It is equal to the maximum number of outputs of circuit elements equal to 1, where the maximum is taken over all input sets of the circuit. It was porved that for arbitrary Boolean operator f, its maximal potential \[\hat{U}\] is greater or equal than \[\sqrt{S} /4 \sqrt{2} \] where S is the area of the minimal plain circuit realizing f .
Keywords: plain circuits, activity, potential, retations between complexity measures, lower bounds, Boolean operators.
The question how difficult it is to prove given theorems in given formal systems arises in many areas. In computational complexity, lower bounds to the size of proofs offer an approach towards the separation of complexity classes. Analysis of proof systems underlying recent SAT solvers provides the main theoretical framework towards understanding the power and limitations of solving. The main part of research in proof complexity has concentrated on proof systems for classical propositional logic. Despite the fact that propositional proof complexity has made enormous progress over the past three decades in showing tight lower and upper bounds for many proof systems, some of strong classical proof systems have resisted all attempts for lower bounds for decades. Nevertheless, a general and long-standing belief in the proof complexity community asserts that there is a close connection between progress in lower bounds for Boolean circuits and progress in proof size lower bounds for strong propositional proof systems. In the paper we show how relates Boolean circuits and proof systems with respect to complexity, i.e. how ideas and techniques from Boolean circuit complexity applies to propositional proof complexity.
Keywords: Propositional proof systems, proof complexity, Boolean circuits, circuit complexity, complexity classes.
Traditionally, it is believed that the lattices of clones in two-valued logic and k-valued logic are totally different. In the paper we show that despite the differences they have a lot in common, and many properties that follow from the Post lattice can be generalized to the multi- valued case. As an example we show that the most general polynomial algorithm for the constraint satisfaction problem on k-element set can be viewed as a combination of methods known for two-valued case.
Keywords: Boolean functions, k-valued functions, relations, Galois connection, constraint satisfaction problem.
Distinguishing sequences for finite automata were first introduced in the classical paper of E. Moore and since that they have many applications in testing of sequential circuits and communication protocols. One of the basic tasks in the testing of finite automata is to identify the initial state of the automaton under investigation. Suppose we have a full description of a finite deterministic Mealy automaton and we know that its initial state is in some subset of its set of states. Then the state-identification problem is to find the initial state by a sequential application of input symbols to the automaton. In this talk we discuss the bounds on the length of such input sequences and show a relation of this problem to combinatorial problems in hypergraph theory.
Keywords: Finite automaton, adaptive distinguishing sequence, Moore theorem, hypergraph.