WWW.KNIGA.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Книги, пособия, учебники, издания, публикации

 

Модел. и анализ информ. систем. Т. 20, № 2 (2013) 92–103

c Хусаинов А.А., Бушмелева Е.С., Тришина Т.А., 2012

УДК 519.7+515.14

Группы гомологий сети Петри конвейера

1

Хусаинов А.А., Бушмелева Е.С., Тришина Т.А.

Комсомольский-на-Амуре государственный технический университет

681013, Комсомольск-на-Амуре, просп. Ленина, 27.

e-mail: husainov51@yandex.ru получена 12 декабря 2012 Ключевые слова: моноид трасс, асинхронная система переходов, элементарная сеть Петри, конвейер, полукубическое множество, гомологии малых категорий.

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

Если рассматривать работу функциональных устройств как непрерывную, то можно прийти к некоторому топологическому пространству “промежуточных” состояний. В работе вычислены группы гомологий этого топологического пространства. С помощью индукции по n, с применением аддиционной последовательности для групп гомологий полукубических множеств, доказано, что в размерностях 0 и 1 целочисленные группы гомологий этих сетей равны группе целых чисел, а в остальных размерностях равны нулю. Исследуются направленные группы гомологий. Установлена связь этих групп с тупиками и рассылками. Эта связь помогает доказать, что все направленные группы гомологий элементарной сети Петри конвейера равны нулю.

Введение Группы гомологий элементарных сетей Петри были введены в работе [1]. Они предназначены для топологического анализа параллельных процессов и систем, описываемых этими сетями. Они также тесно связаны с гомологиями многомерных автоматов, изученных в работах [2]–[3] и примененных в [4] для решения проблем теории направленной гомотопии. Наша работа посвящена вычислению групп гомологий элементарной сети Петри конвейера Pn, состоящей из n переходов (событий) и n 1 мест (условий). В [1] были вычислены группы гомологий сети Петри конвейера P3. В работе [5] построен алгоритм для вычисления всех групп гомологий элементарной сети Петри. Приведен пример вычисления групп гомологий элементарной сети Петри конвейера P4 :

/ / t2 / / t3 / / t t1 p1 p2 p Работа выполнена в рамках программы стратегического развития государственных образовательных учреждений высшего профессионального образования, №2011-ПР-054.

Группы гомологий сети Петри конвейера С помощью описанного в [6] программного обеспечения мы вычислили группы гомологий сети Pn, при n = 2, 3, 4, 5. В этих случаях группы гомологий конвейера равны H0 (Pn ) = H1 (Pn ) = Z, и Hk (Pn ) = 0 при k 2. Возникло естественное предположение о том, что это верно для всех n 2. В данной работе мы доказываем это предположение (теорема 1). Кроме того, вторым соавтором данной работы было разработано программное обеспечение для вычисления направленных групп гомологий пространств состояний. Вычисления показали, что направленные группы элементарных сетей Петри Pn при n = 2, 3, 4, 5 равны нулю во всех размерностях.

В данной работе мы доказываем, что это верно для всех n 2 (теорема 2).

1. Предварительные сведения Через Z будем обозначать группу целых чисел. Для произвольной категории C обозначим через Ob C класс всех ее объектов, Mor C – класс всех морфизмов, C op – дуальную категорию. Для любых A, B Ob C множество всех морфизмов A B в категории C обозначим через C (A, B).

Частичные отображения. Для произвольных множеств S и T частичным отобT называется отношение f S T, обладающее следующим ражением f : S свойством:

(s, t1 ) f & (s, t2 ) f t1 = t2.

Обозначим через P Set категорию множеств и частичных отображений.

Для произвольного множества S обозначим S = S {}. Пусть Set – категория, объектами которой являются множества, каждое из которых равно S для некоторого множества S. Для любых ее объектов S и T множество морфизмов Set (S, T ) состоит из отображений f : S T, удовлетворяющих равенству f () =. Легко видеть, что функтор : P Set Set, определенный на объектах как (S) = S, а на морфизмах f (x), если f (x) определен, (f )(x) =, если f (x) не определен или x =, будет осуществлять изоморфизм категорий P Set и Set. Этот изоморфизм позволяет нам отождествлять категорию P Set с категорией Set и рассматривать частичные отображения как тотальные, сохраняющую точку.

Частичное действие моноида. Пусть M – моноид. Операцию умножения в нем временно обозначим через ·M. Всякий моноид M мы будем рассматривать как малую категорию, имеющую единственный объект ptM. Множество морфизмов этой категории совпадает с множеством M. В частности определен дуальный моноид M op. Произведение элементов µ1, µ2 M в этом моноиде определяется по формуле µ1 ·M op µ2 = µ2 ·M µ1. Частичным действием моноида M справа на множестве S называется произвольный гомоморфизм M op P Set(S, S). В соответствии с данным выше соглашением, частичное действие будем рассматривать как гомоморфизм M op Set (S, S ). Отсюда вытекает, что его можно рассматривать как функтор M op Set. Ниже повсюду вместо µ1 ·M µ2 будем писать просто µ1 µ2, оставляя символ ’·’ для обозначения действия моноида.

