Semilattice graphs, matrix representations of idempotent semigroups and Waterloo automaton semilattices
Abstract
Semigroups are a numerous class of algebras due to the fact that only one axiom of associativity of an operation must hold in a semigroup. So, for example, there are 836021 semigroups of the seventh order, and already 1843120128 semigroups of the eighth order. For comparison, there is only one group of order seven, 5 groups of order eight. It is convenient to define semigroups of small orders by the Cayley table, but even in this case it can be quite difficult to get some idea of the structure of the semigroup. In the case when it is possible to obtain an exact matrix representation of a semigroup, the structure of the semigroup becomes clear, since matrices are a well-studied semigroup with a multiplication operation defined in a certain way. As a rule, it is difficult to find the exact matrix representation of a semigroup; first, it is convenient to find a representation of this semigroup by a transformation semigroup. In this case, in what follows, instead of the elements of the original semigroup, we consider the corresponding transformations. The article considers the semigroups of idempotents S, the corresponding semigroups of transformations, as well as the connection between the ranks of these transformations and the presence of an exact matrix representation of the original semigroups. Since any semigroup of idempotents is a semilattice of rectangular semigroups, we first consider the exact matrix representations of a finite semilattice and an arbitrary rectangular semigroup, then describe the exact representation of the semilattice of right zero semigroups in the case when the right shifts of all elements of such a semigroup have a finite rank. The second part of this paper presents the results of a study of semilattices on a set of grid subsets of the Waterloo automaton.
Full Text:
PDF (Russian)References
Clifford A. Matrix representation of completely simple semigroups // Amer.J.Math. 1942. Vol. 64. P. 327–342.
Clifford A.H., Preston G.B. The algebraic theory of semigroups. Vol.1,2. Providence: Amer. Math. Soc., 1967.
Ponizovsky I.S. On irreducible matrix representations of finite associative systems // Proceedings of Kemer. ped. institute. 1956. Vol. 1. P. 245–250 (in Russian).
Higman D. Indecompasable representations of completely simple semigroups // Amer.J.Math. 1954. Vol. 21. P. 377–381.
Ponizovsky I.S. On matrix representations of finite commutative semigroups. // Sib. Math. J. 1970. Vol. XI. P. 1098–1106 (in Russian).
Okninski J. Linear representation of semigroups // Proc. Bercley Workshop on Monoids. 1991. P. 563–581.
Abstract algebra. Vol. 2 / Artamonov V.A., Saliy V.N., Skornyakov L.A. et al. Moscow: Nauka Publ., Phizmatlit, 1991 (in Russian).
Zyablitceva L.V., Korabelshchikova S.Yu., Popov I.N. Some special semigroups and their homomorphisms. Arkhangelsk: NArFu Publ., 2013 (in Russian).
Zyablitceva L.V., Pestov S.A. Algorithm for checking isomorphism of semilattices using graph theory invariants // Arctic Environmental Research. 2017. P. 368–375 (in Russian).
Dang V.V., Dodonova N.L., Korabelshchikova S.Yu, Melnikov B.F. SH-weak duality of semigroups and minimum semigroup of SH-approximation // University proceedings. Volga region. Physical and mathematical sciences. 2019. No. 1 (49). P. 29–39 (in Russian).
Melnikov B.F. Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part I. Extracting the root from the language // International Journal of Open Information Technologies. 2022. Vol. 10. No. 4. P. 1–9 (in Russian).
Melnikov B.F. Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part II. Constructing an inverse morphism // International Journal of Open Information Technologies. 2022. Vol. 10. No 5. P. 1–8 (in Russian).
Melnikov B.F. Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part III. The condition for the existence of a lattice // International Journal of Open Information Technologies. 2022. Vol. 10. No. 7. P. 1–9 (in Russian).
Dolgov V., Melnikov B., Melnikova A. The loops of the basis finite automaton and the connected questions // Bulletin of the Voronezh State University. Series: Physics. Mathematics. 2016. No. 4. P. 95–111 (in Russian).
Dolgov V., Malnikov B. Construction of universal finite automaton. II. Examples of algorithms functioning // Bulletin of the Voronezh State University. Series: Physics. Mathematics. 2014. No. 1. P. 78–85 (in Russian).
Kameda T., Weiner P. On the state minimization of nondeterministic finite automata. IEEE Transactions on Computers. 1970. Vol. C-19. No. 7. P.617–627.
Abramyan M.E. Computing the weight of subtasks in state minimization of nondeterministic finite automata by the branch and bound method // University proceedings. Volga region. Physical and mathematical sciences. 2021. No. 2 (58). P. 46–52 (in Russian). doi:10.21685/2072-3040-2021-2-4
Melnikov B.F. Regular languages and nondeterministic finite automata: a monograph. – M. : RGSU Publ., 2018 (in Russian).
Refbacks
- There are currently no refbacks.
Abava Кибербезопасность MoNeTec 2024
ISSN: 2307-8162