TEST ALGORITHMS OF THE GRAPH ISOMORPHISM IN THE THEORY OF SEMIGROUPS
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.