Моделирование и анализ информационных систем Т. 20, № 2 (2013) Моноиды трасс и пространства состояний. Пусть E – множество, I E E называется отношением независимости на E, если для всех a E верно (a, a) / I, и для каждой пары (a, b) I имеет место (b, a) I. Моноид, порожденный множеством E и заданный с помощью соотношений ab = ba, для всех (a, b) I, называется свободным частично коммутативным моноидом или моноидом трасс и обозначается через M (E, I). Он будет равен фактор-моноиду E / моноида слов по наименьшему отношению конгруэнтности, содержащему пары (ab, ba) для всех пар (a, b) I. Пространством состояний называется пара (S, M (E, I)), где M (E, I) – моноид трасс, действующий частично на некотором множестве S.

Пространство состояний элементарной сети Петри. Элементарной сетью Петри называется пятерка (P, E, pre, post, s0 ), состоящая из конечных множеств P и E, отображений pre : E {0, 1}P, post : E {0, 1}P и подмножества s0 E.

Здесь {0, 1}P обозначает множество всех подмножеств s P. В работе [7] элементарные сети Петри называются просто сетями Петри. Элементы p P называются местами, а a E – событиями.

Для произвольной элементарной сети Петри N = (P, E, pre, post, s0 ) определяется моноид трасс M (E, I), порожденный множеством E и отношением независимости Пусть a E. Для всякого подмножества s P, обладающего свойствами обозначим s · a = (s \ pre(a)) post(a). Это определяет для каждого a E частичное отображение s s · a, из множества {0, 1}P в {0, 1}P. Здесь подмножества s P рассматриваются как их характеристические функции.

Согласно [7, Prop. 42], полученное частичное отображение будет равно отношению перехода из [7]–[8], определенному как множество таких троек (s, a, s ), что С помощью индукции по длине трассы µ = a1 a2 · · · an, по формуле s · a1 a2 · · · an = (s · a1 a2 · · · an1 ) · an, это действие определяет частичное действие моноида M (E, I) справа на {0, 1}P. Полученное пространство состояний ({0, 1}P, M (E, I)) будем называть пространством состояний элементарной сети Петри.

Если рассматривать вместо {0, 1}P множество достижимых состояний, то это частичное действие будет определять пространство достижимых состояний элементарной сети.

2. Гомологии полукубических множеств и пространств состояний Напомним определение полукубического множества и его групп гомологий [9]. Опишем полукубическое множество, соответствующее категории состояний и имеющее такие же группы гомологий.

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

Полукубическим множеством X = (Xn, in, ) называется последовательность множеств Xn, n 0, и семейство отображений in, : Xn Xn1, определенных при 1 i n, {0, 1}, и делающих диаграммы коммутативными для всех n 2, 1 i j n.

Морфизмом полукубических множеств f : X X называется последовательность отображений fn : Xn Xn, n 0, для которых диаграммы коммутативны для всех 1 i множеств состоит из вложений Xn Xn, для всех n 0, то X называется полукубическим подмножеством в X.

Гомологии полукубических множеств. Пусть X = (Xn, in, ) – полукубическое множество. Рассмотрим комплекс состоящий из свободных абелевых групп LXn, n 0, порожденных множествами Xn, и дифференциалов, действующих на элементах базиса по формуле Группы гомологий этого комплекса называются группами гомологий Hn (X) полукубического множества X, n 0.

Предложение 1. Пусть X = X1 X2 – объединение полукубических подмножеств. Тогда существует длинная точная последовательность групп Доказательство. Рассмотрим комплекс Cn (X) = LXn, с дифференциалами (1)i (in,1 () in,0 ()). Рассмотрим точную последовательность комdn () = плексов, связанную с гомоморфизмом 1 2 1 2, Моделирование и анализ информационных систем Т. 20, № 2 (2013) где n () = для каждого (X1 X2 )n. Длинная точная последовательность, соответствующая этой короткой точной последовательности, будет искомой.

Гомологии категории состояний и полукубических множеств.

Пусть (S, M (E, I)) – пространство состояний. Рассмотрим произвольное отношение линейного порядка на E. Оно определяет полукубическое множество с граничными операторами при 1 i n, {0, 1}. Здесь a0 = 1, и a1 = ai.

Категория состояний K(S) пространства состояний (S, M (E, I)) имеет объектами элементы s S. Ее морфизмами s t служат такие тройки элементов s, t S и µ M (E, I), что s · µ = t. Композиция задана формулой (t u) (s t) = (s u).

Для произвольной элементарной сети Петри N группы гомологий Hn ( N ) определяются как группы гомологий Hn (K(S)) (нерва) ее категории достижимых состояний. Согласно [5, Corollary 4], Hn (K(S)) Hn (Q(S, E, I)), для всех n 0. Поэтому группы гомологий элементарной сети Петри Hn ( N ) будут изоморфны группам гомологий полукубического множества, соответствующего ее пространству достижимых состояний.

