Моноид трассировки - Trace monoid

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

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

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

След

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

В след определяется как симметричное, рефлексивное и транзитивное замыкание ${\displaystyle \sim }$. Таким образом, след является отношением эквивалентности на ${\displaystyle \Sigma ^{*}}$, и обозначается ${\displaystyle \equiv _{D}}$. Нижний индекс D на эквивалентности просто означает, что эквивалентность получается из независимости я вызванный зависимостью D. Ясно, что разные зависимости дадут разные отношения эквивалентности.

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

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

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

Гомоморфизм

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

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

Примеры

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

${\displaystyle {\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}}}$

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

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

Следовательно, буквы ${\displaystyle b,c}$ ездить. Так, например, класс эквивалентности трассировки для строки ${\displaystyle abababbca}$ было бы

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

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

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

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

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

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

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

${\displaystyle x\equiv z_{1}z_{3},\qquad y\equiv z_{2}z_{4}.}$^[2]

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

А морфизм зависимости (относительно зависимости D) является морфизмом

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

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

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

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

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

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

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

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

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

Языки трассировки

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

Язык ${\displaystyle L\subseteq \Sigma ^{*}}$ является языком трассировки или называется последовательный с зависимостью D если

${\displaystyle L=\bigcup [L]_{D}}$

куда

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

является замыканием трассировки набора строк.

Примечания

1. Sándor & Crstici (2004) с.161
2. Предложение 2.2, Дикерт и Метивье 1997.

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

Общие ссылки

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

Основные публикации

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