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

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

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

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

След [ править ]

Позволять $\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 . Таким образом, моноид трассировки является синтаксическим моноидом. ^{[ non sequitur См. обсуждение:Trace monoid#As Syntactic Monoids ]}
Независимость: если $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}.

^[2]

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

( Морфизм зависимости относительно зависимости 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-х годах. ^[3]

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

Отслеживание языков [ править ]

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

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

L=[L]_{D}

где

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

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

См. также [ править ]

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

Примечания [ править ]

^ Шандор и Крстичи (2004) стр.161
^ Предложение 2.2, Дикерт и Метивье, 1997.
^ Раздел 2.3, Дикерт и Метивье, 1997.

Ссылки [ править ]

Общие ссылки

Дикерт, Волкер; Метивье, Ив (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 г.

[CS161-1] Шандор и Крстичи (2004) стр.161

[2] Предложение 2.2, Дикерт и Метивье, 1997.

[3] Раздел 2.3, Дикерт и Метивье, 1997.

[1]

[2]

[3]