3. Категория состояний сети Петри конвейера и ее группы гомологий В этой части мы будем исследовать категорию состояний элементарной сети Петри конвейера и вычислим целочисленные группы гомологий этой категории.

Категория состояний элементарной сети Петри конвейера. Мы рассматриваем сеть Петри конвейера Pn :

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

Пусть N n – сеть Петри Обозначим через Cn ее категорию состояний. Всякое частично упорядоченное множество можно рассматривать как малую категорию C, для любых объектов которой x, y Ob C множество C (x, y) содержит не более одного элемента, а одновременное выполнение соотношений C (x, y) = и C (y, x) = невозможно в случае x = y.

Состоянием элементарной сети Петри N n будет произвольная функция f : {p1, p2, · · ·, pn1 } {0, 1}. Отсюда следует, что состояние может быть задано последовательностью значений этой функции 1 2 · · · n1, где i = f (pi ) при n 1. Пусть S1 – множество состояний, начинающихся с 1 = 1, и S – множество состояний, начинающихся с 1 = 0. Множество всех состояний будет равно S = S1 S0. В общем случае элементы из S1 и S0 соединены переходами Например, при n = 4, S1 и S0 будут линейно упорядоченными множествами, соответствующими столбцам диаграммы:

Переходы между S1 и S0 показаны пунктирными стрелками.

Для любого состояния x = 1 · · · n1 введем число |x| = 1 · 2n2 + 2 · 2n3 + · · · + n1 · 20. Например, |11 · · · 1| = 2n1 1 и |00 · · · 0| = 0. Если существует переход x y, то |x| |y| Лемма 1. Категория Cn является частично упорядоченным множеством, имеющим наибольший и наименьший элементы.

Доказательство. С помощью индукции будем доказывать, что Cn – частично упорядоченное множество с наименьшим элементом 11 · · · 1 и наибольшим элементом 00 · · · 0. Пусть это доказано для n 1. Тогда Cn1 – частично упорядоченное множество с наименьшим и наибольшим элементами. Легко видеть, что полные подкатегории категории Cn, с множествами объектов S1 и S0 будут изоморфны категории Cn1. Значит, они будут частично упорядоченными множествами. Будем обозначать эти частично упорядоченные множества через S1 и S0. В S1 наименьший элемент согласно предположению индукции равен 11 · · · 1, а наибольший – 10 · · · 0.

В S0 наименьший элемент равен 01 · · · 1, а наибольший – 00 · · · 0.

Пусть x · µ = y, x S1, y S0. Тогда µ содержит букву t2. Поэтому существуют такие µ1 и µ2, что µ = µ1 t2 µ2, причем µ1 не содержит t2. Далее будем переставлять с t2 буквы из µ1, до тех пор, пока не встретим t3. Для некоторых µ1 и µ2 получим разложение µ = µ1 t3 t2 µ2.

Следующее ниже действие будем выполнять до тех пор, пока не получим разложение вида µ = tk · · · t2 µ.

Предположим, что µ = µ1 ttk1 · · · t2, для некоторых k 3 и t E. Опишем действие, выполняемое нами в каждом из возможных случаев:

(i) t = tk увеличиваем k на 1, (ii) t = ti, для некоторого i k, переставляем t с tk1, tk2, · · ·, t2.

Моделирование и анализ информационных систем Т. 20, № 2 (2013) При i k 1 разложение вида µ = µ1 ti tk1 · · · t2 невозможно, ибо x · tk1 · · · t тогда и только тогда определено, когда x = 11 · · · 10k · · · n1. Такой элемент x итерация описанного действия приведет к разложению µ = tk · · · t2 µ.

Теперь будем доказывать, что x · µ = x · = y S влечет µ =, откуда будет следовать, что Cn – предупорядоченное множество.

Если x · µ = x · = y S0 и y S0, то µ =, ибо S0 – частично упорядоченное множество. Аналогичное верно в случае x·µ = x· = y S1 и y S1. Не существует Рассмотрим теперь случай x·µ = x· = y S0, x S1. В этом случае существуют разложения µ = tk · · · t2 µ и = tm · · · t2. Поскольку x · tk tk1 · · · t2 µ S0, то x = 11 · · · 10k+1 · · · n1, при некоторых k+1, · · ·, n1 {0, 1}. Отсюда m = k.

Получаем равенство Поскольку x · tk · · · t2 S0 и S0 – частично упорядоченное множество, то из этого равенства следует µ =. Следовательно, µ = и Cn – предупорядоченное множество. Если для некоторых x = 1 · · · n1, y = 1 · · · n1 существует такое µ = 1, что x · µ = y, то |x| |y|. Поэтому из x · µ = y и y · = x будет следовать µ = = 1. Значит, отношение предпорядка будет антисимметричным, а Cn будет частично упорядоченным множеством.

Группы гомологий конвейера. Пусть Pn – элементарная сеть конвейера. Удаляя событие t1, мы получили сеть N n. Удаляя из Pn событие t2, получим следующую элементарную сеть:

Обозначим ее через N n.

