Моноид истории

В математике и информатике моноид истории — это способ представления истории одновременно выполняемых компьютерных процессов в виде набора строк , каждая строка представляет индивидуальную историю процесса. Моноид истории предоставляет набор примитивов синхронизации (таких как блокировки , мьютексы или объединения потоков ) для обеспечения точек встречи между набором независимо выполняющихся процессов или потоков .

Моноиды истории встречаются в теории параллельных вычислений и обеспечивают низкоуровневую математическую основу для исчислений процессов , таких как CSP (язык взаимодействия последовательных процессов ) или CCS ( исчисление взаимодействующих систем ). Моноиды истории были впервые представлены М.В. Шилдсом. ^[1]

Моноиды истории изоморфны моноидам трассировки ( свободным частично коммутативным моноидам) и моноиду графов зависимостей . По существу, они являются свободными объектами и универсальны . Моноид истории — это тип полуабелева категориального произведения в категории моноидов.

Моноиды продукта и проекция

Позволять

${\displaystyle A=(\Sigma _{1},\Sigma _{2},\ldots ,\Sigma _{n})}$

обозначают n -кортеж (не обязательно попарно непересекающихся) алфавитов . Обозначим все возможные комбинации одной строки конечной длины из каждого алфавита: ${\displaystyle \Sigma _{k}}$ ${\displaystyle P(A)}$

${\displaystyle P(A)=\Sigma _{1}^{*}\times \Sigma _{2}^{*}\times \cdots \times \Sigma _{n}^{*}}$

(На более формальном языке — это декартово произведение свободных моноидов . Надстрочная звезда — это звезда Клини .) Состав в моноиде произведения является покомпонентным, так что для ${\displaystyle P(A)}$ ${\displaystyle \Sigma _{k}}$

${\displaystyle \mathbf {u} =(u_{1},u_{2},\ldots ,u_{n})\,}$

и

${\displaystyle \mathbf {v} =(v_{1},v_{2},\ldots ,v_{n})\,}$

затем

${\displaystyle \mathbf {uv} =(u_{1}v_{1},u_{2}v_{2},\ldots ,u_{n}v_{n})\,}$

для всех в . Определите алфавит объединения как ${\displaystyle \mathbf {u} ,\mathbf {v} }$ ${\displaystyle P(A)}$

${\displaystyle \Sigma =\Sigma _{1}\cup \Sigma _{2}\cup \cdots \cup \Sigma _{n}.\,}$

(Объединение здесь — это объединение множеств , а не непересекающееся объединение .) Учитывая любую строку , мы можем выбрать только буквы в некоторых из них, используя соответствующую проекцию строки . Распределение — это отображение, которое действует со всеми , разделяя их на компоненты в каждом свободном моноиде: ${\displaystyle w\in \Sigma ^{*}}$ ${\displaystyle \Sigma _{k}^{*}}$ ${\displaystyle \pi _{k}:\Sigma ^{*}\to \Sigma _{k}^{*}}$ ${\displaystyle \pi :\Sigma ^{*}\to P(A)}$ ${\displaystyle w\in \Sigma ^{*}}$ ${\displaystyle \pi _{k}}$

${\displaystyle \pi (w)\mapsto (\pi _{1}(w),\pi _{2}(w),\ldots ,\pi _{n}(w)).\,}$

Истории

Для каждого кортеж называется элементарной историей файла . Она служит индикаторной функцией включения буквы а в алфавит . То есть, ${\displaystyle a\in \Sigma }$ ${\displaystyle \pi (a)}$ ${\displaystyle \Sigma _{k}}$

${\displaystyle \pi (a)=(a_{1},a_{2},\ldots ,a_{n})}$

где

${\displaystyle a_{k}={\begin{cases}a{\mbox{ if }}a\in \Sigma _{k}\\\varepsilon {\mbox{ otherwise }}.\end{cases}}}$

Здесь обозначает пустую строку . Моноид истории — это субмоноид моноида произведения , порожденного элементарными историями: (где надстрочная звезда — это звезда Клини, примененная с покомпонентным определением состава, как указано выше). Элементы глобальной истории называются глобальными историями , а проекции глобальной истории — индивидуальными историями . ${\displaystyle \varepsilon }$ ${\displaystyle H(A)}$ ${\displaystyle P(A)}$ ${\displaystyle H(A)=\{\pi (a)|a\in \Sigma \}^{*}}$ ${\displaystyle H(A)}$

Связь с информатикой

