UDC

Authors

Abstract

One of the most interesting problems in the theory of semigroups is the isomorphism problem for this class of semigroups. This issue consists in the existence of an algorithm (which differs from the exhaustive algorithm) recognizing isomorphism of any two semigroups of a given class. A similar problem exists in the graph theory, and this issue has been resolved for some classes of graphs. The article considers semigroups, which are semilattices; their isomorphism can be checked by the known algorithms for the graph isomorphism testing. The corresponding graph can be found for these semigroups. This graph can be a tree; in this case we can apply the known algorithms of the trees isomorphism testing to verify the isomorphism of semigroups. The paper formulates and proves a criterion, when the semilattice graph is a tree. We have justified the choice of the algorithm of the trees isomorphism testing, described it, and presented a program written in Haskell that implements it. We should associate a tree with semilattice to apply the selected algorithm for the semilattice isomorphism testing. For this purpose the authors have developed and implemented an efficient algorithm in the Haskell language. The developed program for two semilattices, given by the Cayley tables, displays the structure of the trees relevant to semilattices, the canonical name of derived trees, tests the isomorphism of trees and semilattices. The choice and implementation of algorithms are effective; the program determines the semilattices isomorphism with a three-digit number of elements for a few seconds.

Keywords

References

1. Zyablitseva L.V., Korabel’shchikova S.Yu., Popov I.N. Nekotorye spetsial’nye polugruppy i ikh gomomorfizmy [Some Special Semigroups and Their Homomorphisms]. Arkhangelsk, 2013. 128 p. 
2. Artamonov V.A., Saliy V.N., Skornyakov L.A. Obshchaya algebra. T. 2. [General Algebra. Vol. 2]. Moscow, 1991. 480 p. 
3. Aho A.V., Hopcroft J.E., Ullman J.D. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. 
4. Ponomarenko I.N. Problema izomorfizma grafov: Algoritmicheskie aspekty [The Problem of Graphs Isomorphism: Algorithmic Aspects]. Saint Petersburg, 2010. 57 p. Available at: logic.pdmi.ras.ru/csclub/sites/default/files/graph_ isomorphism_ponomarenko_lecture_notes.pdf (accessed 06.12.2016). 
5. Gavrilov G.P., Sapozhenko A.A. Zadachi i uprazhneniya po diskretnoy matematike: ucheb. posobie [Tasks and Exercises in Discrete Mathematics]. Moscow, 2006. 416 p. 
6. Smal A. Explanation for “Tree Isomorphism” Talk. Saint Petersburg, 2008. 10 p. Available at: http://logic.pdmi. ras.ru/~smal/files/smal_jass08.pdf (accessed 06.12.2016).