Предложение 2. Полукубическое множество Q(Pn ) равно объединению полукубических подмножеств Q( N n ) Q( N n ). Пересечение Q( N n ) Q( N n ) будет полукубическим множеством, имеющим две компоненты связности, каждая из которых изоморфна Q( N n1 ).

Доказательство. Имеет место Q0 (Pn ) = Q0 ( N n ) Q0 ( N n ), ибо все эти множества равны S = {0, 1}n1. Если k 1, то поскольку t1 и t2 зависимы, то они не могут принадлежать набору попарно независимых событий (e1, · · ·, em ). Значит, для всякого (s, e1, · · ·, em ) Qm (Pn ) будет иметь место t1 {e1, · · ·, em } / либо t2 {e1, · · ·, em }, откуда (s, e1, · · ·, em ) Qm ( N n ) Qm ( N n ). Поскольку из вложения перестановочны с граничными операторами. Стало быть, Q(Pn ) равно объединению своих кубических подмножеств Q( N n ) и Q( N n ).

Теорема 1. H0 (Pn ) = H1 (Pn ) = Z, и Hk (Pn ) = 0 при k 1.

Доказательство. Согласно предложению 2, Q(Pn ) = Q( N n ) Q( N n ). Применим предложение 1. По лемме 1 категория состояний сети N n обладает инициальным и терминальным объектом. Пусть I = {0, 1} – частично упорядоченное множество, состоящее из элементов 0 и 1, с обычным отношением порядка 0 1.

Легко видеть, что категория состояний сети N n будет изоморфна произведению I Cn2. Поэтому она тоже обладает инициальным и терминальным объектами.

Отсюда вытекают изоморфизмы Hk (Q( N n )) = Hk (Q( N n )) = 0, при k 0. Точная последовательность предложения 1 приводит к изоморфизмам Hk (Q(Pn )) = Q( N n1 ) Q( N n1 ). Получаем Hk (Q(Pn )) Hk1 (Q( N n1 )) Hk1 (Q( N n1 )) = при k 2. Следовательно, Hk (Pn ) = 0 при k 2. Из предложения 1 получаем также точную последовательность Группы H0 свободно порождены компонентами связности полукубических множеств.

Гомоморфизм индуцирован цепным гомоморфизмом определенным на (Q( N n )Q( N n ))k по формуле k () =. Отсюда вытекает, что H0 () действует на классах гомологий по формуле H0 ()(cls()) = cls()cls().

Поскольку эти классы гомологий равны компонентам связности полукубических множеств, то H0 () будет гомоморфизмом Z Z Z Z, заданным матрицей. Но H1 (Pn ) изоморфен ядру гомоморфизма H0 (), а H0 (Pn ) – коядру. Отсюда, например, с помощью приведения этой матрицы к нормальной форме Смита, получаем H0 (Pn ) = H1 (Pn ) = Z.

4. Направленные гомологии Приведем вспомогательные сведения по группам гомологий Губо полукубических множеств. Изучим свойства направленных групп гомологий категории состояний и их интерпретацию в размерности 0. Вычислим направленные группы гомологий сети Петри конвейера.

Группы гомологий Губо. Пусть X = (Xn, in, ) – полукубическое множество. Для каждого {0, 1} рассмотрим цепной комплекс абелевых групп Cn (X) = L(Xn ) с дифференциалами где d () = Группы гомологий Hn (X) этого комплекса называются группами гомологий Губо полукубического множества X. Они были изучены в работе [2].

Группы Hn (X) называются инициальными, а Hn (X) – финальными группами гомологий Губо.

Моделирование и анализ информационных систем Т. 20, № 2 (2013) Предложение 3. Пусть X = X1 X2 – объединение полукубических подмножеств X1 X и X2 X. Тогда для каждого {0, 1} существует длинная точная последовательность Доказательство дословно повторяет доказательство предложения 1.

Направленные группы гомологий категории состояний. Группами гомологий малой категории C с коэффициентами в функторе F : C Ab называются значения limC F левых производных функторов функтора копредела limC : AbC Ab на F.

Пусть (S, M (E, I)) – пространство состояний, K(S) – его категория состояний.

Рассмотрим функторы 0 Z : K(S) Ab и 1 Z : K(S)op Ab, принимающие на объектах постоянные значения 0 Z(s) = 1 Z(s) = Z. А на морфизмах определенные по формулам Определение 1. Направленные группы гомологий пространства состояний определяются по формулам Hn (S, M (E, I)) =def limK(S) 0 Z, Hn (S, M (E, I)) =def limK(S) 1 Z.

Для произвольной элементарной сети Петри N ее группы гомологий Hn ( N ) определяются как группы гомологий ее пространства состояний.

