2023 year, volume 27, issue 4 (PDF)

Chasovskikh A.A., Polovnikov V.S., Khusaenov A.A., Bointsysjournal.orgkov G.V., Konovalov A.Yu, Drobyshev A.S., Biryukova V.A. Automation of artificial neural network architectures search

A review of works on methods for automating generation of artificial neural network architectures is presented. The most detailed material is presented on the use of large language models for this. For the experiments, we used ChatGPT & Midjourney,which is available in Telegram Messenger.

Keywords: artificial neural network, large language models, neural architecture search, generative pre-training transformer (GPT).

Dergach P.S., Bahramova D.B. About automaton malfunctions in alphabetical coding

The question of possible faults in regular languages that preserve the property of ambiguity in alphabet coding is investigated in this work. It is shown that any Moore diagram that defines a language with ambiguous encoding can always maintain the property of ambiguity in the event of a one-time fault in the output value on an arrow.

Keywords: alphabet encoding, Moore diagram, automaton faults.

Korchagin N.P. Complexity of surjective homomorphism problem to reflexive cycles

In this article we explore the complexity of the decision problem which takes a graph as an input and asks, if there is a surjective homomorphism from it to some fixed graph G. We prove, that if G is a reflexive cycle with 7 or more vertices, then this problem is NP-hard. The proof is based on a novel approach, which enables reduction of a constraint satisfaction problem to the problem of satisfying a system of equations, which, in turn, is reduced to solving surjective constraint satisfaction problem.

Keywords: surjective homomorphisms, computation complexity, constraint satisfaction, polymorphisms.

Aleksiadis N.Ph. Closed classes in the functional system of rational functions with rational coefficients

A functional system is a set of functions endowed with a set of operations on these functions. The operations allow one to obtain new functions from the existing ones. Functional systems are mathematical models of real and abstract control systems and thus are one of the main objects of discrete mathematics and mathematical cybernetic. The problems in the area of functional systems are extensive. One of the main problems is deciding completeness; this problem consists in the description of all subsets of functions that are complete, i.e. generate the whole set. In our paper we consider the functional system of rational functions with rational coefficients endowed with the superposition operation for this system we study the problem of closed classes (structure, basis, number of finite and infinite closed classes). Importance of the problem of closed classes is ensured by the fact that completeness problem can frequently be solved with the help of (maximal) closed classes. The main results concerning the functional system of rational functions with rational coefficients presented in our paper are the following:
1. all finite closed classes are described explicitly;
2. the number of finite closed classes, infinite closed classes and all closed classes is found;
3. the problem of bases of closed classes is studied, namely, it is established that there exist closed classes with a finite basis, there exist closed classes with an infinite basis, and there exist closed classes without a basis; explicit examples of the corresponding closed classes are given;
4. the number of closed classes with a finite basis, the number of closed classes with an infinite basis and the number of closed classes without a basis are established.

Keywords: functional system, completeness problem, complete system, closed classes, rational function

Babin D.N, Letunovskiy A.A. About expressibility of automata with superposition

Expressibility of constant and linear automata for extended superposition is decidable. There is a theorem about decidability of automaton with linear transition expressibility.

Keywords: extended superposition, expressibility, linear automata, decidability.

Dergach P.S., Botirova N.S On changing the minimum glue length for alphabetic faults

The purpose of this thesis is to study the nature of the change in the minimum length of gluing for alphabetic coding for various types of faults in circuits. Three types of operations are considered: deletion, addition and replacement of one letter. The main issue studied in the work is to estimate how many times the length of the minimum gluing can change after performing each of the indicated operations. As a result of the study, a criterion for preserving the ambiguity property in terms of the coding scheme was found, and upper and lower bounds were obtained for the rate of change in the length of the minimum gluing in each of the three cases. These estimates are an important practical tool for designing alphabetic encodings, taking into account possible faults in circuits.

Keywords: alphabetic coding, minimum gluing, coding scheme, alphabetic encoding.