Algorithms for Converting Finite Automata Corresponding to Infinite Iterative Trees
Abstract
In this paper, we work with some different variants of finite automata, each of which corresponds to an infinite iterative tree constructed for some given morphism. At the same time, each of the automata constructed for a given morphism describes the main properties of this morphism. Besides, in each case (i.e., for each variant of the automaton), the following “inverse problem” also arises: to describe the morphism (or simply specify a pair of languages) for which such a given automaton is obtained.
We present a computer program for constructing one such automaton, so-called PRI automaton. After that, we consider a detailed example of a PRI automaton for a pair of different languages. Continuing to consider this example, we use the last automaton to perform usual transformations described and repeatedly applied in our previous publications, i.e., the determination and canonization of the mirror automaton for possible application of the results obtained in the algorithm for minimizing nondeterministic automata. In the considered situation, such a minimal automaton is another automaton constructed on the basis of a given morphism tree, a nondeterministic automaton, the so-called NSPRI# automaton, and we also show the equality of these automata (which implies the equivalence of PRI and NSPRI#) in the paper by an example.
Based on the NSPRI# automaton, a non-deterministic NSPRI automaton is constructed using a trivial (but non-equivalent) transformation; a detailed study of this automaton is expected in future publications. Examples of PRI and NSPRI# automata for pairs of matching languages are also of interest, we also give one such example in this paper.
References
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.)
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
