Кубические гомологии моноидов трасс Хусаинов А.А.

2 Цель доклада Изложить решение проблемы, поставленной автором в работеИзложить решение проблемы, поставленной автором в работе Husainov A., ``On the homology of small categories and asynchronous transition systems``, Homology Homotopy Appl. 2004, 1 (6), (Open Problem 1) Представить новую теорию гомологий асинхронных системПредставить новую теорию гомологий асинхронных систем

3 Задачи Сравнение гомологий множеств, на которых действуют моноиды трасс, с кубическими гомологиями обобщенных торовСравнение гомологий множеств, на которых действуют моноиды трасс, с кубическими гомологиями обобщенных торов Разработка алгоритмов вычисления групп гомологий асинхронных систем, сетей Петри, языков трасс МазуркевичаРазработка алгоритмов вычисления групп гомологий асинхронных систем, сетей Петри, языков трасс Мазуркевича

4 Моноиды трасс Пусть E – множество, I E E – антирефлексивное, симметричное отношение (независимости) Свободным частично коммутативным моноидом (или моноидом трасс) M(E,I) называется фактор-моноид E * /( ), моноида слов E * по отношению эквивалентности, при котором uabv ubav, для всех (a,b) I, u E *, v E *

5 Примеры моноидов трасс E ={a,b}, I ={(a,b),(b,a)}, M(E,I) N 2 – свободный коммутативный моноид M(E,I) N 2 – свободный коммутативный моноид E ={a,b}, I =, M(E,I) {a,b} * – свободный моноид M(E,I) {a,b} * – свободный моноид

6 Интерпретация трасс Трасса w M(E,I) интерпретируется как последовательность действий a 1 a 2 … a n Переставляя пары независимых элементов, ее можно привести к нормальной форме Фоаты [b 1 b 2 …b p ] [b p+1 … b q ]… [b r+1 … b n ] (в скобках действия, выполняемые параллельно) (в скобках действия, выполняемые параллельно)

7 Пространство состояний Элементам a E соответствуют частичные отображения S S. Пространство состояний (M(E,I), S) состоит из множества S (состояний) с частичным действием моноида M(E,I) справа. Например

8 Аугментация пространства состояний Добавляя состояние ``зависания *, получим Трассы интерпретируются как вычислительные процессы, например aaba включает действия в состоянии *

9 Категория состояний Аугментированная категория состояний K (S): Объекты S { }. Морфизмы – тройки (s, w, s), s,s S { }, w M(E,I) Категориясостояний K(S) K (S) – полная под- категория с объектами S

10 Группы гомологий категории С – малая категория, F: С Ab - функтор Группы H n (C,F) = Ker d n / Im d n+1 называются группами гомологий C с коэффициентами в F

11 Вычисление групп гомологий Пусть k – поле, -комплекс векторных пространств Тогда H n =Ker d n / Im d n+1 = k dimC n -r(d n )-r(d n+1 ), где r(A) обозначает ранг матрицы A Предложение. Пусть A – матрица с целыми коэффициентами. Тогда существуют матрицы S, T, D, такие, что 1)A= T D S2) |det S|=|det T|=1 3) D – диагональная матрица где 1 | 2 | … | r Если вместо k – кольцо целых чисел, то группы гомологий вычисляются с помощью нормальной формы Смита H n =Ker d n / Im d n+1 = Z dimC n -r(d n )-r(d n+1 ) Z/ 1 Z … Z/ r Z, r=r(d n+1 )

12 Пример вычисления групп гомологий частично упорядоченного множества Здесь F= Z. Комплекс состоит из абелевых групп

13 Вычисление групп гомологий

14 Вычисление групп гомологий Нормальные формы состоят из единиц, отсюда

15 Гомологии категории как производные функтора копредела Предложение. Пусть colim C : Ab C Ab – функтор копредела, F: C Ab – объект из Ab C. 0 F P 0 P 1 … P n P n+1 … -проективная резольвента, С - комплекс 0 colim C P 0 colim C P 1 … … colim C P n colim C P n+1 … Тогда H n (C,F) H n (С ).

