Open AccessComplex system engineering based on the automaton models requires a reasoned data structure selection to implement them. The problem of automaton representation and data structure selection to be used in it has been understudied. Arbitrary data structure selection for automaton model software implementation leads to unnecessary computational burden and reduces the developed system efficiency. This article proposes an approach to the reasoned selection of data structures to represent finite algoristic automaton basic models and gives practical considerations based on it.
Static and dynamic data structures are proposed for three main ways to assign Mealy and Moore automatons: a transition table, a matrix of coupling and a transition graph. A thirddimensional array, a rectangular matrix and a matrix of lists are the static structures. Dynamic structures are list-oriented structures: two-level and three-level Ayliff vectors and a multi-linked list. These structures allow us to store all required information about finite state automaton model components - characteristic set cardinalities and data of transition and output functions.
A criterion system is proposed for data structure comparative evaluation in virtue of algorithmic features of automata theory problems. The criteria focused on capacitive and time computational complexity of operations performed in tasks such as equivalent automaton conversions, proving of automaton equivalence and isomorphism, and automaton minimization.
A data structure comparative analysis based on the criterion system has done for both static and dynamic type. The analysis showed advantages of the third-dimensional array, matrix and two-level Ayliff vector. These are structures that assign automaton by transition table. For these structures an experiment was done to measure the execution time of automation operations included in criterion system.
The analysis of experiment results showed that a dynamic structure - two-level Ayliff vector - is more beneficial for an increasing task dimension. Static structures such us the thirddimensional array and matrix should be preferred to represent only automaton with small component set cardinalities.
The article results may find application in software system development using the automata theory when a memory and time consumption minimization of finite state automaton model processing is required. In prospect, it is necessary to work at an optimization of data structures representing the finite state automaton basic models and algorithms to solve problems with their use. Other models that have a practical application are also of interest, for example, nondeterministic automatons. It is advisable to explore machine implementation aspects of such models in terms of computational complexity of applied algorithms.