2019 year, volume 23, issue 4 (PDF)

Sukhareva A.V., Vorontsov K.V. Building a complete set of topics of probabilistic topic models

Interpretability, linear increase in complexity with data growth, scalability made topic modeling one of the most popular tools for statistical text analysis. However, there are a number of disadvantages caused by the dependence of the solution on the initialization. It is known that the building of a topic model is reduced to solving an ill- posed problem of the non-negative matrix factorization. The set of its solutions in the general case is infinite. Every time the model finds a local extremum. Repeated training of the model for the same collection can lead to detection of more and more new topics. In practice, it is often necessary to define all the topics of the corpus. To solve this problem, the article proposed and investigated a new algorithm for finding the complete set of topics based on the construction of a convex hull. It was shown experimentally that it is possible to construct a basis for the finite number of models. The likelihood of the basis is higher than for a single model with a similar number of topics. Compare of the basis of LDA models (latent Dirichlet allocation) and ARTM models (additive regularization for topic modeling) suggests that the topics of the sets coincide with high accuracy.

Keywords: probabilistic topic modeling, stability of topic models, complete set of topics of topic models, latent Dirichlet allocation, LDA, regularization, ARTM, BigARTM.

Bernadotte A., Galatenko A. Structural automaton design for solving the problem of exponential blowup for one class of regular languages

It is well known that recognition of a language specified by a regular expression of the form \[\cup_{i=1}^n . * \alpha_i . * \beta_i . * \], where \[\alpha_i\], \[\beta_i\] are words over some alphabet, in the general case requires a deterministic automaton with the number of states which is exponential in n. We propose a design of a structural automaton of a polynomial spatial complexity that recognizes languages from a given class.

Keywords: DFA, structural automaton, regular language, exponential blowup.

Okhotnikov O.A. About proof-search in classical natural deduction calculus using partial skolemization

Automated proof search in single-conclusion sequential variant of classical predicate calculus is considered. In this algorithm, metavariables and partial skolemization are used. Theorems of soundness and completeness for the considered algorithm are proved.

Keywords: automated theorem proving, mechanical proof search, first order language, predicate calculus, sequent calculus, production system, artificial intelligence.

Aleksiadis N.Ph. On a functional system of polynomials with rational coefficients

This article investigates the completeness problem for polynomial functions with rational coefficients, as well as problems of a functional nature generated by its solution, namely: studying the structure of closed and precomplete classes, the problem of bases of complete systems. In particular, it was proved that 1) the system of functions is complete if and only if it is not wholly contained in any precomplete class; 2) the cardinality of the set of all precomplete classes is equal to the continuum; 3) there is a complete system that does not have a basis.

Keywords: polynomial, functional system, problem completeness, rational function, closed classes.

Bistrigova A.V. Using comparation queries in attribute-efficient learning of Boolean functions

We consider the problem of exact attribute-efficient learning functions of Post’s closed classes with the help of comparation queries. Here, we show that the complexity of learning by comparation queries is not worse than by membership queries. Particularly, for some classes, if we use comparation queries, we get better value of complexity function.

Keywords: exact learning, attribute-efficient learning, membership queries, comparation queries, Post’s closed classes.

Ronzhin D.V. A-completeness of systems with additives of linear automata over the ring of dyadic rationals

A brief description of results of A-completeness problem for linear finite state automata, functioning over the ring of dyadic rationals is given. Conditions of A-completeness for systems, containing all one- valued linear automata with finite additive and finite systems with a summing automaton are stated.

Keywords: finite state automata, linear automata, dyadic rationals, A-completeness, maximum subclasses.

Reports of the seminar "Theory of Automata"

Reports of the seminar "Questions of complexity of search algorithms"

2019 year, volume 23, issue 3 (PDF)

Menkin M. Auto-translation of rules of the road to formal graph-theoretic model

The present article deals with semantic analysis of legal documents. In this paper, we introduce one possible approach to formal modeling of rules of the road. We describe the basic procedures for semantic analysis of one type of sentences.

Keywords: semantic analysis of legal documents, pragmatic analysis, modeling of text semantic.

Bokov G.V. Graph based extended resolution for Boolean formulas

In this article we consider a graph based extended resolution for representing refutations of Boolean formulas in conjunction normal form. We prove that a Boolean formula is unsatisfiable iff there is its graph based refutation.

