Моноид трассировки

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

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

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

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

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

След

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

Примеры

Рассмотрим алфавит . Возможным отношением зависимости является ${\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 См. Обсуждение:моноид трассировки#Как синтаксические моноиды ]} ${\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 г.