SEQUENCE RECOGNITION USING FINITE AUTOMATA WITH MACHINE LEARNING

Sequence recognition is a critical task across numerous disciplines. While traditional methods utilizing Finite State Machines (FSMs) offer a structured data representation and high interpretability, their flexibility is limited. Contemporary Machine Learning (ML) algorithms exhibit high accuracy but demand substantial computational resources. Combining these paradigms can enhance the effectiveness of complex sequence recognition. This study explores the integration of FSMs with ML techniques to address sequence analysis problems. Three distinct applications are examined: text classification (spam detection), recognition of genetic sequences related to Alzheimer's disease, and image-based gesture identification. 

For each, hybrid models were developed and tested, combining Deterministic Finite Automata (DFA), Non-deterministic Finite Automata (NFA), and ML algorithms such as Random Forest, Gradient Boosting, and Multilayer Perceptrons (MLP). Experimental results indicate that these hybrid models achieve performance comparable to traditional ML methods, and in some instances, yield more accurate predictions. 

In spam classification, neural network models demonstrated the best results, with FSM-neural network combinations providing similar effectiveness. 

For genetic sequence analysis, gradient boosting-based models exhibited the highest accuracy, with the inclusion of FSMs maintaining performance while enhancing interpretability. 

In gesture recognition, neural network approaches proved most effective, but integrating FSMs with ensemble methods achieved a high level of predictive capability, surpassing conventional ML models. 

In conclusion, the integration of FSMs and ML presents a promising avenue in sequence analysis. Future research could focus on optimizing model architectures and applying them to other domains requiring high-precision recognition of intricate structures. 

1. Determinism and Nondeterminism in Finite Automata with Advice / Р. Ďuriš et al // In Lecture notes in computer science. – 2018. – Р. 3-16. https://doi.org/10.1007/978-3-319-98355-4_1.

2. Veanes M. Applications of symbolic finite automata / M. Veanes // In Lecture notes in computer science. – 2013. – Р. 16-23. https://doi.org/10.1007/978-3-642-39274-0_3.

3. An introduction to learning automata and Optimization / J.K. Kordestani et al // In Intelligent systems reference library. – 2021. Р. 1-50. https://doi.org/10.1007/978-3-030-76291-9_1.

4. Hong P. Gesture modeling and recognition using finite state machines / P. Hong, M. Turk, T.S. Huang // IEEE. – 2002. https://doi.org/10.1109/afgr.2000.840667.

5. Decombinator: a tool for fast, efficient gene assignment in T-cell receptor sequences using a finite state machine / N. Thomas et al // Bioinformatics. – 2013. – № 29(5). – Р. 542-550. https://doi.org/10.1093/bioinformatics/btt004.

6. Road network extraction: a neural-dynamic framework based on deep learning and a finite state machine / J. Wang et al // International Journal of Remote Sensing. – 2015. – № 36(12). – Р. 31443169. https://doi.org/10.1080/01431161.2015.1054049.

7. Constrained training of recurrent neural networks for automata learning / В.К. Aichernig et al // In Lecture notes in computer science. – 2022. – Р. 155-172. https://doi.org/10.1007/978-3-03117108-6_10.

8. Privacy attacks to the 4G and 5G cellular paging protocols using side channel information / S.R. Hussain et al // in Proc. Netw. Distrib. Syst. Security Symp. (NDSS). – 2019. – Р. 1-15.

9. Baray E. WLAN security protocols and WPA3 security approach measurement through aircrackng technique / E. Baray, N.K. Ojha // in Proc. 5th Int. Conf. Comput. Methodologies Commun. (ICCMC). – 2021. – Р. 23-30.

10. Vanhoef M. Dragonblood: Analyzing the Dragonfly Handshake of WPA3 and EAP-pwd / M. Vanhoef, E. Ronen // 2020 IEEE Symposium on Security and Privacy (SP). – IEEE, 2020. – P. 517533.