UDC

519.178:512.53

Authors

Larisa V. Zyablitseva*, Sergey A. Pestov*
*Northern (Arctic) Federal University named after M.V. Lomonosov (Arkhangelsk, Russian Federation)
Corresponding author: Larisa Zyablitseva, address: ul. Uritskogo, 68, korp. 3, Arkhangelsk, 163002, Russian Federation; e-mail: zlarisav@yandex.ru

Abstract

Isomorphism of two commutative idempotent semigroups (semilattices) can be laid down by the algorithms of graph theory. For this, the graph is associated with the semilattices, and in the case when the resulting graph is a tree, known algorithms for checking tree isomorphism are used to verify the isomorphism of such semilattices. Another kind of graphs, which has a checking algorithm of isomorphism (differing from an exhaustive algorithm) are planar graphs. The article solves the question whether the graph of an arbitrary semilattice is a tree, a planar graph. We implement an algorithm to find out isomorphism of semilattices whose graphs are trees. This algorithm can be applied to arbitrary semilattices. In this case, for isomorphic semilattices the answer is true, and for nonisomorphic semilattices it can be erroneous. The paper demonstrates, which code word is given to an arbitrary semilattice, and the fact that this code word can serve as an invariant for checking the isomorphism of such a semilattice. We consider other invariants of graph theory that can be successfully applied to semilattices, and solve the question of completeness of the presented system of invariants. The resulting program for two arbitrary semilattices, given by Cayley tables, gives the information about the graphs (their invariants), determines their isomorphism. In the case of isomorphism, a bijective mapping of the elements of these semilattices is given. Using the program, the authors analyze all semigroups from the first to the eighth orders and find for each order the number of semilattices whose graphs are trees. The set of the proposed invariants for semilattices of no higher than eighth order is a complete system of invariants.

Keywords

semigroup, graph, graph isomorphism, semigroup isomorphism, semilattice, tree, planar graph

References

1. Zyablitseva L.V., Pestov S.A. Primenenie algoritmov proverki izomorfizma grafov v teorii polugrupp [Test Algorithms of the Graph Isomorphism in the Theory of Semigroups]. Vestnik Severnogo (Arkticheskogo) federal’nogo universiteta. Ser.: Estestvennye nauki, 2016, no. 4, pp. 69–74.
   
2. Clifford A., Preston G. The Algebraic Theory of Semigroups. Vol. 1. Mathematical Surveys and Monographs, no. 7, pt. 1. Providence, USA, 1961. 224 p.
   
3. Ore O. Theory of Graphs. American Mathematical Society Colloquium Publications, 1962, vol. 38. 270 p.
   
4. Aho A.V., Hopcroft J.E., Ullman J.D. The Design and Analysis of Computer Algorithms. London; Amsterdam; Don Mills; Sydney, Addison-Wesley Publ., 1974. 470 p.
   
5. 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 18.09.2015).
   
6. Smal A. Explanation for “Tree Isomorphism” Talk. Saint Petersburg, 2008. 10 p. Available at: http://www14. informatik.tumuenchen.de/konferenzen/Jass08/courses/1/smal/Smal_Paper.pdf (accessed 10.09.2015).
   
7. Hopcroft J., Tarjan R. Isomorphism of Planar Graphs. Proc. 4th Ann. Symp. on the Theory of Computing. Shaker Heights, Ohio, USA, 1972, pp. 131‒152.
   
8. Taran I.A., Korabel’shchikova S.Yu. Postroenie diagrammy podpoley konechnogo polya [Construction of a Diagram of Subfields of a Finite Field]. Sovremennye issledovaniya v oblasti estestvennykh i tekhnicheskikh nauk: Mezhdistsiplinarnyy poisk i integratsiya: materialy II nauch.-prakt. vseros. konf. (shkoly-seminara) molodykh uchenykh (Tol’yatti, 1–3 dekabrya 2015 g.) [Modern Research in the Natural and Technical Sciences: Interdisciplinary Search and Integration: Proc. 2nd Sci. Practical All-Russ. Conf. of Young Scientists (Togliatti, December 1–3, 2015)]. Togliatti, 2015, pp. 122–125. (In Russ.)
   
9. Korabel’shchikova S.Yu., Mel’nikov B.F. Maksimal’nye prefiksnye kody i podklassy klassa kontekstnosvobodnykh yazykov [Maximal Prefix Codes and Subclasses of the Context-Free Languages Class]. Vestnik Severnogo (Arkticheskogo) federal’nogo universiteta. Ser.: Estestvennye nauki, 2015, no. 1, pp. 121–129.