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

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

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

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

и

Позволять

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

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

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

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

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

и

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

затем

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

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

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

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

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

Истории

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

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

где

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

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

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

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

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

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

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

Свойства

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

$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).$

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

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

Ссылки

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