16 Две проблемы K(S),Z В работе автора в 2004 году был разработан алгоритм вычисления группы H 1 (K(S),Z) и поставлена Проблема 1. Построить алгоритм для вычисления целочисленных гомологий CE-сетей K(S),Z Нахождение алгоритма вычисления H n (K(S),Z) для категорий состояний будет решением этой проблемы. K (S),F Было доказано, что если моноид трасс M(E,I) не содержит троек попарно независимых образующих, то H n (K (S),F)=0 при n>2. Поставлена K (S),F Проблема 2. Пусть n>0 – максимальное число попарно независимых образующих. Доказать, что H k (K (S),F)=0 при k>n. В случае конечного E эта гипотеза подтверждена Л.Ю. Поляковой (Сиб. мат. журн. 48:6, 2007). В общем случае решена автором (Матем. сб. 199:12, 2008).

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

18 Геометрическая реализация Геометрической реализацией |X| полукубического множества называется топологическое пространство по наименьшему отношению эквивалентности ( ), для которого Пример.

19 Полукубическое множество пространства состояний Пусть S * = S { * }. Пространству состояний (M(E,I),S) сопоставим полукубическое множество Q n (E,I,S)= {(x,a 1,…, a n )| x S *, a i

20 Топологическое пространство промежуточных состояний Введем ``промежуточные состояния, как элементы топологического пространства, полученного из склеиванием звездочек, отрезков, соединяющих их, и единичных квадратов. Получим геометрическую реализацию |Q(E,I,S)| полукубического множества * * aa * s2s2 s3s3 a * a a * bb b bb bb a aa * b a

21 Обобщенные торы Обобщенным тором называется полукубическое множество T n (E,I)={(a 1,…, a n )| a i

22 Примеры обобщенных торов Граф независимостиГеометрическая реализация |T(E,I)| ba a b c Тор T 2 Поверхность вращения цифры 8 a bБукет окружностей ac b T 2 T 1

23 Гомологические системы Пусть X – полукубическое множество. Гомологическая система на X – семейство абелевых групп F(x),, и для которых коммутативна диаграмма

24 Группы гомологий полукубических множеств Определение. H n (X,F) вычисляются с помощью комплекса Пример. H 1 (X,Z[ ])=Z, H n (X,Z[ ])=0 при n 1.

25 Категория факторизаций Пусть C – малая категория. Объектами категории факторизаций Fact(C) служат морфизмы категории C, а морфизмами - коммутативные диаграммы: Пример. Рассмотрим M(E,I) как категорию с одним объектом. Тогда объекты Fact(M(E,I)) – элементы из M(E,I). Морфизмы – пары таких трасс (f,g), что g f=

26 Гомологии Лича как гомологии обобщенного тора Определение. Гомологии Лича моноида M с коэффициентами в функторе F: Fact(M) op Ab определяются как H n ((Fact(M)) op,F) Теорема. Пусть F: Fact(M(E,I)) op Ab – функтор. Тогда существует такая гомологическая система F на T(E,I), что H n (Fact(M(E,I)) op,F) H n (T(E,I), F)

27 Глобальная размерность моноида трасс Теорема. Для функторов F: Fact(M(E,I)) Ab и n 0 верно H n (Fact(M(E,I)),F) H n (T(E,I), F) Следствие. Пусть A – абелева категория с суммами, n – максимальное число попарно перестановочных элементов из E. Тогда в каждом из следующих случаев: 1)A имеет точные суммы (т.е. удовлетворяет AB4) 2)A имеет достаточно проективных объектов Гипотеза. Неравенство верно для абелевых с суммами

28 Глобальная размерность кольца многочленов от частично коммутирующих переменных Пример Пример. Пусть k – поле, x 1, x 2, x 3, x 4, x 5 – символы переменных, таких, что перестановочны тогда gl.dim k x 1,x 2,x 3,x 4,x 5 /(I) =2, где (I) =({x i x j -x j x i | (x i,x j ) I}).

29 Группы гомологий аугментированной категории состояний Теорема. H n (K * (T,F)) равны гомологиям Следствие. Если число попарно независимых событий n, тоH k (K * (T,F))=0 для всех k>n. Следствие. Если число попарно независимых событий n, то H k (K * (T,F))=0 для всех k>n. (Решение Проблемы 2)

30 Пример вычисления групп гомологий |S |=|{s 0, s 1, }|=3 |S E|=|{(s 0,a), (s 0,b), (s 1,a), (s 1,b), (,a), (,b)}|=6 | S T 2 (E,I) |=|{(s 0,a,b), (s 1,a, b), (,a,b)}|

