Abstract

Content

Introduction
1. Goals, objectives and expected results
2. Theme urgency
3. Review of research and development
3.1. Overview of International Sources
3.2. Overview of national sources
3.3 Overview of local sources
4. Statement of the problem and the results obtained
Conclusion
References

Introduction

In this paper, we continue to study the properties of automata subject to the transfer of arcs under the condition that the automaton is group and does not change its behavior under the action of the transfer.

We say that an automaton admits a transfer if, as a result, it produces an automaton isomorphic to the original automaton. Such a transfer is called admissible, and the permissible transfer of k-arcs will be called k-transfer.

1. Goals, objectives and expected results

The object of the investigation is the behavior of the finite reduced group automaton in the transfer of arcs.

The subject of the study is the identification of conditions under which the automaton admits the transfer of k-arcs, while preserving the isomorphism and property of being group.

The aim of the master's thesis is to develop and study the method of analysis of group automata and the permissible arrows transfer.

The main tasks of the work:

analyze the behavior of the group automaton as a result of transferring k-arcs, where k ≥ 1;
find out the existence of admissible k-transfers and describe the structure of automata admitting them;
develop an algorithm for constructing admissible k-transfers;

2. Theme urgency

The present paper refers to the theory of experiments with automata. An experiment is the process of feeding a sequence of input signals to an automaton, observing the corresponding reaction of an automaton, and inferring the conclusion about the functioning and properties of an automaton based on these observations and a priori information about the automaton. The main task of the theory of experiments is to develop effective experiments that enable us to obtain certain information about the structure of the automaton, its functions, and the characteristics of the information conversion process carried out by this automaton.

Thus, the study of the model of a finite automaton and the study of its behavior is an actual problem.

3. Review of research and development

3.1 Overview of International Sources

The founding of the theory of experiments with automata was laid by Moore [1]. In his works the study was conducted in two directions: indistinguishability of automata by any multiple and no simple experiment, and also recognition of the automaton and its states by means of such experiments. The methods and results of the analysis of automata and algorithms for carrying out experiments with them are presented quite fully in Gill's famous book [2].

3.2 Overview of national sources

Domestic works in the field of experiments with automata are associated with the names of A.M. Bogomolov and his students, M.P. Vasilevsky, V.N. Noskova, N.V. Evtushenko, A.F. Petrenko, I.K. Ryssova, V.A. Tverdokhlebova, S.V. Yablonsky, VB Kudryavtsev, and others [3-11].

The theory of experiments is intensively developing at the present time. In [12-13], a number of results were obtained related to the analysis of the behavior of automata under the influence of environmental factors on them. In a number of papers, the effect of transferring arcs to the behavior of an automaton was studied. In the theory of graphs, related problems were also considered, where the problem of determining when one of the graphs (the automaton) can be obtained from another as a result of some sequence of transfers of arcs was studied [14].

3.3 Overview of local sources

In the Donetsk National Technical University (Department of System Analysis and Artificial Intelligence), the behavior of an automaton subject to transfer of arcs was studied in the works of Kopytova OM, Burlayeva EI, Shvets OA. , etc. The following main results were obtained in [15-19].

4. Statement of the problem and the results obtained

States, input and output symbols, respectively, and δ, λ are the transition and output functions, with ∀ x: { δ(s, x) | s ∈ S} = S .

In our case, the automaton can be conveniently defined as a transition graph whose vertices correspond to states in S, and the arcs are the quadruples (s, x, y, t), where t = δ (s, x), y = λ (s, x) . A pair (x, y) is called an arc mark, s is its beginning, and t is an end. If e = (t, x, y, u) is an arc in the transition graph of the automaton A, then transferring this arc from the state u to a state v different from u is called replacing it by an arc (t, x, y, v).

The effect of the transfer of arcs to the behavior of the automaton will be studied as follows:

first consider the transfer of exactly one arc;
then we formulate the results concerning the transfer of exactly 2 arcs;
after this we proceed to the study of the transfer of k-arcs, where > 2;

To date, the following results have been obtained:

Theorem 1. The transfer of one arc in a group automaton always leads to a nonisomorphic automaton.

Theorem 2. The transfer of two arcs in a group automaton always leads to a nonisomorphic automaton.

Theorem 3. For any k ≥ 3, there exists a group automaton that allows the transfer of k-arcs.

Conclusion