# 2019 year, volume 23, issue 4 (PDF)

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.

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.

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.

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.

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.

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.

# 2019 year, volume 23, issue 3 (PDF)

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.

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.

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.

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

Keywords: pattern recognition, images, image codes.

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.

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.

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.

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.

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.

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.

# 2019 year, volume 23, issue 2 (PDF)

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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)

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.