Keywords: Resolution, graph based refutation, unsatisfiability, Boolean formulas.

Eremenko A.R., Yashunsky A.D. On the weight of functions, defined by read-once AND/OR formulas

We consider the set of functions defined by read-once formulas with binary conjunction (logical AND) and disjunction (logical OR) operations. For the functions defined by formulas with a fixed number of operations we investigate the weights of functions, i.e. the number of tuples on which the function has value 1. We establish asymptotic bounds on the number of read-once formulas that define functions with specific weights, in particular on the number of formulas, that define functions with no more than a quarter of ones among their values.

Keywords: Boolean function, read-once formula, function weight, asymptotic bound.

V.N. Kozlov Codes that define images accurate to affine transformations

The paper presents codes that define images with an accuracy of affine transformations, including some new code.

Keywords: pattern recognition, images, image codes.

Sitdikov T. R. The complexity of multidimensional rectangular circuits design

A model of rectangular multidimensional circuits is considered in this paper. Logic gates are placed in cells of d-dimensional mesh. Each pair of adjacent cells is connected by a bus with at most k wires. We establish Shannon function upper bound \[ \frac{2^n}{\min(n,d \log{k})} \] for the complexity of this type of circuits.

Keywords: multidimensional circuits, multilayer circuits, Shannon function asymptotics, circuit complexity.

Chasovskikh A.A. On the number of maximum overclasses in the linear automata class

Updated maximale subclasses lists in linear automata classes over finite fields. A criterion is found for the finiteness of the number of precomplete overclasses for a given set of linear automata.

Keywords: finite automaton, linear automaton, operation of composition, feedback, completeness, closed class, maximum subclass, finite field.

Babin D.N. Automata with linear transition functions

The problem of completeness of the system of automaton functions with linear transitions with respect to the operation of superposition is considered. This system is not complete; moreover, any system of automata that complements it to the basis is infinite.

Keywords: finite automaton, completeness, superposition, closed class.

Popkov K.A. Short single fault detection tests for contact circuits under breaks and closures of contacts

We consider a problem of implementation of Boolean functions by irredundant two-pole contact circuits which allow short single fault detection tests regarding breaks and closures of contacts. We describe all functions which the minimal length of such a test equals 0, 1, 2, and 3 for. We prove that, for almost all Boolean functions on n variables, this length equals 4.

Keywords: contact circuit, Boolean function, contact break, contact closure, fault detection test.

Konovalov A.Yu. The intuitionistic set theory is not sound with respect to the constructive sematics based on hyperarithmetic sorts.

The soundness of axioms of the intuitionistic set theory with respect to the realizability semantics based on hyperarithmetical sorts is studied.

Keywords: constructive semantics, realizability, axiomatic set theory, hyperarithmetical sorts.

Chasovskikh A.A. On classes of transfer functions of linear automata

For classes of transfer functions of linear automata over a finite field with operations induced by composition operations on these automata, all maximal subclasses are found.

Keywords: finite automaton, linear automaton, transfer function, operation of composition, feedback, completeness, closed class, maximum subclass, finite field.

Reports of the seminar "Theory of Automata"

2019 year, volume 23, issue 2 (PDF)

Botkholov A.J. Recovery of two notes sounding simultaneously

In this work recovery of two notes sounding simultaneously in terms of amplitudes and frequencies is considered. The methods of recovery of amplitudes of two notes which were played at the same time by two different musical instruments are given. Cases of existence and not existence of two solutions for a problem of recovery of notes are described.

Keywords: basic tone, overtone, amplitude, frequency, bending around note, total spectrogram.

Kushnareva L., Kuzminykh D. Persistent homology of Markov chains and its application to natural language processing

In this work we introduce new persistent topological invariants for Markov chains. We also demonstrate the way of using these invariants for natural language processing task.

Keywords: Topology data analysis, persistent homology, Markov chains, natural language processing.

Kazakov I.B. Reliabilty criterion for channels with prohibitions

We investigate the possibility of reliable transmission in a situation when an adversary can prohibit some characters, and a set of prohibitions can change at every clock cycle. We show that reliable transmission is possible if and only if the cardinality of the alphabet n and the number of allowed characters k satisfy the inequality n ≤ 2k−2.

Keywords: covert channels, walks in a plane, character prohibition, transmittable language.

V.N. Kozlov Image segmentation and shape-preserving transformations

