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

редактировать

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

Исторические моноиды встречаются в теории параллельных вычислений и обеспечивают низкоуровневую математическую основу для вычислений процесса, например, CSP - язык последовательных процессов связи или CCS - исчисление взаимодействующих систем. Исторические моноиды были впервые представлены MW Shields.

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

Содержание

1 Моноиды продукта и проекция
2 Истории
3 Связь с информатикой
4 Свойства
5 Примечания
6 Ссылки

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

Пусть

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

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

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

P (A) = Σ 1 ∗ × Σ 2 ∗ × ⋯ × Σ N ∗ {\ Displaystyle P (A) = \ Sigma _ {1} ^ {*} \ times \ Sigma _ {2} ^ {*} \ times \ cdots \ times \ Sigma _ {n} ^ { *}}

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

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

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

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

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

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

затем

uv = (u 1 v 1, u 2 v 2,…, unvn) {\ displaystyle \ mathbf {uv} = (u_ {1} v_ {1}, u_ {2 } v_ {2}, \ ldots, u_ {n} v_ {n}) \,}

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

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

Σ = Σ 1 ∪ Σ 2 ∪ ⋯ ∪ Σ n. {\ displaystyle \ Sigma = \ Sigma _ {1} \ cup \ Sigma _ {2} \ cup \ cdots \ cup \ Sigma _ {n}. \,}

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

(объединение здесь - это объединение множества , а не дизъюнктное объединение.) Для любой строки $w ∈ Σ ∗ {\ displaystyle w \ in \ Sigma ^ {*}}$ ${\ displaystyle w \ in \ Sigma ^ {*}}$ мы можем выбрать только буквы в некотором $Σ k ∗ {\ displaystyle \ Sigma _ {k} ^ {*}}$ ${\ displaystyle \ Sigma _ {k} ^ {*}}$ с использованием соответствующей строковой проекции $π k: Σ ∗ → Σ К * {\ Displaystyle \ пи _ {к}: \ Sigma ^ {*} \ to \ Sigma _ {k} ^ {*}}$ ${\ displaystyle \ pi _ {k}: \ Sigma ^ {*} \ to \ Sigma _ {k} ^ {*}}$ . A распределение $π: Σ ∗ → P (A) {\ displaystyle \ pi: \ Sigma ^ {*} \ to P (A)}$ ${\ displaystyle \ pi: \ Sigma ^ {*} \ to P (A)}$ - это отображение, которое работает на $w ∈ Σ ∗ {\ displaystyle w \ in \ Sigma ^ {*}}$ ${\ displaystyle w \ in \ Sigma ^ {*}}$ со всеми $π k {\ displaystyle \ pi _ {k}}$ $\ pi _ {k}$ , разделяя его на компоненты в каждом свободном моноиде:

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

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

Истории

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

π (a) = (a 1, a 2,…, an) {\ displaystyle \ pi (a) = (a_ {1}, a_ {2}, \ ldots, a_ {n}) }

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

где

ak = {a, если a ∈ Σ, k ε в противном случае. {\ displaystyle a_ {k} = {\ begin {cases} a {\ t_dv {if}} a \ in \ Sigma _ {k} \\\ varepsilon {\ t_dv {else}}. \ end {cases}}}

{\ displaystyle a_ {k} = {\ begin {cases} a {\ t_dv {if}} a \ в \ Sigma _ {k} \\\ varepsilon {\ t_dv {else}}. \ end {cases}}}

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

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

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

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

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

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

Свойства

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

D = (Σ 1 × Σ 1) ∪ (Σ 2 × Σ 2) ∪ ⋯ ∪ (Σ n × Σ n). {\ 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 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).}

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

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

Notes

^MW Шилдс "Параллельные машины", Компьютерный журнал, (1985) 28 стр. 449–465.

Ссылки

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