Использование слова « история» в этом контексте и его связь с параллельными вычислениями можно понимать следующим образом. Индивидуальная история — это запись последовательности состояний процесса (или потока , или машины ); алфавит — это набор состояний процесса. ${\displaystyle \Sigma _{k}}$

Буква, встречающаяся в двух или более алфавитах, служит примитивом синхронизации между различными отдельными историями. То есть, если такое письмо встречается в одной отдельной истории, оно должно произойти и в другой истории и служит для «связывания» или «свидания» их вместе.

Рассмотрим, например, и . Союзный алфавит, конечно . Элементарные истории — это , , , и . В этом примере отдельная история первого процесса может иметь вид, а отдельная история второй машины — . Обе эти отдельные истории представлены глобальной историей , поскольку проекция этой строки на отдельные алфавиты дает индивидуальные истории. В глобальной истории буквы и можно рассматривать как коммутирующие с буквами и , поскольку их можно переставлять без изменения отдельных историй. Такая коммутация — это просто утверждение, что первый и второй процессы выполняются одновременно и неупорядочены друг относительно друга; они (пока) не обменивались сообщениями и не выполняли синхронизацию. ${\displaystyle \Sigma _{1}=\{a,b,c\}}$ ${\displaystyle \Sigma _{2}=\{a,d,e\}}$ ${\displaystyle \Sigma =\{a,b,c,d,e\}}$ ${\displaystyle (a,a)}$ ${\displaystyle (b,\varepsilon )}$ ${\displaystyle (c,\varepsilon )}$ ${\displaystyle (\varepsilon ,d)}$ ${\displaystyle (\varepsilon ,e)}$ ${\displaystyle bcbcc}$ ${\displaystyle ddded}$ ${\displaystyle bcbdddcced}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle e}$

Буква служит примитивом синхронизации, поскольку ее появление отмечает место как в глобальной, так и в индивидуальной истории, через которое невозможно переключиться. Таким образом, хотя буквы и можно переупорядочить мимо и , их нельзя переупорядочить мимо . Таким образом, глобальная история и глобальная история имеют отдельные истории и , что указывает на то, что исполнение может произойти до или после . Однако письмо синхронизируется, поэтому это гарантированно произойдет после , даже если оно находится в другом процессе , чем . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle e}$ ${\displaystyle a}$ ${\displaystyle bcdabe}$ ${\displaystyle bdcaeb}$ ${\displaystyle bcab}$ ${\displaystyle dae}$ ${\displaystyle d}$ ${\displaystyle c}$ ${\displaystyle a}$ ${\displaystyle e}$ ${\displaystyle c}$ ${\displaystyle e}$ ${\displaystyle c}$

Характеристики

Моноид истории изоморфен моноиду следа и, как таковой, является типом полуабелева категориального произведения в категории моноидов. В частности, моноид истории изоморфен моноиду следа с отношением зависимости , заданным выражением ${\displaystyle H(\Sigma _{1},\Sigma _{2},\ldots ,\Sigma _{n})}$ ${\displaystyle \mathbb {M} (D)}$

${\displaystyle D=\left(\Sigma _{1}\times \Sigma _{1}\right)\cup \left(\Sigma _{2}\times \Sigma _{2}\right)\cup \cdots \cup \left(\Sigma _{n}\times \Sigma _{n}\right).}$

Проще говоря, это всего лишь формальная формулировка неформального обсуждения, приведенного выше: буквы алфавита могут быть коммутативно переупорядочены после букв алфавита , если только они не являются буквами, встречающимися в обоих алфавитах. Таким образом, следы – это именно глобальные истории, и наоборот. ${\displaystyle \Sigma _{k}}$ ${\displaystyle \Sigma _{j}}$

И наоборот, учитывая любой моноид следа , можно построить изоморфный моноид истории, взяв последовательность алфавитов , где пробегает все пары в . ${\displaystyle \mathbb {M} (D)}$ ${\displaystyle \Sigma _{a,b}=\{a,b\}}$ ${\displaystyle (a,b)}$ ${\displaystyle D}$

Примечания

1. М.В. Шилдс «Параллельные машины», Computer Journal , (1985) 28 стр. 449–465.

Рекомендации

• Антони Мазуркевич, «Введение в теорию следов», стр. 3–41, в «Книге следов» , В. Дикерт, Г. Розенберг, ред. (1995) World Scientific, Сингапур ISBN  981-02-2058-8
• Фолькер Дикерт, Ив Метивье, «Частичная коммутация и следы», Г. Розенберг и А. Саломаа , редакторы, Справочник по формальным языкам , Vol. 3 , За гранью слов, страницы 457–534. Шпрингер-Верлаг, Берлин, 1997 г.