Candidate of Physical and Mathematical Sciences, Associate Professor of the Department 604, Aerospace Faculty
The development of finite state machines and the synthesis of neural networks come with enormous computational difficulties. The problems that are faced both by the creators of control finite state machines and the creators of neural networks are almost the same. In order for a control finite state machine to be implemented, an algorithm for its operation must be created, and then a program must be written, and finally this program must be implemented in hardware in the form of a finite state machine. It is crucial to create a finite state machine, which will be deterministic. As for neural networks, it is necessary either to set the weights on its edges with the help of experts, or it must be trained to obtain optimal weights on its edges. Both tasks, that is, the determination of finite state machines and the training of neural networks, are currently most often performed using approximate (exponential or genetic) algorithms. At the same time, few authors point out the fact that, firstly these algorithms give an error of up to 15 %, and secondly the operating time is quite long and requires large energy costs. The article has proven that control finite state machines and neural networks are equivalent based on their structure, which can be represented as a directed edge graph. Such equivalence makes it possible to use methods of normalizing arbitrary graphs to determine finite automata and synthesize neural networks. Methods of graph normalizing are extremely new, they are based on a fundamentally new approach of the extension of graph theory and will allow performing these operations using algorithms that have linear complexity or can significantly reduce the number of options when using brute force.
Разработку конечных автоматов и синтез нейросетей сопровождают огромные вычислительные трудности. Проблемы, с которыми сталкиваются как создатели управляющих конечных автоматов, так и создатели нейросетей, практически одинаковы. Для того чтобы управляющий конечный автомат мог быть реализован, надо сначала создать алгоритм его работы, потом написать программу, потом эту программу реализовать в «железе» в виде конечного автомата. Главное - надо создать, и это важно, детерминированный конечный автомат. Что касается нейросетей, то, чтобы она работала, необходимо либо задать с помощью экспертов веса на ее ребрах, либо ее надо обучить, чтобы получить оптимальные веса на ребрах. И то, и другое, то есть, детерминизация конечных автоматов и обучение нейронных сетей, в настоящее время производится чаще всего с помощью приближенных (экспоненциальных или генетических) алгоритмов. При этом часто авторы не указывают на тот факт, что, во-первых, эти алгоритмы дают ошибку до 15 %, а, во-вторых, время работы подобных алгоритмов достаточно велико, и требует больших энергетических затрат. В материале статьи доказывается, что управляющие конечные автоматы и нейросети - эквивалентны, если исходить из их структуры, которую можно представить в виде ориентированного реберного графа. Подобная эквивалентность позволяет применять для детерминизации конечных автоматов и синтеза нейросетей методы нормализации произвольных графов. Методы нормализации произвольных графов новые, они основаны на расширении теории графов и позволят применять алгоритмы линейной сложности или существенно уменьшать число вариантов при переборе.