Предложение 4. Для элементарной сети Петри N n, полученнной с помощью удаления перехода t1 из сети Петри конвейера Pn, группы гомологий равны Доказательство. Согласно лемме 1, категория Cn состояний сети Петри N n имеет инициальный и терминальный объекты. Если малая категория имеет терминальный объект, то копредел функтора по этой категории равен значению этого функтора на терминальном объекте. Отсюда Hk ( N n ) = limk Z = 0 при k 0 и Согласно [5, Corollary 5], для произвольного отношения линейного порядка на E имеют место изоморфизмы Отсюда получаем следующую интерпретацию направленных гомологий пространства состояний в размерности 0. Состояние s называется тупиком, если не существует a E, для которых s · a S. Оно называется рассылкой, если не существует таких пар s S и a E, что s · a = s. В категории состояний тупиком будет объект, из которого не выходят морфизмы (кроме тождественного), а в рассылку нет входящих в нее морфизмов (кроме тождественного).

Предложение 5. Группа H0 (S, M (E, I)) изоморфна свободной абелевой группе порожденной тупиками, а H0 (S, M (E, I)) – рассылками.

Доказательство. Из [5, Corollary 5] следует, что H0 (S, M (E, I)) будет изоморфно коядру гомоморфизма d0 : LQ1 (S, E, I) LQ0 (S, E, I), действующего как d0 (s, a) = s. Коядро порождено множеством, полученным отождествлением с нулем элементов s S, для которых существуют такие a E, что s · a S. Из множества S удаляются не тупики, а оставшееся множество порождает коядро. Аналогично доказывается для H0 (S, M (E, I)) – из S удаляются элементы, равные s · a, для некоторых s S и a E. Остаются рассылки, порождающие H0 (S, M (E, I)).

Пример 1. Категория состояний элементарной сети Петри конвейера не имеет ни рассылок, ни тупиков, откуда H0 (Pn ) = H0 (Pn ) = 0.

Направленные группы гомологий конвейера. Согласно приведенному выше примеру, группы H0 (Pn ) и H0 (Pn ) равны нулю. Следующее утверждение показывает, что Hk (Pn ) и Hk (Pn ) равны 0 для всех k 0.

Доказательство. Выше мы установили, что полукубическое множество Q(Pn ) равно объединению полукубических множеств Q( N n ) и Q( N n ). Категории состояний сетей N n и N n имеют наибольшие и наименьшие элементы. Значит, Hk ( N n ) = Q( N n ) Q( N n1 ) Q( N n1 ). Отсюда следует, что фрагмент точной последовательности предложения приводит к равенствам Hk (Q(Pn )) = 0 при k 2. Кроме того, имеет место точная последовательность Согласно примеру 1 и изоморфизмам (1) H0 (Q(Pn )) = 0. Получаем эпиморфизм Z Z Z Z. Но Z Z – проективный объект категории абелевых групп.

Отсюда следует существование гомоморфизма такого, что H0 () = 1 Z Z. Значит, определитель матрицы H0 () обратим, откуда следует, что ядро гомоморфизма H0 () равно нулю. Следовательно, H1 (Q(Pn )) = 0. Мы доказали, что Hk (Q(Pn )) = для всех k 0. Из изоморфизмов (1) получаем Hk (Pn ) Hk (Q(Pn )), откуда вытекает утверждение теоремы.

Список литературы 1. Husainov A. A. On the homology of small categories and asynchronous transition systems // Homology Homotopy Appl. 2004. V. 6, №1. P. 439–471. http://www.rmi.acnet.ge/hha Моделирование и анализ информационных систем Т. 20, № 2 (2013) Goubault E. The Geometry of Concurrency: Thesis Doct. Phylosophy (Mathematics).

Ecole Normale Suprieure, 1995.

3. Gaucher P. About the globular homology of higher dimensional automata // Topol. Geom.

Dier. 2002. V. 43, №2. P. 107–156.

4. Goubault E., Haucourt E., Krishnan S. Covering space theory for directed topology // Theory Appl. Categ. 2009. V. 22, №9. P. 252–268.

5. Husainov A.A. The Homology of Partial Monoid Actions and Petri Nets // Appl. Categor.

Struct. 2012. DOI: 10.1007/s10485–012–9280– Хусаинов А.А., Бушмелева Е.С. Гомологии асинхронных систем // Актуальные проблемы математики, физики, информатики в вузе и школе: материалы Международной научно-практической конференции 23 марта 2012 г. Комсомольск-на-Амуре.