The image in the paper is a finite (non-empty) set of points in Euclidean spaces of different dimensions. Briefly, the work consists in having an image belonging to a certain image to extract from this image what could be called a description of this image.

Keywords:mathematical definition of the image, image recognition.

Piven N.A. Some properties of permutation construction for parametric assignment of quasigroups

We analyse so–called permutation construction, introduced before. It turns out, that it’s redundant, so we propose an improvement, which makes it injective for linear functions and possibly injective without conditions.

Keywords: Quasigroup, Latin square, parametric assignment, proper families of functions.

Sobyanin P.I. About algorithm which checks if subquasigroup exists in a given quasigroup

Algorithm which checks if subquasigroup exists in a given quasigroup. Performance of its consequent and CUDA parallel versions are compared.

Keywords: quasigroup, subquasigroup, GPU, CUDA.

Vedernikov I.K. Criterion for almost complete prediction of a superword in a multi-valued alphabet

The machine predicts the next character of the input sequence if it outputs that character the moment before. The present paper considers whether an arbitrary superword in multivalued alphabet can be almost completely predicted or not. The paper provides a theorem that enables to restrict the class of machines, with the help of which superwords are predicted. Moreover, the paper presents the criterion for almost complete predicting.

Keywords: almost complete predicting, predicting machine, prediction of superwords by a machine, criterion for predicting.

Efimov A.A. The upper estimate of the volumetric power consumption of the circuits that implement boolean operators.

In this work volume schemes which are generalization of plane schemes in space are considered. The class of the schemes implementing boolean operators was considered. For this class upper assessment of potential — a measure of the power equal to quantity of the circuit elements giving unit on this input pattern is received. It is shown that any operator of n variables can be realized with a volume scheme whose potential does not exceed \[O(m \cdot 2^{n/3})\] if m ≤ n and \[O(\frac{m}{n} \cdot \sqrt[3]{n} \cdot 2^{n/3})\] if m > n.

Keywords: schemes from functional elements, volume schemes, scheme power, potential.

Kan A. N. Questions of expressibility in the class of matched functions

In this paper we consider the 2-completeness in the class of matched functions P. This class was considered earlier in [3, 4]. It is precomplete in the class PL of piecewise-linear functions. There are two precomplete classes: the class of continuous fucnton, the class of matched finite function.

Keywords: Class of piecewise-linear functions, the class of piecewise-linear continuous functions, the class of matched functions, class of finite functions, the class of mathced finite function, 2-precompleteness, the Heaviside function.

Kapustin I.S. On the elementary expressibility in predicate logic

New mathematics concepts are often introduced with some quantifier definitions. If we have a sufficiently large stock of such notions, it can allow to reformulate the new quantifier definitions in a quantifier-free form. This makes the problem of finding basic concepts, which make further quantifiable definition redundant, worth considering. Creating computer programs that automatically introduce such bases is also worth considering. In this paper we observe 3 simple cases of reducing the quantifier expressions to the quantifier-free ones. We investigate predicates and functions defined by ∈ predicate on the set \[\textit{Z} \cup\ 2^Z\], where Z is the set of integers. We consider predicates expressed by ∈ predicate on the set of points of the plane and the lines lying in it. Finally, predicates expressed on the set of natural numbers by the | predicate on it are also considered. Bases were found in all 3 cases.

Keywords: predicate logic, quantifier definitions

Konovalov A. Yu. The Zermelo–Fraenkel set theory is not sound with respect to the constructive sematics based on hyperarithmetic sorts

A semantics of the realizability based on hyperarithmetical sorts for formulas of the language of set theory is introduced. The soundness of axioms of the Zermelo–Fraenkel set theory with respect to this semantics is studied.

Keywords: constructive semantics, realizability, axiomatic set theory, hyperarithmetical sorts.

2019 year, volume 23, issue 1 (PDF)

Golikov K.A. Learning algorithm of systems with discrete control

The learning algorithm was developed for the problem of positioning systems with discrete control, it is based on a method of generalizing using a global interpolation and a gradient descent of trials and fails that stored in the database. The algorithm is optimized by the criterion of reducing the learning time (number of attempts). The algorithm was tested on a simulator for models of systems operating on a plate of two different types: for a mobile differential-drive robot and for an open kinematic chain with rotational and prismatic joints.

Keywords: positioning, learning algorithm, robot, interpolation, approximation.

