sibsutisВестник СибГУТИThe Herald of the Siberian State University of Telecommunications and Information Science1998-6920СибГУТИ10.55648/1998-6920-2022-16-2-12-22sibsutis-129Research ArticleСтатьиПрименение специализированных детерминированных конечных автоматов для прогнозирования временных рядовApplication of specialized DFA for time series forecastingПавловаУльяна ВладимировнаPavlovaUlyana VladimirovnaПавлова Ульяна Владимировна, аспирант 1-го курса института ИВТ, ассистент кафедры ПМиК 

630102, Новосибирск, ул. Кирова, 86

Ulyana V. Pavlova, Postgraduate student, Department of Appl. Math. and Cybernetics

Novosibirsk

uljana.pavlova2012@yandex.ruРакитскийАнтон АндреевичRakitskiyAnton AndreevichРакитский Антон Андреевич, к.т.н, доцент кафедры ПМиК; научный сотрудник НГУ; старший научный сотрудник ИВТ СО РАН

630102, Новосибирск, ул. Кирова, 86

Anton A. Rakitskiy, Candidate of technical sciences, Docent

Novosibirsk

rakitsky.anton@gmail.comСибГУТИРоссияSiberian State University of Telecommunications and Information ScienceRussian Federation20222207202202Вестник СибГУТИ1222Copyright © Павлова У.В., Ракитский А.А., 20222022Павлова У.В., Ракитский А.А.Pavlova U.V., Rakitskiy A.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.sibsutis.ru/jour/article/view/129

В данной работе рассматривается возможность использования детерминированных конеч-ных автоматов для прогнозирования временных рядов в режиме реального времени. Длярешения этой проблемы авторами предлагается модификация автомата с десятью считы-вающими головками, предназначенного для распознавания мультилинейных последова-тельностей. В статье представлены модификации этого автомата, алгоритмы для их реали-заций и приведены результаты, полученные с их помощью. Кроме того, в работе представ-лен метод изменения алгоритма работы автомата, обеспечивающий его пошаговое выпол-нение

In this paper the possibility of using deterministic finite automaton to forecast time series in real time is con-sidered. To solve this problem, a modification of the automaton with 10 reading heads designed to recognizemultilinear sequences is proposed. The article presents modifications of this automaton, algorithms for theirimplementation, and demonstrates the results for various time series. In addition, the paper presents a methodfor changing the algorithm of the automaton ensuring its step-by-step execution

