Полукубические множества и свободные частично коммутативные моноиды

ПОЛУКУБИЧЕСКИЕ МНОЖЕСТВА И СВОБОДНЫЕ ЧАСТИЧНО КОММУТАТИВНЫЕ МОНОИДЫ

                                                                                   г. Комсомольск-на-Амуре

                                                                                   ГОУВПО «КнАГТУ»

                                                                                   г. Комсомольск-на-Амуре

                                                                                  ФГОУВПО «АмГПГУ»

Работа посвящена построению функторов между категориями, связанными с моделированием параллельных вычислительных систем. Вычислительная система состоит из набора инструкций, которые можно моделировать как буквы некоторого алфавита. Вычислительным процессам соответствуют слова, состоящие из букв. Если инструкции могут выполняться одновременно, то соответствующие им буквы можно переставлять. Описанная математическая модель называется свободным частично коммутативным моноидом, и ей можно сопоставить автомат высшей размерности. Спрашивается, можно ли сопоставить автомату высшей размерности свободный частично коммутативный моноид, который был бы наиболее близок к этому автомату?

Попытки решить эту задачу предпринимали многие ученые. Но их решения оказались громоздкими. Мы предлагаем простое решение.  Мы вводим плоские гомоморфизмы между свободными частично коммутативными моноидами. Доказываем, что категория свободных частично коммутативных моноидов и плоских гомоморфизмов допускает прямые пределы. Строим пару сопряженных функторов между категориями свободных частично коммутативных моноидов и полукубических множеств. Поскольку автоматы высших размерностей определяются как полукубические множество, то построение этих сопряженных функторов является ответом на вопрос.  

§1. Свободные частично коммутативные моноиды

Определение 1. Пусть E - множество, I Í E´E – антирефлексивное симметричное отношение. Свободным частично коммутативным моноидом M(E,I) называется моноид, заданный с помощью множества образующих E, и  соотношений ab=ba , выполненных для всех пар (a,b)ÎI .

Пример 1. Пусть E={a,b}, I=Æ. Тогда M(E,I) – свободный моноид, порожденный элементами a и b. Его элементами являются слова, составленные из этих букв:

1 (пустое слово), a, b, aa, ab, ba, bb, aaa, … .

Этот пример можно обобщить. Если E – произвольное множество букв, а I=Æ, то M(E,I) будет моноидов слов, составленных из букв принадлежащих E. В частности, для E={a} получаем моноид N={1, a, a², a³, …}, который называется свободным циклическим.

Пусть E – множество, I  – антирефлексивное симметричное отношение на E. Два слова называются эквивалентными, если они получаются с помощью перестановок пар соседних элементов. Эти пары должны принадлежать I. Элементами M(E,I) являются классы эквивалентных элементов. Произведение классов равно классу произведения произвольных представителей этих классов. Если умножать  каждый элемент первого класса на каждый элемент второго класса, то получим все элементы произведения классов.

Пример 2. Пусть E={a,b}, I={(a,b), (b,a)}. Тогда M(E,I) – свободный коммутатив-ный моноид, порожденный элементами a и b. В данном случае его элементы – классы эквивалентных слов

{1}, {a}, {b}, {ab,ba}, {aa}, {bb}, {aab, aba, baa}, …

Легко видеть, что в данном примере моноид M(E,I) изоморфен декартовому произведению моноида N={1, a, a², a³, …}. Каждый элемент из M(E,I) содержит представитель вида a^pb^q для некоторых неотрицательных целых p, q. Изоморфизм осуществляется с помощью отображения, сопоставляющего паре (a^p, a^q)ÎN×N класс, содержащий слово a^pb^q.

§2. Категория свободных частично коммутативных моноидов

Определение 2. Пусть FPCM — категория, объектами которой являются свободные частично коммутативные моноиды M(E, I),  а морфизмы f : M(E, I) → M(, ) определя- ются как гомоморфизмы моноидов, переводящие элементы из E в элементы множества {1}. Такие гомоморфизмы  f : M(E, I) → M(, ) называются плоскими.

Пример 3. Рассмотрим  моноиды M({a,b}, I) и M({a}, Æ), где I={(a,b),(b,a)}.

Первый из них изоморфен NN, второй – N. Гомоморфизм, продолжающий отображение f(a)=a², f(b)=a не будет плоским. А гомоморфизм, определенный на образующих по фор-мулам f(a)=f(b)=a, будет плоским. Он будет морфизмом в категории FPCM.