Heuristic optimization methods for linear ordering of automata

The rapid development of society is associated with two key areas of science and technology: methods of working with Big Data and Artificial Intelligence. There is a common belief that up to 80% of the data analysis process is the time spent on data preparation. One aspect of preparing data for analysis is structuring and organizing data sets (also known as data tidying). Order relations are ubiquitous, we meet them when we consider numbers, Boolean algebras, partitions, multisets, graphs, logical formulas, and many other mathematical entities. On the one hand, order relations are used for representing data and knowledge, on the other hand, they serve as important tools for describing models and methods of data analysis, such as decision trees, random forests, version spaces, association rules, and so on. Since a serious limitation of many methods of pattern mining is computational complexity, it is important to have an efficient algorithm for ordering data. In this paper, we consider deterministic automata without output signals and investigate the problem of linear ordering of such automata, which consists of building a linear order on the set of states of an automaton, that will be consistent with the action of each input signal of the automaton. To solve this problem, we consider heuristic methods of global optimization: simulated annealing method and artificial bee colony algorithm. For both methods, we made a software implementation and performed testing on a special kind of automata.