конечный автоматпрогнозированиеанализ временных рядовтеория ин- формациимашинное обучениесжатие данных.finite state automatonforecastingtime series analysisinformation theorymachine learningdata compression.ReferencesSumi S. M., Zaman M. F., Hirose H. A rainfall forecasting method using machine learning models and its application to the Fukuoka city case // International Journal of Applied Mathematics and Computer Science. 2012. V. 22, № 4. P. 841–854.Sumi S. M., Zaman M. F., Hirose H. A rainfall forecasting method using machine learning models and its application to the Fukuoka city case. International Journal of Applied Mathematics and Computer Science, 2012, vol. 22, no. 4, pp. 841-854. DOI: 10.2478/v10006-012-0062-1.Carreno E. M., Rocha R. M., Padilha-Feltrin A. A cellular automaton approach to spatial electric load forecasting // IEEE Transactions on Power Systems. 2010. V. 26, №. 2. P. 532–540.Carreno E. M., Rocha R. M., Padilha-Feltrin A. A cellular automaton approach to spatial electric load forecasting. IEEE Transactions on Power Systems, 2010, vol. 26, no. 2, pp. 532-540. DOI: 10.1109/tpwrs.2010.2061877.Abeyrathna K. D. A Novel Multi-step Finite-State Automaton for Arbitrarily Deterministic Tsetlin Machine Learning // International Conference on Innovative Techniques and Applications of Artificial Intelligence. Cambridge, UK, December 15–17, 2020. V. 12498. P. 108.Abeyrathna K. D. A Novel Multi-step Finite-State Automaton for Arbitrarily Deterministic Tsetlin Machine Learning. International Conference on Innovative Techniques and Applications of Artificial Intelligence, Cambridge, UK, 15-17 December, 2020, vol. 12498, pp. 108. DOI: 10.1007/978-3-030-63799-6_8.Alevizos E., Artikis A., Paliouras G. Wayeb: a tool for complex event forecasting // 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning. Awassa, Ethiopia, November 16–21, 2018.Alevizos E., Artikis A., Paliouras G. Wayeb: a tool for complex event forecasting. 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning, Awassa, Ethiopia, 16-21 November, 2018.Qin L., Hammerschmidt C., Pellegrino G., Verwer S. Short-term Time Series Forecasting with Regression Automata // ACM SIGKDD 2016 Workshop on Mining and Learning from Time Series (MiLeTS). San Francisco, California, USA, August 13–17, 2016. DOI: 10.1145/1235.Qin L., Hammerschmidt C., Pellegrino G., Verwer S. Short-term Time Series Forecasting with Regression Automata. ACM SIGKDD 2016 Workshop on Mining and Learning from Time Series (MiLeTS), San Francisco, California, USA, 13-17 August, 2016. DOI: 10.1145/1235.Alevizos E., Artikis A., Paliouras G. Event Forecasting with Pattern Markov Chains // 11th ACM Int. Conf. on Distributed and Event-based Systems, 2017. P. 146–157.Alevizos E., Artikis A., Paliouras G. Event Forecasting with Pattern Markov Chains. 11th ACM Int'l Conf. on Distributed and Event-based Systems, 2017, pp. 146-157. DOI: 10.1145/3093742.3093920.Jenkins G. M., Box G. Time Series Analyses. Forecasting and control. Holden-Day, 1976. 589 p.Jenkins G. M., Box G. Time Series Analyses. Forecasting and control. Holden-Day, 1976, 589 p.Lysyak A. S., Ryabko B. Y. Time series prediction based on data compression methods // Problems of Information Transmission. 2016. V. 52, № 1. P. 92–99.Lysyak A. S., Ryabko B. Y. Time series prediction based on data compression methods. Problems of Information Transmission, 2016, vol. 52, no. 1, pp. 92-99. DOI: 10.1134/s0032946016010075.Чирихин К. С., Рябко Б. Я. Экспериментальное исследование точности методов прогноза, базирующихся на архиваторах // Вестник Новосибирского государственного университета. Серия: Информационные технологии. 2018. Т. 16, №. 3. C. 145–168.Chirikhin, K. S., and B. Ya. Ryabko. Jeksperimental'noe issledovanie tochnosti metodov prognoza, bazirujushhihsja na arhiva-torah [Experimental Study of the Accuracy of Compression-Based Forecasting Methods]. Vestnik NSU, Series: Information Technologies, 2018, vol. 16, no. 3, pp. 145-158. DOI: 10.25205/1818-7900-2018-16-3-145-158.Hopcroft J. E., Ullman J. D. Introduction to automata theory, languages, computation. AddisonWesley publishing company, 1979. 427 p.Hopcroft J.E., Ullman J.D. Introduction to automata theory, languages, computation. Addison-Wesley publishing company, 1979, 427 p.Smith T. Prediction of infinite words with automata // Theory of Computing Systems. 2018. V. 62, № 3. P. 653–681.Smith T. Prediction of infinite words with automata. Theory of Computing Systems, 2018, vol. 62, no. 3, pp. 653 - 681. DOI: 10.1007/s00224-016-9739-4.Павлова У. В., Ракитский А. А. Исследование возможности применения автоматов для прогнозирования временных рядов // РНТК «Обработка информации и математическое моделирование», СибГУТИ, 25–26 апреля 2019. С. 168–172.Pavlova U. V., Rakitsky A. A. Issledovanie vozmozhnosti primenenija avtomatov dlja prognozirovanija vremennyh rjadov [Investigation of the possibility of using automata to predict time series]. Rossijskaja nauchno-tehnicheskaja konferencija, Novosibirsk, 25-26 April, 2019, pp. 168-172.Pavlova U., Rakitskiy A. Time Series Forecasting Method Based on Finite State Machine // International Conference of Young Specialists on Micro/Nanotechnologies and Electron Devices (EDM). Aya, Altai Region, Russia, June 30 – July 3, 2021. P. 533–536.Pavlova, U., Rakitskiy, A. Time Series Forecasting Method Based on Finite State Machine. 2021 IEEE 22nd International Conference of Young Professionals in Electron Devices and Materials (EDM), Aya, Altai Region, Russian Federation, 30 June – 3 July, 2021, pp. 533-536. DOI: 10.1109/edm52169.2021.9507729.Pavlova U., Rakitskiy A. Development and Research of the Time Series Prediction Method Based on Finite State Automaton // Ural Symposium on Biomedical Engineering, Radioelectronics and Information Technology (USBEREIT), Yekaterinburg, Russia, 13–14 May, 2021. P. 305–307.Pavlova, U., Rakitskiy, A. Development and Research of the Time Series Prediction Method Based on Finite State Automaton. 2021 Ural Symposium on Biomedical Engineering, Radioelectronics and Information Technology (USBEREIT), Yekaterinburg, Russian Federation, 13-14 May, 2021, pp. 305-307. DOI: 10.1109/usbereit51232.2021.9455056.Павлова У. В., Ракитский А. А. Разработка и исследование метода прогнозирования временных рядов на основе конечных автоматов // РНТК «Обработка информации и математическое моделирование», СибГУТИ, 23–24 апреля 2020. С. 142–145.Pavlova U. V., Rakitsky A. A. Razrabotka i issledovanie metoda prognozirovanija vremennyh rjadov na osnove konechnyh avtomatov [Development and research of a time series forecasting method based on finite automata]. Rossijskaja nauchno-tehnicheskaja konferencija, Novosibirsk, 23-24 April, 2020, pp. 142-145.UCI Machine Learning Repository [Электронный ресурс]. URL: https://archive.ics.uci.edu/ml/index.php (дата обращения: 28.01.2022).UCI Machine Learning Repository, available at: https://archive.ics.uci.edu/ml/index.php (accessed 28.01.2022).

The authors declare that there are no conflicts of interest present.