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.

← Back to archive