31 Языки трасс Мазуркевича Для v, w M(E,I) положим v w, если ( u M(E,I)) vu = w. Пусть P(E,I)=(M(E,I), ) – частично упорядоченное множество Определение Определение. L M(E,I) называется префиксно-замкнутым, если v < w L v L. Пусть (M(E,I), L { }) – действие v w=vw, если vw L, и v w=, в других случаях.

32 Группы гомологий языка трасс Теорема Теорема. H n (K (L), Z) H n (P(E,I),Z[L]) Z p n Здесь p n – число n-клик графа независимости p 1 =5, p 2 = 4, p 3 =1

33 Группы гомологий частично упорядоченных множеств трасс Теорема. H n (P(E,I),Z[L]) n-1 (M(E,I)\L), при n 1. Следствие. H 1 (K (L), Z) – свободна Гипотеза. H 1 (K (S), Z) свободна для произвольного множества с частичным действием моноида трасс. Свойства групп гомологий ч.у. множества трасс 1)Если I состоит из всех (a,b), a b, то H n (P(E,I),Z[L])=0 для всех n>0 2)Если I=, то H n (P(E,I),Z[L])=0 для всех n>0 3)Для любых конечно-порожденных абелевых групп A 1, …, A k, где A 1 – свободна, существует такой M(E,I), что H n (P(E,I),Z[{1}]) A n, для всех 1 n k

34 Гомологии Бауэса-Виршинг Пусть X – правое M(E,I)-множество, K(X) – категория с объектами x X и морфизмами F: Fact(K(X)) op Ab – функтор, U: K(X) M(E,I) – функтор, забывающий начала и концы морфизмов Теорема Теорема. H n (Fact(K(X)) op,F) H n (Fact(M(E,I)) op,L(F)) Здесь L(F) – левое расширение Кана функтора F вдоль функтора Fact(K(X)) op Fact(M(E,I)) op, определенного функтором U.

35 Решение проблемы 1 Следствие Следствие. Пусть (M(E,I),S) – пространство состояний, K(S) – категория состояний. Группы H n (K(S), Z) изоморфны группам гомологий комплекса Было высказано как гипотеза в препринте в 2009.

36 Алгоритм вычисления групп гомологий категории состояний На примере C 0 =Z{s 0,s 1 }, C 1 =Z{(s 0,a), (s 0,b), (s 1,a)}, C 2 =Z{(s 0,a,b)} Получаем H 0 =Z 2-1 =Z, H 1 =Z = Z

37 Элементарные сети Петри Элементарные сети Петри CE-сеть состоит из блоков действий и условий, указывающих на состояние готовности данных. t1t1 t2t2 p1p1 p2p2 t1t1 t1t1 t2t2 p1p1 p2p2 t1t1 t2t2 p1p1 p2p2 t2t2 t3t3 t3t3 t3t3 p3p3 p4p4 p5p5 p3p3 p3p3 p4p4 p5p5 p4p4 p5p5

38 Группы гомологий CE-сетей Положим E={t 1, …, t n }. I={(t i,t j )| не имеющих общих данных} В примере, I={(t 1,t 3 ), (t 3,t 1 )} S={{p 1, p 2 },{p 4 },{p 1, p 5 }} Действие: {p 1, p 2 } t 1 ={p 4 } {p 1, p 2 } t 2 ={p 1, p 5 } Определение Определение. Группы гомологий CE-сети определяются как H n (K(S), Z). t1t1 t2t2 p1p1 p2p2 t3t3 p3p3 p4p4 p5p5

39 Вычисление групп гомологий CE-сетей Петри На примере конвейера Получаем H 0 =Z 8-7 =Z, H 1 =Z = Z t1t1 t2t2 t3t3 t4t4 (0,1,1)(0,1,0) (1,1,1) (0,0,0)(0,0,1) (1,0,1)(1,0,0) (1,1,0) t1t1 t1t1 t1t1 t1t1 t4t4 t4t4 t4t4 t4t4 t2t2 t2t2 t3t3 t3t3

40 Перспектива Определение групп гомологий Губо как групп гомологий с коэффициентами в гомологических системах Исследование связи гомологических и бисимиляционных инвариантов Исследование гомотопических копределов диаграмм над категориями состояний