Исторический моноид - History monoid

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

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

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

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

Позволять

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

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

${displaystyle P(A)=Sigma _{1}^{*} imes Sigma _{2}^{*} imes cdots imes 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 win Sigma ^{*}}$, мы можем выделить только буквы в некоторых ${displaystyle Sigma _{k}^{*}}$ используя соответствующие струнная проекция ${displaystyle pi _{k}:Sigma ^{*} o Sigma _{k}^{*}}$. А распространение ${displaystyle pi :Sigma ^{*} o P(A)}$ это отображение, которое действует на ${displaystyle win Sigma ^{*}}$ со всеми ${displaystyle pi _{k}}$, разделяя его на составляющие в каждом свободном моноиде:

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

Истории

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

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

где

${displaystyle a_{k}={egin{cases}a{mbox{ if }}ain Sigma _{k}varepsilon {mbox{ otherwise }}.end{cases}}}$

Вот, ${displaystyle varepsilon }$ обозначает пустой строки. В история моноид ${displaystyle H(A)}$ - подмоноид моноида произведения ${displaystyle P(A)}$ порождаемые элементарными историями: ${displaystyle H(A)={pi (a)|ain 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} imes Sigma _{1}ight)cup left(Sigma _{2} imes Sigma _{2}ight)cup cdots cup left(Sigma _{n} imes Sigma _{n}ight).}$

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

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

Заметки

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

использованная литература

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