Трассировка моноида

В информатике трассировка — это набор строк , в которых некоторым буквам строки разрешено коммутировать , а другим — нет. Он обобщает концепцию строки, не заставляя буквы всегда находиться в фиксированном порядке, но допуская определенные перетасовки. Следы были введены Пьером Картье и Домиником Фоата в 1969 году, чтобы дать комбинаторное доказательство основной теоремы Мак-Магона . Трассировки используются в теориях параллельных вычислений , где коммутирующие буквы обозначают части задания, которые могут выполняться независимо друг от друга, а некоммутирующие буквы обозначают блокировки, точки синхронизации или соединения потоков .

Моноид следов или свободный частично коммутативный моноид — это моноид следов. В двух словах оно устроено следующим образом: множества коммутирующих букв задаются отношением независимости . Они вызывают отношение эквивалентности эквивалентных строк; элементами классов эквивалентности являются следы. Затем отношение эквивалентности разбивает свободный моноид (множество всех строк конечной длины) на набор классов эквивалентности; результат по-прежнему остается моноидом; это фактормоноид и называется моноидом следа . Моноид следа является универсальным , поскольку все моноиды, гомоморфные по зависимостям (см. ниже), фактически изоморфны .

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

След

Позволять $\Sigma ^{*}$ обозначаем свободный моноид, то есть множество всех строк, записанных в алфавите $\Sigma$. Здесь звездочкой обозначена, как обычно, звезда Клини . Отношение независимости $I$ на $\Sigma$ затем индуцирует (симметричное) бинарное отношение $\sim$ на $\Sigma ^{*}$, где $u\sim v$ тогда и только тогда, когда существуют $x,y\in \Sigma ^{*}$и пара $(a,b)\in I$ такой, что $u=xaby$ и $v=xbay$. Здесь, $u,v,x$ и $y$ понимаются как строки (элементы $\Sigma ^{*}$), пока $a$ и $b$ буквы (элементы $\Sigma$).

След определяется как рефлексивное транзитивное замыкание $\sim$. Таким образом, след является отношением эквивалентности на $\Sigma ^{*}$, и обозначается $\equiv _{D}$, где $D$ – отношение зависимости, соответствующее $I,$ то есть $D=(\Sigma \times \Sigma )\setminus I$ и наоборот $I=(\Sigma \times \Sigma )\setminus D.$ Очевидно, что разные зависимости дадут разные отношения эквивалентности.

Транзитивное замыкание означает, что $u\equiv v$ тогда и только тогда, когда существует последовательность строк $(w_{0},w_{1},\cdots ,w_{n})$ такой, что $u\sim w_{0}$ и $v\sim w_{n}$ и $w_{i}\sim w_{i+1}$ для всех $0\leq i<n$. След устойчив при работе моноида на $\Sigma ^{*}$ ( конкатенация ) и, следовательно, является отношением конгруэнтности на $\Sigma ^{*}$.

Моноид следа, обычно обозначаемый как $\mathbb {M} (D)$, определяется как фактормоноид

$\mathbb {M} (D)=\Sigma ^{*}/\equiv _{D}.$

Гомоморфизм

$\phi _{D}:\Sigma ^{*}\to \mathbb {M} (D)$

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

Также можно найти моноид следа, обозначаемый как $M(\Sigma ,I)$ где $I$ это отношение независимости. Что сбивает с толку, можно также найти отношение коммутации, используемое вместо отношения независимости (оно отличается включением всех диагональных элементов).

Примеры

Рассмотрим алфавит $\Sigma =\{a,b,c\}$. Возможным отношением зависимости является

${\begin{matrix}D&=&\{a,b\}\times \{a,b\}\quad \cup \quad \{a,c\}\times \{a,c\}\\&=&\{a,b\}^{2}\cup \{a,c\}^{2}\\&=&\{(a,b),(b,a),(a,c),(c,a),(a,a),(b,b),(c,c)\}\end{matrix}}$

Соответствующая независимость

$I_{D}=\{(b,c)\,,\,(c,b)\}$

Поэтому буквы $b,c$ добираться. Так, например, класс эквивалентности трассировки для строки $abababbca$ было бы

$[abababbca]_{D}=\{abababbca\,,\;abababcba\,,\;ababacbba\}$

Класс эквивалентности $[abababbca]_{D}$ является элементом моноида следа.

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

Свойство отмены утверждает, что эквивалентность сохраняется при отмене по праву . То есть, если $w\equiv v$, затем $(w\div a)\equiv (v\div a)$. Здесь обозначение $w\div a$ обозначает правую отмену, удаление первого вхождения буквы a из строки w , начиная с правой части. Эквивалентность также поддерживается за счет левого сокращения. Далее следуют несколько следствий:

