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

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

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

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

След

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

Следа определяются как симметричное, рефлексивное и транзитивное замыкание . Таким образом, след является отношением эквивалентности на и обозначается . Индекс Д об эквивалентности просто означает , что эквивалентность получается из независимости I , индуцированной зависимости D . Ясно, что разные зависимости дадут разные отношения эквивалентности. ${\ displaystyle \ sim}$ ${\ displaystyle \ Sigma ^ {*}}$ ${\ Displaystyle \ Equiv _ {D}}$

Транзитивное замыкание просто означает , что , если и только если существует последовательность строк таким образом, что и и для всех . След стабилен относительно операции моноида на ( конкатенации ) и, следовательно, является отношением конгруэнтности на . ${\ Displaystyle и \ эквивалент v}$ ${\ Displaystyle (ш_ {0}, ш_ {1}, \ cdots, ш_ {п})}$ ${\ displaystyle u \ sim w_ {0}}$ ${\ displaystyle v \ sim w_ {n}}$ ${\ Displaystyle ш_ {я} \ сим ш_ {я + 1}}$ ${\ Displaystyle 0 \ Leq я <п}$ ${\ 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 = \ {а, б, с \}}$

{\ 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 ш \ эквив v}$ ${\ Displaystyle (вес \ div а) \ эквив (v \ div а)}$ ${\ displaystyle w \ div a}$

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

Для следов верна сильная форма леммы Леви . В частности, если для строк u , v , x , y , тогда существуют строки и такие, что для всех букв и таких, которые встречаются и встречаются в , и ${\ Displaystyle УФ \ эквив ху}$ ${\ 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 и \ эквив г_ {1} г_ {2}, \ qquad v \ эквив г_ {3} г_ {4},}

{\ Displaystyle x \ Equiv z_ {1} z_ {3}, \ qquad y \ Equiv z_ {2} z_ {4}.}

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

Морфизм зависимостей (по отношению к зависимости D ) морфизм

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

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

1. означает, что

{\ Displaystyle \ пси (ш) = \ пси (\ varepsilon)}

{\ Displaystyle ш = \ 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}$ ${\ Displaystyle \ mathbb {M} (D)}$

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

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

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

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

Язык является языком трассировки или считается совместимым с зависимостью D, если ${\ Displaystyle L \ substeq \ Sigma ^ {*}}$

{\ Displaystyle L = [L] _ {D}}

где

{\ Displaystyle [L] _ {D} = \ bigcup _ {ш \ in L} [ш] _ {D}}

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

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

Кеш трассировки

Languages

In other projects