Разработка алгоритма построения решеток мультиопераций на основе неразложимых алгебр

  • Dmitriy Aleksandrovich Eremenko Санкт-Петербургский государственный электротехнический университет "ЛЭТИ" им. В.И. Ульянова (Ленина) http://orcid.org/0000-0001-5974-1485

Аннотация

Рассматриваемая в статье теория относится к теории функциональных систем. Этот раздел математики исследует функции, которые определены на конечных множествах, а также композиции этих функций. Такие функции используются в математической логике и в универсальной алгебре, в частности, в теории клонов.
Традиционными объектами исследования в универсальной алгебре являются алгебры операций и мультиопераций. Одной из основных задач в теории мультиопераций является классификация алгебр. Для решения этой задачи необходимо построить решетку алгебр. В статье представлен алгоритм построения решеток мультиопераций на основе неразложимых алгебр. Для реализации данного алгоритма были найдены все неразложимые алгебры унарных мультиопераций ранга 3, которые были представлены в виде графа по включению. Вершины графа представляют собой неразложимые алгебры, а ребра графа отражают связь между алгебрами по включению. Если между двумя вершинами графа существует путь, значит, одна алгебра является подалеброй для другой. Используя полученный граф, был реализован алгоритм построения решетки унарных мультиопераций ранга 3. Полученные результаты согласуются с результатами, которые описаны в статье Казимирова А. С., Перязева Н. А. "Алгебры унарных мультиопераций". Данный алгоритм может быть применён для построения решёток мультиопераций более высоких рангов либо больших местностей.

Сведения об авторе

Dmitriy Aleksandrovich Eremenko, Санкт-Петербургский государственный электротехнический университет "ЛЭТИ" им. В.И. Ульянова (Ленина)

аспирант кафедры вычислительной техники

Литература