Комсомольск-на-Амуре: Изд-во АмГПГУ, 2012. С. 24–31 (Husainov A.A., Bushmeleva E.S. Gomologii asinhronnyh sistem // Aktualnye problemy matematiki, ziki, informatiki v vuze i shkole: materialy Mezhdunarodnoj nauchno-prakticheskoj konferencii 23 marta 2012, Komsomolsk-na-Amure. Komsomolsk-na-Amure: Izd-vo AmGPGU, 2012. S. 24– [in Russian]).

Winskel G., Nielsen M. Models for Concurrency. Handbook of Logic in Computer Science.

Vol. IV / ed. Abramsky, Gabbay and Maibaum. Oxford University Press, 1995. P. 1–148.

8. Nielsen M., Winskel G. Petri nets and bisimulation // Theoretical Computer Science.

1996. V. 153, №1–2. P. 211–244.

9. Хусаинов А. А. О группах гомологий полукубических множеств // Сиб. мат. журн.

2008. Т. 49, № 1. С. 224–237 (English transl.: Khusainov A. A. Homology groups of semicubical sets // Sib. Math. J. 2008. V. 49, No 1. P. 593–604).

Komsomolsk-on-Amur State Technical University, Lenina prosp., 27, Komsomolsk-on-Amur, 681013, Russia Keywords: trace monoid, asynchronous transition system, elementary Petri net, pipeline, semicubical set, homology of small categories.

Petri net is said to be elementary if every place can contain no more than one token. In this paper, it is studied topological properties of the elementary Petri net for a pipeline consisting of n functional devices. If the work of the functional devices is considered continuous, we can come to some topological space of “intermediate” states. In the paper, it is calculated the homology groups of this topological space. By induction on n, using the Addition Sequence for homology groups of semicubical sets, it is proved that in dimension 0 and 1 the integer homology groups of these nets are equal to the group of integers, and in the remaining dimensions are zero. Directed homology groups are studied. A connection of these groups with deadlocks and newsletters is found. This helps to prove that all directed homology groups of the pipeline elementary Petri nets are zeroth.

ФГБОУ ВПО “Комсомольский-на-Амуре государственный технический университет”, профессор, доктор физико-математических наук;

ФГБОУ ВПО “Комсомольский-на-Амуре государственный технический ФГБОУ ВПО “Комсомольский-на-Амуре государственный технический

 


Похожие работы:

«Руководство пользователя Конфигурация сети EtherNet/IP Каталожные номера 1756-ENBT, 1756-EN2F, 1756-EN2T, 1756-EN2TR, 1756-EN2TXT, 1756-EN3TR, 1756-EN2TSC, 1756-EN2TRXT, 1768-ENBT, 1769-L23E-QB1B, 1769-L23E-QBFC1B, 1769-L32E, 1769-L35E, 1769-AENTR, 1783-ETAP, 1783-ETAP1F, 1783-ETAP2F, 1794-AENT, 20-COMM-E, 22-COMM-E, 1734-AENT, 1734-AENTR Важная информация для пользователя Перед тем как устанавливать, настраивать, эксплуатировать или обслуживать данное оборудование, прочитайте этот документ и...»

«СТАНДАРТ ПРЕДПРИЯТИЯ Образовательный стандарт высшего профессионального образования АлтГТУ. ОБРАЗОВАТЕЛЬНЫЙ СТАНДАРТ СПЕЦИАЛЬНОСТИ 090104 (075400) КОМПЛЕКСНАЯ ЗАЩИТА ОБЪЕКТОВ ИНФОРМАТИЗАЦИИ Алтайский государственный технический университет им. И.И. Ползунова 2004 СТП 075400-04 ПРЕДИСЛОВИЕ 1) РАЗРАБОТАН кафедрой Защита информационных ресурсов и систем связи наименование кафедры, разработавшей стандарт 2) В стандарте использованы следующие нормативные документы: -письмо Минобразования России от...»

«КАТАЛОГ № 2006 Каталог оборудования для технического обслуживания Наиболее эффективное оборудование и инстру менты для обслуживания землеройных машин и автомобилей, рекомендованное с учётом нашего всемирного технического опыта. MARUMA ВВЕДЕНИЕ Каталог компании Марума № 2000 представляет собой единственный в мире каталог, в котором содержится всё необходимое оборудование и инструменты для использования при об служивании как землеройных машин, так и автомобилей. Этот полный список...»

«1 Купцова А.К., преподаватель кафедры лексикографии и теории перевода МГУ им. Ломоносова М.В. Стерлигова А.Н., доцент кафедры логистики ГУ-ВШЭ, к.э.н., доцент Анализ процесса стандартизации терминологии логистики за рубежом 1. Участники процесса стандартизации терминологии логистики за рубежом Стандартизацией терминологии логистики за рубежом в настоящее время занимается ряд иностранных организаций, который можно разделить на две части: 1) профессиональные логистические организации, 2)...»

«Владислав Юрьевич Панченко, доцент кафедры теории государства и права Сибирского федерального университета, кандидат юридических наук 660075 г. Красноярск, ул. Маерчака, д.6, а.2-24 т. сот. 8-908-221-22-95 т. раб. 8 (391) 206-23-55 panchenkovlad@mail Илья Александрович Шевченко, доцент кафедры уголовного процесса Сибирского федерального университета, кандидат юридических наук 660075 г. Красноярск, ул. Маерчака, д.6, а.2- т. раб. 8 (391) 206-23- Ilya_shev@rambler.ru Профессиональная подготовка...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ ГОРОДА МОСКВЫ МОСКОВСКИЙ ГОРОДСКОЙ ДВОРЕЦ ДЕТСКОГО (ЮНОШЕСКОГО) ТВОРЧЕСТВА ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ) ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ УЧРЕЖДЕНИЕ ГОСУДАРСТВЕННЫЙ НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ ИНСТИТУТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И ТЕЛЕКОММУНИКАЦИЙ “ИНФОРМИКА” АВТОНОМНАЯ НЕКОММЕРЧЕСКАЯ...»

