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

Обобщение строк в информатике

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

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

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

След

Обозначим через свободный моноид, то есть множество всех строк, записанных в алфавите . Здесь звездочкой обозначена, как обычно, звезда Клини . Отношение независимости на тогда индуцирует (симметричное) бинарное отношение на , где тогда и только тогда, когда существуют , и пара такая, что и . Здесь под и понимаются строки (элементы ), а под буквами (элементы ). ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \Sigma }$ ${\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}}$ ${\displaystyle D}$ ${\displaystyle I,}$ ${\displaystyle D=(\Sigma \times \Sigma )\setminus I}$ ${\displaystyle I=(\Sigma \times \Sigma )\setminus 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 M(\Sigma ,I)}$ ${\displaystyle I}$

Примеры

Рассмотрим алфавит . Возможным отношением зависимости является ${\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}}$

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

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

• Встраивание: тогда и только тогда, когда для строк x и y . Таким образом, моноид трассировки является синтаксическим моноидом. ^{[ non sequitur См. обсуждение:Trace monoid#As Syntactic Monoids ]} ${\displaystyle w\equiv v}$ ${\displaystyle xwy\equiv xvy}$
• Независимость: если и , то a не зависит от b . То есть, . Более того, существует строка w такая, что и . ${\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)}$

Для следов справедлива сильная форма леммы Леви . В частности, если для строк u , v , x , y , то существуют строки и такие, что для всех букв и такие, которые встречаются в и встречаются в , и ${\displaystyle uv\equiv xy}$ ${\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 , если это морфизм зависимости моноида M , то M изоморфен моноиду следа . В частности, естественный гомоморфизм является морфизмом зависимостей. ${\displaystyle \psi :\Sigma ^{*}\to M}$ ${\displaystyle \mathbb {M} (D)}$

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

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

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

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

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

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

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

где

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

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

Смотрите также

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

Примечания

1. Шандор и Крстичи (2004) стр.161
2. Предложение 2.2, Дикерт и Метивье, 1997.
3. Раздел 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 г.