RADIOELECTRONIC AND COMPUTER SYSTEMS

The construction concept and general principles of the operation of a new kind of finite state machine are presented, for which the input and output elements are panels of square matrices, and the transitions between their states are determined by numerical tensors of the third rank. In this case, the structure of the tensors is specified in the form of cubic grids, in whose cells' natural numbers are located according to the principle of Sudoku construction. An algorithm for constructing such tensors of arbitrary size is indicated. The structures of tensors constructed using ranked sets of natural numbers are defined as standard. It is shown that the possibility of determining Sudoku type tensors using a one-dimensional parameter is basic for the manifestation of their functional self-similarity. The property of additive conservation of the structure of numerical tensors of the third rank to the requirements of Sudoku is formulated as a theorem. It is proved that the tensor obtained by summing an arbitrary tensor structure and a constant, taking into account the introduced cyclic ranking rule, satisfies the general requirements of Sudoku. The problems of abstract and structural synthesis of finite state machine based on the analyzed tensor structures are considered. In this case, the task of abstract synthesis has traditionally been defined as the creation of a mathematical model of an automaton, and the task of structural synthesis is just the development of its functional logical scheme. Based on the ambiguity of the function of the output of the finite state machine, the possibility of the simultaneous use of several different output alphabets is substantiated. The modes of functioning of the minimal finite state machine of the proposed type are described by the example of an initial state machine with a distinguished standard initial state. In the general case, it is shown that the finite state machines defined on the group of these requirements can be attributed to generalized first-order finite-state machines (or Mealy machines) with a multi-valued output. The features of network applications of structural automata are presented. Variants of possible applications of the considered finite state machines are analyzed.

finite state machine; machine synthesis; transition tensor; Sudoku principle

Hopcroft, J. E., Motwani, R., Ullman, J. D. Introduction to automata theory, Languages and Computation. Pearson Education Limited, 2014. 488 p.

Minsky, M. L. Computation: finite and infinite machines. Englewood Cliffs, N. J., Prentice-Hall Publ., 1967. 317 p.

Fiske, M. S. Non-deterministic secure active element machine. U.S. Patent, 2015. 843 p.

Russel, E., Jarvis, A. F. Mathematics of Sudoku II, Mathematical Spectrum 39, pp. 54–58.

Penkin, Y., Khara, G. Deterministic Chaos in Vibrations of Discrete Structures of Matrix Type. Proc. Inter. Scien.-Pract. Conf. on Problems of Infocommunications Science and Technology. Kharkiv, 2018, vol. 2, pp. 548-552.

Mueller, Sc. Upgrading and Repairing PCs (19th Edition). USA, Person Education Publ., 2010. 1156 p.

Yao, Y. Three-way decision and granular computing. International Journal of Approximate Reasoning, 2018, vol. 103, pp. 107-123.