Mikhail Menkin Objects model of rules of the road

The present article deals with semantic analysis of legal documents. By legal document semantics we mean the mapping from legal document text to formal model. In this article, we describe one possible approach to formal modeling of rules of the road.

Keywords: semantic analysis of legal documents, pragmatic analysis, formal modeling.

Bokov G. V. On the finite representation of logical systems

In this paper, we consider a problem of finite representation for logical systems. We research three types of logical systems: linear, monotone and implicational. For each type of logical systems we prove sufficient conditions of finite representation. Moreover, we prove a criterion for logical system of classical tautologies to be finitely generated.

Keywords: logical systems, propositional calculus, finite representation, inference rules.

Galatenko A.V., Pankratiev A.E., Rodin S.B. Polynomial completeness of finite quasigroups

We give a survey of results connected to deciding polynomial completeness of finite quasigroups. The paper is based on a report presented at the seminar “Automata theory”.

Keywords: quasigroup, Latin square, polynomial completeness, simplicity, affinity.

Dergach P.S., Danilevskaya E.D. On the progressive representation of periodic sets with restrictions on the beginning and the step

In the article the set \[K(n) := \mathbb{N} \backslash (n,n) \] is being examined, it’s presentation as union of as few arithmetic progressions as possible with constraints to the begining or step is being investigated. In both two cases appropriate accurate estimations have been found.

Keywords: arithmetic progression, natural series, minimization problem, types of constraints.

Konovalov A. Yu. Markov’s Principle is uniformly V-realizable in any V-enumerable domain.

Various variants of the notion of the V-realizability for predicate formulas are defined, where indexes of functions in the set V are used for interpreting the implication and the universal quantifier. It is proved that Markov’s Principle is weakly V-realizable, not uniformly V-realizable, and uniformly V-realizable in any V-enumerable domain \[M \subseteq N\].

Keywords: constructive semantics, realizability, absolute realizability, generalized realizability, Markov’s Principle.

Agafonova M.V. On a minimal Scheffer function in the class of partial-parallel functions defined over binary rational numbers

This article discusses the class of neural partial-parallel functions with binary rational coefficients (BPP-class). It is proven that a minimal Scheffer function exists in this class. By a minimal Scheffer function in the class, we mean a function of this class that generates this class by superposition operations and contains the minimum possible number of variables and threshold functions. It was established that a minimal Scheffer function contains two variables and one threshold function. The article also provides one of the necessary conditions for the Scheffer-type function to be contained in the BPP-class.

Keywords: class, partial-parallel functions, neural functions, binary coefficients, superposition operations, Scheffer function.

Efimov A.A. The top assessment of energy consumption in a class of volume schemes

In this work volume schemes which are generalization of plane schemes in space are considered. The class of the schemes implementing boolean functions was considered. For this class upper assessment of potential — a measure of the power equal to quantity of the circuit elements giving unit on this input pattern is received. It is shown that any function from n of variables can be implemented the volume scheme which potential does not exceed \[O(2^{n/3})\].

Keywords: schemes from functional elements, volume schemes, scheme power, potential.

Konovalov A. Yu. The criterion of the soundness and the comleteness of the classical logic with respect to the V-realizability.

Let L be an extension of the language of arithmetic, V a class of number-theoretical functions. A notion of the V-realizability for predicate formulas is defined in such a way that predicate variables are substituted by formulas of the language L. It is proved that the classical logic is sound and complete with respect to the semantics of the V-realizability if V contains all L-definable functions.

Keywords: constructive semantics, realizability, generalized realizability, formal arithmetic.

Kudryavtsev V.B., Babin D.N. Classification of bases in P_k by the property of decidability of the completeness for automata.

We consider the problem of the completeness of systems of automaton functions with operations of superposition and feedback of the form \[\Phi \cup \nu\] , where \[\Phi \subseteq P_k\], \[ \nu \] is finite. For k = 2, the solution of this problem leads to the separation of the lattice of closed Post classes into strong ones (whose presence in the system under study guarantees the solvability of the completeness problem of finite bases) and weak ones (which does not guarantee this in the system under study). For k = 2 this problem was solved for systems of automaton functions of arbitrary form (Babin DN 1998). In this paper, we investigate corollaries and possible extensions of this problem, as well as some results for \[ P_k \], k > 2.

Keywords: Boolean function, finite automaton, algorithmic solvalibility of functions by formulas.