Алгоритмы преобразования конечных автоматов, соответствующих бесконечным итерационным деревьям
Аннотация
В настоящей статье мы работаем с несколькими различными вариантами конечных автоматов, каждый из которых соответствует бесконечному итерационному дереву, построенному для некоторого заданного морфизма. При этом каждый из построенных для некоторого морфизма автоматов описывает основные свойства этого морфизма. Кроме того, в каждом случае (т. е. для каждого варианта автомата) возникает также следующая "обратная задача": необходимо описать морфизм (либо просто указать пару языков), для которого получается такой заданный автомат.
Мы приводим компьютерную программу построения одного из таких автоматов – т. н. автомата PRI. После этого мы рассматриваем подробный пример автомата PRI для пары несовпадающих языков. Продолжая рассматривать этот пример, мы с последним автоматом выполняем обычные преобразования, описанные и неоднократно применённые в наших предыдущих публикациях, а именно – детерминизацию и канонизацию зеркального автомата для возможного применения полученных результатов в алгоритме минимизации недетерминированных автоматов. В рассматриваемой нами ситуации таким минимальным автоматом является другой строимый на основе заданного дерева морфизма автомат – недетерминированный, т. н. автомат NSPRI# – и равенство этих автоматов (что влечёт эквивалентность PRI и NSPRI#) мы также показываем в статье на примере.
На основе автомата NSPRI# с помощью тривиального (но неэквивалентного) преобразования строится недетерминированный автомат NSPRI – подробное исследование которого предполагается в дальнейших публикациях. Интерес представляют также примеры автоматов PRI и NSPRI# для пар совпадающих языков – мы также приводим один такой пример в настоящей статье.
Литература
2.Melnikov B., Melnikova A. Infinite trees in the algorithm for checking the equivalence condition of iterations of finite languages. Part II. International Journal of Open Information Technologies. 2021; 9(5):1-11. Available at: https://elibrary.ru/item.asp?id=45671876 (accessed 19.02.2021). (In Russ., abstract in Eng.)
3.Melnikov B., Melnikova A. Some properties of the basis finite automaton. Korean Journal of Computational & Applied Mathematics. 2002; 9(1):135-150. (In Eng.) DOI: https://doi.org/10.1007/BF03012345
4.Melnikov B., Tsyganov A. The state minimization problem for nondeterministic finite automata: the parallel implementation of the truncated branch and bound method. Proceedings of the International Symposium on Parallel Architectures, Algorithms and Programming (PAAP-2012). Taipei, Taiwan; 2012. p. 194-201. (In Eng.)
5.Melnikov B., Dolgov V. Some more algorithms for Conway's universal automaton. Acta Universitatis Sapientiae, Informatica. 2014; 6(1):5-20. (In Eng.) DOI: https://doi.org/10.2478/ausi-2014-0015
6.Melnikov B. The complete finite automaton. International Journal of Open Information Technologies. 2017; 5(10):9-17. Available at: https://elibrary.ru/item.asp?id=30101608 (accessed 19.02.2021). (In Eng.)
7.Dolgov V., Melnikov B. Construction of universal finite automaton. I. From theory to the practical algorithm. Proceedings of Voronezh State University. Series: Physics. Mathematics. 2013; (2):173-181. Available at: https://elibrary.ru/item.asp?id=20267924 (accessed 19.02.2021). (In Russ., abstract in Eng.)
8.Dolgov V., Melnikov B. Construction of universal finite automaton. II. Examples of algorithms functioning. Proceedings of Voronezh State University. Series: Physics. Mathematics. 2014; (1):78-85. Available at: https://elibrary.ru/item.asp?id=21445963 (accessed 19.02.2021). (In Russ., abstract in Eng.)
9.Melnikov B.F., Vakhitova A.A. Some more on the finite automata.Korean Journal of Computational & Applied Mathematics. 1998; 5(3):495-505. (In Eng.) DOI: https://doi.org/10.1007/BF03008877
10.Melnikov B.F., Sciarini-Guryanova N.V. Possible edges of a finite automaton defining a given regular language. Korean Journal of Computational & Applied Mathematics. 2002; 9(2):475-485. (In Eng.) DOI: https://doi.org/10.1007/BF03021555
11.Lombardy S., Sakarovitch J. The universal automaton. In: J. Flum, E. Grädel, T. Wilke (Eds.) Logic and Automata: History and Perspectives. Texts in Logic and Games, vol. 2. Amsterdam University Press; 2007. p. 457-504. (In Eng.)
12.Dedekind R. Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler. Gesammelte Werke, vol. 2. Braunschweig; 1897. p. 103-148. (In German)
13.Korshunov A. On the number of monotone Boolean functions. Problemy kibernetiki = Problems of Cybernetics. 1981; 38:5-108. (In Russ.)
14.Abramyan M.E., Melnikov B.F. On the application of some heuristics in the study of the problem of state minimization of nondeterministic finite automata by the branch and bound method. Part 1. International Journal of Open Information Technologies. 2020; 8(9):1-7. Available at: https://elibrary.ru/item.asp?id=43925422 (accessed 19.02.2021). (In Russ., abstract in Eng.)
15.Abramyan M.E., Melnikov B.F. On the application of some heuristics in the study of the problem of state minimization of nondeterministic finite automata by the branch and bound method. Part 2. International Journal of Open Information Technologies. 2020; 8(10):1-9. Available at: https://elibrary.ru/item.asp?id=44106795 (accessed 19.02.2021). (In Russ., abstract in Eng.)
16.Abramyan M.E., Melnikov B.F. Investigation of the problem of state minimization of nondeterministic finite automata using the branch and bound method. Cloud of Science. 2020; 7(2):297-319. Available at: https://elibrary.ru/item.asp?id=42708816 (accessed 19.02.2021). (In Russ., abstract in Eng.)
17.Alekseyeva A.G., Melnikov B.F. Iterations of finite and infinite languages and nondeterministic finite automata. Science Vector of Togliatti State University. 2011; (3):30-33. Available at: https://elibrary.ru/item.asp?id=18066263 (accessed 19.02.2021). (In Russ., abstract in Eng.)
18.Melnikov B.F. The equality condition for infinite catenations of two sets of finite words. International Journal of Foundations of Computer Science. 1993; 4(3):267-274. (In Eng.) DOI: https://doi.org/10.1142/S0129054193000171
19.Melnikov B.F. A new algorithm of the state-minimization for the nondeterministic finite automata. Korean Journal of Computational & Applied Mathematics. 1999; 6(2):277-290. (In Eng.) DOI: https://doi.org/10.1007/BF03014374
20.Perrin D. Finite Automata. In: J. van Leeuwen (Ed.) Formal Models and Sematics. Handbook of Theoretical Computer Science, vol. B. Elsevier Science; 1990. p. 3-57. (In Eng.) DOI: https://doi.org/10.1016/B978-0-444-88074-1.50006-8
21.Gruber H., Holzer M. Provably Shorter Regular Expressions From Finite Automata. International Journal of Foundations of Computer Science. 2013; 24(8):1255-1279. (In Eng.) DOI: https://doi.org/10.1142/S0129054113500330
22.Fernau H. Algorithms for learning regular expressions from positive data. Information and Computation. 2009; 207:521-541. (In Eng.) DOI: https://doi.org/10.1016/j.ic.2008.12.008
23.Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms. 3rd edition.MIT Press; 2009. (In Eng.)
24.Meng J., Lin T. Regarding covering as a collection of binary relations. In: 2014 IEEE International Conference on Granular Computing (GrC). Noboribetsu, Japan; 2014. p. 191-195. (In Eng.) DOI: https://doi.org/10.1109/GRC.2014.6982833
25.Carayol A., Loding C., Serre O. Automata on Infinite Trees with Equality and Disequality Constraints Between Siblings. In: 2016 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS).NewYork, NY; 2016. p. 1-10. (In Eng.)
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
