On the software implementation of the groupoid of construction of PRI automaton and related computational experiments
Abstract
This paper is a continuation of the previous paper by the same authors, which considered variants for defining the groupoid and semigroup of the primary automaton PRI. To study various emerging examples of a groupoid, which in important special cases is a semigroup, we implemented appropriate computer programs in C++ and performed computational experiments, which are described in this paper. The main purpose of creating a program and conducting computational experiments. It is an attempt to understand the internal structure of the resulting groupoids (in special cases, semigroups), as well as an attempt to “explain the nature” of the special binary relations considered in many previous papers (the so-called relations of coverability and equivalence at infinity), given on sets of finite formal languages. The program described in the article has shown its effectiveness in the study of complex examples in which the number of elements of the resulting groupoid was measured in several tens. The program produced interesting results for further interpretation, and at the same time its execution time approximately coincided with the theoretically calculated values. The main conclusions, which were obtained, in particular, as an analysis of the conducted computational experiments, can be considered as follows. It is obvious that languages over the same one-letter alphabet are equivalent at infinity. There is a connection between the condition for obtaining a semigroup and equivalence at infinity, which is shown precisely in these languages. We show that for such languages (over a one-letter alphabet), the groupoid is always a semigroup, and the latter is always commutative and is a monoid. When calculating the characters and factor representations of the elements of a semigroup of interest to us, the series of degrees contain information of idempotents in a pair consisting of an index and a period. Therefore, it is possible not to find the idempodents of the obtained semigroups separately, and calculate their number after calculating the series of degrees. Thus, based on the examples obtained by the program, we obtain descriptions of the properties of the groupoid, which can subsequently be formulated in the form of statements and theorems.
Full Text:
PDF (Russian)References
Meng Lingqian, Melnikov B. On the groupoid of the primary automaton PRI defined for one finite language // International Journal of Open Information Technologies. – 2023. – Vol. 11. No. 9. – P. 1–12. (In Russian.)
Melnikov B. Description of special submonoids of the global supermonoid of the free monoid // News of higher educational institutions. Mathematics. – 2004. – No. 3. – С. 46–56. (In Russian.)
Melnikov B. The equality condition for infinite catenations of two sets of finite words // International Journal of Foundation of Computer Science. – 1993. – Vol. 4. No. 3. – P. 267–274.
Melnikov B. Variants of finite automata corresponding to infinite iterative morphism trees. Part I // International Journal of Open Information Technologies. – 2021. – Vol. 9. No. 7. – P. 5–13. (In Russian.)
Melnikov B. Variants of finite automata corresponding to infinite iterative morphism trees. Part II // International Journal of Open Information Technologies. –2021. – Vol. 9. No. 10. – P. 1–8. (In Russian.)
Melnikov B. 2ω-finite automata and sets of obstructions of their language // The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). – 2000. – Vol. 6. No. 3. – P. 565–574.
Melnikov B., Melnikova A. Infinite trees in the algorithm for checking the equivalence condition of iterations of finite languages. Part I //International Journal of Open Information Technologies. – 2021. – Vol. 9. No. 4. – P. 1–11. (In Russian.)
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. – Vol. 9. No. 5. – P. 1–11. (In Russian.)
Meng Lingqian, Melnikov B. Eight variants of finite automata for checking the fulfillment of the iteration coverage ratio of two finite languages. Part I // International Journal of Open Information Technologies. – 2023. – Vol. 11. No. 11. – P. 1–9. (In Russian.)
Meng Lingqian, Melnikov B. Eight variants of finite automata for checking the fulfillment of the iteration coverage ratio of two finite languages. Part II // International Journal of Open Information Technologies. – 2024. – Vol. 12. No. 2. – P. 1–11. (In Russian.)
Lyapin E. Semigrouops. – Moscow, Fizmatlit. – 1960. – 592 p. (In Russian.)
Birkhoff G., Bartee T. Modern Applied Algebra. – NY, McGraw-Hill Ed. – 1970. – 431 p.
Lallement G. Semigroups and Combinatorial Applications. – NY, John Wiley & Sons. – 1979. – 376 p.
Salomaa A. Jewels of Formal Language Theory. – Rockville, Maryland, Computer Science Press. – 1981. – 144 p.
Skornyakov L. (Ed.) General algebra. Vol. 2. – Moscow, Nauka. – 1991. – 480 p. (In Russian.)
Pin J.-E. Mathematical Foundations of Automata Theory. – Berlin, Springer-Verlag. – 2012. – 310 p.
Solter N., Kleper S . Professional C++. – NJ, John Wiley & Son. – 2005. – 864 p.
Refbacks
- There are currently no refbacks.
Abava Кибербезопасность IT Congress 2024
ISSN: 2307-8162