2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Попарно неизоморфные полугруппы
Сообщение23.04.2011, 12:34 
Добрый день! Требуется написать программу для генерации попарно неизоморфных полугрупп заданного порядка. Полугруппа задается в виде матрицы. Сел разбираться, понял, что не понимаю как это можно сделать. Нашел что-то связанное с таблицами Кэли, больше ничего. Если перебирать все возможные варианты таблиц, то их получится n^n^2, что нереально вычислить и уж тем более обработать.
Как их вообще генерировать? Как реализовать проверку двух матриц на изоморфность?
Заранее спасибо!

 
 
 
 Re: Попарно неизоморфные полугруппы
Сообщение23.04.2011, 17:27 
Честно говоря, толком, наверное ничего не посоветую, но:
1. Любая группа является полугруппой, поэтому можете погуглить способы задания конечной группы и проверки изоморфизма заданных конечных групп. Возможно, какой-либо способ проверки переносится и на полугруппы.
2. Книжка Ляпин Полугруппы - можете нагуглить или скачать (или у меня есть) - там можно просто с предметом ознакомиться (методов проверки на изоморфизм явно там нету).
3. При задании полугруппы таблицей Кэли достаточно проверить ассоциативность, о чем есть тема: topic43246.html (там же есть ссылка на Вики на проверку).
И вообще, сколько существует полугрупп порядка $n$? По-моему, очень много, что довольно затрудняет задачу...

 
 
 
 Re: Попарно неизоморфные полугруппы
Сообщение07.05.2011, 00:54 
Не знаю, кто Вам дал такую задачу, но она нелегкая, мягко говоря.
Вот известные результаты о числе полугрупп:

Порядок ....... Число неизоморфных
полугруппы ....... полугрупп

1 ....... 1
2 ....... 4
3 ....... 18
4 ....... 126
5 ....... 1.160
6 ....... 15.973
7 ....... 836.021
8 ....... 1.843.120.128

Последний результат является содержанием статьи

S. Satoh, K. Yama, M. Tokizawa. Semigroups of order 8.
"Semigroup Forum", 49(1994), 7-29.

В ней Вы сможете найти полезную информацию.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group