1.Kearnes K.A., Szendrei Á. Cube term blockers without finiteness. Algebra Universalis. 2017; 78(4):437-459. (In Eng.) DOI: https://doi.org/10.1007/s00012-017-0476-6
2.Kuznetsov S.O., Obiedkov S.A. Algorithms for the Construction of Concept Lattices and Their Diagram Graphs. In: De Raedt L., Siebes A. (Eds.) Principles of Data Mining and Knowledge Discovery. PKDD 2001. Lecture Notes in Computer Science, vol. 2168. Springer, Berlin, Heidelberg; 2001. p. 289-300. (In Eng.) DOI: https://doi.org/10.1007/3-540-44794-6_24
3.Behrisch M., Vargas-García E. Unique inclusions of maximal C-clones in maximal clones. Algebra Universalis. 2018; 79(2):31. (In Eng.) DOI: https://doi.org/10.1007/s00012-018-0497-9
4.Badmaev S.A. On Some Maximal Clone of Partial Ultrafunctions on a Two-element Set. Journal of Siberian Federal University. Mathematics & Physics. 2017; 10(2):140-145. (In Eng.) DOI: https://doi.org/10.17516/1997-1397-2017-10-2-140-145
5.Pinus A.G. Fragments of Functional Clones. Algebra Logic. 2017; 56(4):318-323. (In Eng.) DOI: https://doi.org/10.1007/s10469-017-9452-7
6.Pinus A.G. Algebraically Equivalent Clones. Algebra Logic. 2017; 55(6):501-506. (In Eng.) DOI: https://doi.org/10.1007/s10469-017-9420-2
7.Behrisch M., Vargas-García E., Zhuk D. The Number of Clones Determined by Disjunctions of Unary Relations. Theory of Computing Systems. 2019; 63(6):1298-1313. (In Eng.) DOI: https://doi.org/10.1007/s00224-018-9905-y
8.Peryazev N.A., Sharankhaev I.K. On some Sufficient Condition for the Equality of Multi-clone and Super-clone. Journal of Siberian Federal University. Mathematics & Physics. 2018; 11(1):97-102. (In Eng.) DOI: https://doi.org/10.17516/1997-1397-2018-11-1-97-102
9.Badmaev S.A., Sharankhaev I.K. On the classes of partial functions generated by maximal partial ultraclones. Siberian Electronic Mathematical Reports. 2020; 17:32-46. (In Russ., abstract in Eng.) DOI: https://doi.org/10.33048/semi.2020.17.003
10.Badmaev S.A. A completeness criterion for sets of multifunctions in full partial ultraclone of rank 2. Siberian Electronic Mathematical Reports. 2018; 15:450-474. (In Russ., abstract in Eng.) DOI: https://doi.org/10.17377/semi.2018.15.040
11.Badmaev S.A. Classification of hyperfunctions of rank 2 with respect to membership in the maximal partial ultraclones. Set. Journal of Siberian Federal University. Mathematics & Physics. 2019; 12(5):645-652. (In Eng.) DOI: https://doi.org/10.17516/1997-1397-2019-12-5-645-652
12.Kazimirov A.S., Peryazev N.A. Algebras of unary multioperations. Proceedings of the International Conference on Mal’tsev Meeting. Novosibirsk; 2013. p. 156. Available at: https://elibrary.ru/item.asp?id=27230507 (accessed 26.01.2021). (In Russ.)
13.Peryazev N.A., Peryazeva Yu.V., Sharankhaev I.K. Minimal Algebras of Unary Multioperations. Journal of Siberian Federal University. Mathematics & Physics. 2016; 9(2):220-224. (In Eng.) DOI: https://doi.org/10.17516/1997-1397-2016-9-2-220-224
14.Malina A.V., Peryazev N.A. Sheffer’s multioperations in full algebra of unary multioperation of the rank 4. Proceedings of the Southwest State University. Series: Control, Computer Engineering, Information Science. Medical Instruments Engineering. 2016; (1):29-32. Available at: https://elibrary.ru/item.asp?id=25942201 (accessed 26.01.2021). (In Russ., abstract in Eng.)
15.Peryazev N.A., Sharankhaev I.K. Algebras of multioperations. In: A.G. Pinus, E.N. Poroshenko, S.V. Sudoplatov, E.I. Timoshenko (Eds.) Algebra and Model Theory 11. Collection of papers. NSTU Publ., Novosibirsk; 2017. p. 102-111. Available at: https://elibrary.ru/item.asp?id=34916824 (accessed 26.01.2021). (In Russ.)
16.Peryazev N.A. Algebras of unary multioperations of finite rank. In: S. S. Goncharov et al. (Eds.) Syntax and Semantics of Logical Systems. Collection of papers. ISU Publ., Irkutsk; 2019. p. 76-79. Available at: https://elibrary.ru/item.asp?id=41216139 (accessed 26.01.2021). (In Russ., abstract in Eng.)
17.Peryazev N.A.Finite Algebras of Multioperations. Proceedings of the International Conference on Algebra, Number Theory and Discrete Geometry: modern problems, applications and problems of history, dedicated to the 80th anniversary of the birth of Professor Michel Desa. TSPU of Leo Tolstoy, Tula; 2019. p. 51-54. Available at: https://elibrary.ru/item.asp?id=39552184 (accessed 26.01.2021). (In Russ., abstract in Eng.)
18.Peryazev N.A. Identities in Fixed Dimension Algebras of Multioperations. The Bulletin of Irkutsk State University. Series: Mathematics. 2019; 29:86-97. (In Russ., abstract in Eng.) DOI: https://doi.org/10.26516/1997-7670.2019.29.86
19.Panteleev V.I., Riabets L.V. Classification of Multioperations of Rank 2 by E-precomplete Sets. The Bulletin of Irkutsk State University. Series: Mathematics. 2020; 34:93-108. (In Eng.) DOI: https://doi.org/10.26516/1997-7670.2020.34.93
20.Panteleev V.I., Riabets L.V. The Completeness Criterion for Closure Operator with the Equality Predicate Branching on the Set of Multioperations on Two-Element Set. The Bulletin of Irkutsk State University. Series: Mathematics. 2019; 29:68-85. (In Eng.) DOI: https://doi.org/10.26516/1997-7670.2019.29.68
21.Kazimirov A.S. On Complexity of Standard Forms for Multifunctions. The Bulletin of Irkutsk State University. Series: Mathematics. 2017; 22:63-70. (In Eng.) DOI: https://doi.org/10.26516/1997-7670.2017.22.63
22.Peryazev N.A. Galois Theory for Finite Algebras of Operations and Multioperations of Rank 2. The Bulletin of Irkutsk State University. Series: Mathematics. 2019; 28:113-122. (In Russ., abstract in Eng.) DOI: https://doi.org/10.26516/1997-7670.2019.28.113
23.Kazda A., Opršal J., Valeriote M., Zhuk D. Deciding the Existence of Minority Terms. Canadian Mathematical Bulletin. 2020; 63(3):577-591. (In Eng.) DOI: https://doi.org/10.4153/S0008439519000651
24.Panteleyev V.I., Haltanova S.Yu. About some intervals in the lattic of clones of partial ultrafunctions. The Bulletin of Irkutsk State University. Series: Mathematics. 2010; 3(4):80-87. Available at: https://elibrary.ru/item.asp?id=15540117 (accessed 26.01.2021). (In Russ., abstract in Eng.)
25.Basheyeva A., Nurakunov A., Schwidefsky M., Zamojska-Dzienio A. Lattices of subclasses. III. Siberian Electronic Mathematical Reports. 2017; 14:252-263. (In Eng.) DOI: https://doi.org/10.17377/semi.2017.14.023
26.Kravchenko A.V. Complexity of Quasivariety Lattices for Varieties of Unary Algebras. Siberian Electronic Mathematical Reports. 2016; 13:388-394. (In Russ.) DOI: https://doi.org/10.17377/semi.2016.13.034
Опубликована
2021-04-15
Как цитировать
EREMENKO, Dmitriy Aleksandrovich. Разработка алгоритма построения решеток мультиопераций на основе неразложимых алгебр. Современные информационные технологии и ИТ-образование, [S.l.], v. 17, n. 1, p. 24-36, apr. 2021. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/674>. Дата доступа: 09 dec. 2022 doi: https://doi.org/10.25559/SITITO.17.202101.674.
Раздел
Теоретические вопросы информатики, прикладной математики, компьютерных наук