• Встраивание: $w\equiv v$ тогда и только тогда, когда $xwy\equiv xvy$ для строк x и y . Таким образом, моноид трассировки является синтаксическим моноидом.
• Независимость: если $ua\equiv vb$ и $a\neq b$, то a не зависит от b . То есть, $(a,b)\in I_{D}$. Более того, существует строка w такая, что $u\equiv wb$ и $v\equiv wa$.
• сохраняется эквивалентность Правило проекции: при проекции строки , так что если $w\equiv v$, затем $\pi _{\Sigma }(w)\equiv \pi _{\Sigma }(v)$.

Для следов справедлива сильная форма леммы Леви . В частности, если $uv\equiv xy$ для строк u , v , x , y , то существуют строки $z_{1},z_{2},z_{3}$ и $z_{4}$ такой, что $(w_{2},w_{3})\in I_{D}$для всех букв $w_{2}\in \Sigma$ и $w_{3}\in \Sigma$ такой, что $w_{2}$ происходит в $z_{2}$ и $w_{3}$ происходит в $z_{3}$, и

$u\equiv z_{1}z_{2},\qquad v\equiv z_{3}z_{4},$

$x\equiv z_{1}z_{3},\qquad y\equiv z_{2}z_{4}.$

Универсальная собственность

Морфизм зависимости (относительно зависимости D ) — это морфизм

$\psi :\Sigma ^{*}\to M$

к некоторому моноиду M , такому, что выполняются «обычные» свойства следа, а именно:

1. $\psi (w)=\psi (\varepsilon )$ подразумевает, что $w=\varepsilon$

2. $(a,b)\in I_{D}$ подразумевает, что $\psi (ab)=\psi (ba)$

3. $\psi (ua)=\psi (v)$ подразумевает, что $\psi (u)=\psi (v\div a)$

4. $\psi (ua)=\psi (vb)$ и $a\neq b$ подразумеваю, что $(a,b)\in I_{D}$

Морфизмы зависимостей универсальны в том смысле, что для данной фиксированной зависимости D , если $\psi :\Sigma ^{*}\to M$ является морфизмом зависимости моноида M то M изоморфен , моноиду следа $\mathbb {M} (D)$. В частности, естественный гомоморфизм является морфизмом зависимостей.

Нормальные формы

Существуют две хорошо известные нормальные формы слов в следовых моноидах. Одна из них — это лексикографическая нормальная форма, созданная Анатолием В. Анисимовым и Дональдом Кнутом , а другая — нормальная форма Фоата , созданная Пьером Картье и Домиником Фоата , которые изучали моноид следа для его комбинаторики в 1960-х годах.

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

Трассировка языков

Точно так же, как формальный язык можно рассматривать как подмножество $\Sigma ^{*}$, набор всех возможных строк, поэтому язык трассировки определяется как подмножество $\mathbb {M} (D)$ все возможные следы.

Альтернативно, но эквивалентно, язык $L\subseteq \Sigma ^{*}$ является языком трассировки или считается совместимым с зависимостью D , если

$L=[L]_{D}$

где

$[L]_{D}=\bigcup _{w\in L}[w]_{D}$

— это замыкание трассировки набора строк.

См. также

• Трассировка кэша

Ссылки

Общие ссылки

• Дикерт, Волкер; Метивье, Ив (1997), «Частичная коммутация и следы» , в Розенберге, Г.; Саломаа А. (ред.), Справочник по формальным языкам, том. 3; Beyond Words , Springer-Verlag, Берлин, стр. 457–534, ISBN.  3-540-60649-1
• Лотер, М. (2011), Алгебраическая комбинаторика слов , Энциклопедия математики и ее приложений, том. 90, с предисловием Жана Берстеля и Доминика Перрена (перепечатка издания в твердом переплете 2002 г.), Cambridge University Press, ISBN  978-0-521-18071-9 , Збл   1221,68183
• Антони Мазуркевич, «Введение в теорию следов», стр. 3–41, в «Книге следов» , В. Дикерт, Г. Розенберг, ред. (1995) World Scientific, Сингапур ISBN   981-02-2058-8
• Фолькер Дикерт, Комбинаторика следов , LNCS 454, Springer, 1990, ISBN   3-540-53031-2 , стр. 9–29.
• Шандор, Джозеф; Крстичи, Борислав (2004), Справочник по теории чисел II , Дордрехт: Kluwer Academic, стр. 32–36, ISBN  1-4020-2546-7 , Збл   1079.11001

Основополагающие публикации

• Пьер Картье и Доминик Фоата, Комбинаторные проблемы переключения и перестановок , Конспекты лекций по математике 85, Springer-Verlag, Берлин, 1969, бесплатное переиздание 2006 г. с новыми приложениями.
• Антони Мазуркевич, Схемы параллельных программ и их интерпретации , Отчет DAIMI PB 78, Орхусский университет, 1977 г.