A machine learning approach to synchronization of automata. (1st May 2018)

• Record Type: Journal Article
• Authors: Podolak, Igor; Roman, Adam; Szykuła, Marek; Zieliński, Bartosz
• Is Part Of: Expert systems with applications. Volume 97(2018)
• Page Start: 357
• Page End: 371
• Publication Date: 2018-05-01
• Subjects: Synchronizing automata -- Reset words -- Černý conjecture -- Synchronizing words -- Machine learning; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2017.12.043
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: We introduce a set of features that describe finite automaton. We use machine learning methods to predict the reset word length for automata. We investigate the importance of the consecutive features for the prediction. Abstract: We present a novel method to predict the length of the shortest synchronizing words of a finite automaton by applying the machine learning approach. We introduce several so-called automata features which depict the structure of an automaton, and use them with machine learning algorithms. The article discusses effectiveness of the machine learning approach in predicting the length of the shortest synchronizing words. We also examine the impact of particular features on this length, which may be helpful in methods of constructing automata as models of real systems, algorithms finding synchronizing words, and further theoretical research on synchronizing automata and the Černý conjecture.