«Н ЦЕРЕТЕЛЛИ РУССКАЯ КРЕСТЬЯНСКАЯ ИГРУШКА ACADEMIA 1933 Супер - обложка, переплет, форзац, титульный лист и заставки В. А. Милашевского МАЛЬЧИК НА ПЕТУХЕ И ЛЕБЕДЬ. П а п ь е - м а ш е. Сергиев посад. (Государственный музей игрушки. Загорск). GARCON SUR UN COQ ET UN CYGNE. Papier-mache. Serghiew Possad. (Musee d'Eiat des jouets. Sagorsk); ОТ ИЗДАТЕЛЬСТВА Литература об игрушке, как искусстве, насчитывает не один десяток книг. Многие из них представляют собой итог серьезной, иногда долголетней...»

«МНТЦ Международный научно-технический центр Проект # 2097 РАДИНФО РАЗРАБОТКА КОМПЛЕКСНОЙ ИНФОРМАЦИОННОЙ СИСТЕМЫ, ВКЛЮЧАЮЩЕЙ БАЗУ МЕТА-ДАННЫХ И РЕГИОНАЛЬНЫЕ РАДИОЭКОЛОГИЧЕСКИЕ КАДАСТРЫ ДЛЯ ОЦЕНКИ РАДИАЦИОННОГО ВОЗДЕЙСТВИЯ НА ОКРУЖАЮЩУЮ СРЕДУ И НАСЕЛЕНИЕ Аналитическое исследование Северо-запада России и Красноярского региона ТЕХНИЧЕСКИЙ ОТЧЕТ за третий квартал (01 февраля 2003 г – 30 апреля 2003 г) Научный соруководитель проекта Н.П. Лаверов Научный соруководитель проекта В.А.Лебедев Руководитель...»

«ЕКОНОМІКА І ФІНАНСИ 251 УДК 336.717+339.722 Е.В. Чайкина, ст. преподаватель Севастопольский национальный технический университет ул. Университетская 33, г. Севастополь, 99011, Украина E-mail: finance09@mai1.ru ОСОБЕННОСТИ РЫНКА ДРАГОЦЕННЫХ МЕТАЛЛОВ УКРАИНЫ Рассмотрены особенности украинского рынка драгоценных металлов, его структура и функционирование. Ключевые слова: золото, серебро, платина, рынок драгоценных металлов. Постановка проблемы. Финансовая нестабильность мировой валютной системы...»

«База нормативной документации: www.complexdoc.ru СИСТЕМА НОРМАТИВНЫХ ДОКУМЕНТОВ В СТРОИТЕЛЬСТВЕ СВОД ПРАВИЛ ПО ПРОЕКТИРОВАНИЮ И СТРОИТЕЛЬСТВУ ПРОЕКТИРОВАНИЕ ЗЕМЛЯНОГО ПОЛОТНА ЖЕЛЕЗНЫХ ДОРОГ КОЛЕИ 1520 мм СП 32-104-98 ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ПО СТРОИТЕЛЬНОЙ, АРХИТЕКТУРНОЙ И ЖИЛИЩНОЙ ПОЛИТИКЕ (ГОССТРОЙ РОССИИ) МОСКВА ПРЕДИСЛОВИЕ 1 РАЗРАБОТАН институтом ОАО ЦНИИС с участием ВНИИЖТ, ОАО Мосгипротранс, АО Ленгипротранс, АО Сибгипротранс, Киевгипротранс, Московского...»

«СОДЕРЖАНИЕ 3 Введение 4 1 Организационно-правовое обеспечение образовательной деятельности 6 2 Структура факультета и система управления процессом обучения 10 3 Структура подготовки обучающихся 11 4 Качество содержания подготовки обучающихся 14 5 Качество организации учебного процесса 15 6 Внутривузовская система контроля качества подготовки обучающихся 7 Востребованность выпускников 8 Качество кадрового обеспечения 9 Качество учебно-методического и библиотечно-информационного обеспечения 10...»

«Ministry of Natural Resourcesand ecologies of the Russian Federation Sokhondinsky State Nature Biosphere Reserve FLORA AND FAUNA OF THE TRANSBOUNDARY ESPECIALLY PROTECTED AREA “THE UPPER REACHES OF THE AMUR” Proceedings of the Sokhondinsky Reserve 5th issue Chita 2012. Министерство природных ресурсов и экологии РФ Сохондинский государственный природный биосферный заповедник РАСТИТЕЛЬНЫЙ И ЖИВОТНЫЙ МИР ТРАНСГРАНИЧНОЙ ОСОБО ОХРАНЯЕМОЙ ТЕРРИТОРИИ “ИСТОКИ АМУРА” Труды Сохондинского заповедника...»

«Н. А. КОНОВАЛОВ, Е. А. ПУГАЧ ОСНОВЫ ЛЕСНОЙ СЕЛЕКЦИИ И СОРТОВОГО СЕМЕНОВОДСТВА Издание 2-е, переработанное Москва Издательство ЛЕСНАЯ ПРОМЫШЛЕННОСТЬ 1978 У Д К 634.0.165.6 Основы лесной селекции и сортового семеноводства. И зд. 2-е, перераб. К о н о в а л о в Н. А., П у г а ч Е. А. М., Лесная промышленность, 1978. 176 с. В книге освещены основные вопросы генетики, лесной селекции и сорто­ вого семеноводства. В ра зд ел е Лесная селекция изложены на современном научном уровне понятия о генетике...»

«ГОСТ Р 52969-2008 Группа Н17 НАЦИОНАЛЬНЫЙ СТАНДАРТ РОССИЙСКОЙ ФЕДЕРАЦИИ МАСЛО СЛИВОЧНОЕ Технические условия Butter. Specifications ОКС 67.100.20 ОКП 92 2110 Дата введения 2010-01-01 Предисловие Цели и принципы стандартизации в Российской Федерации установлены Федеральным законом от 27 декабря 2002 г. N 184-ФЗ О техническом регулировании, а правила применения национальных стандартов Российской Федерации - ГОСТ Р 1.0-2004 Стандартизация в Российской Федерации. Основные положения Сведения о...»

«Богдасарова Т.С., Писарева С.А., Пискунова Е.В., Светенко Т.В. Vercammen E. Теория и практика подготовки менеджеров по развитию в современных университетах: по материалам реализации международного межвузовского проекта 1 Богдасарова Т.С., Писарева С.А., Пискунова Е.В., Светенко Т.В., Vercammen E. Теория и практика подготовки менеджеров по развитию в современных университетах: по материалам реализации международного межвузовского проекта. Научно-методические материалы. 2 Оглавление Стр. Введение...»

«Научно-производственная фирма ЯР ПРОЕКТИРОВАНИЕ И АНАЛИЗ РАДИОСЕТЕЙ и САНИТАРНЫЕ ПАСПОРТА НА ПЕРЕДАЮЩИЕ РАДИОТЕХНИЧЕСКИЕ ОБЪЕКТЫ КРАТКАЯ ИНФОРМАЦИЯ О РАЗРАБОТКЕ Ярославль 2010 2 Введение 1. ПИАР 4.56 1.1 Структура пакета программ версии 4.56/2010 1.2 Геоинформационная база 1.3 Интерфейс пользователя 1.4 Основные технические характеристики 1.5 Основные функциональные возможности 1.6 Функциональные возможности анализа ЭМС 2. Сравнение измеренных и расчетных...»

«Е.В.Буянов Техника горных маршрутов Снаряжение Тактика Приемы Процессы Библиография 1991 - 2010 АННОТАЦИЯ Сборник статей мастера спорта СССР по туризму (книга написана в период с 1991 по 1997 г. с обновлением материала до современного уровня) посвящена вопросам подготовки, проведения горных путешествий и применения различных предметов снаряжения. Даны описания конструкций, их возможных модификаций с изложением принципов работы, технических и технологических особенностей, техники использования....»

«Введены в действие Приказом Федеральной службы геодезии и картографии России от 24 декабря 2002 г. N 196-пр СМЕТНЫЕ УКРУПНЕННЫЕ РАСЦЕНКИ НА ТОПОГРАФОГЕОДЕЗИЧЕСКИЕ РАБОТЫ СУР-2002 Сметные укрупненные расценки на топографо-геодезические работы (СУР-2002) разработаны Отделом экономики Центрального ордена Знак Почета научно-исследовательского института геодезии, аэросъемки и картографии им. Ф.Н. Красовского (ЦНИИГАиК) Федеральной службы геодезии и картографии России (Роскартографии). В справочник...»

«ОСОБЕННОСТИ СОБЫТИЙНОГО МАРКЕТИНГА ТОРГОВО-РАЗВЛЕКАТЕЛЬНОГО ЦЕНТРА ВЕСНА! Беспаликова А. Е. – студент, Антюфеева Е. В. - доцент, кандидат филологических наук. Алтайский государственный технический университет им. И.И. Ползунова (г. Барнаул) Событийный маректинг – один из новых инструментов привлечения внимания потребителей к бренду. В городе Барнауле он начал применяться относительно недавно. Особенно активно сейчас он используется крупными торговыми центрами, такими, как ТРЦ Весна!. Потому...»

«Каталог мотор-редукторы 15 Издание 09/2013 Страницы Двигатели 547-598 Общая информация Режимы эксплуатации согласно стандарту DIN EN 60034 Технические параметры двигателей на 50 Гц Технические параметры двигателей на 60 Гц Эксплуатация с преобразователем частоты Взрывозащита 547 www.bauergears.com P-7112-BGM-A4 Двигатели Общая информация Директива по экологичности кон- Директива Европарламента и Совета Европы 2009/125/EC, изданная в 2009 году, струкции важных для энергопотре- регламентирует...»




 
© 2014 www.kniga.seluk.ru - «Бесплатная электронная библиотека - Книги, пособия, учебники, издания, публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.