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

редактировать

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

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

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

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

Содержание

1 Трассировка
2 Примеры
3 Свойства
4 Универсальное свойство
5 Нормальные формы
6 Языки трассировки
7 Примечания
8 Ссылки

След

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

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

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

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

M (D) = Σ ∗ / ≡ D. {\ Displaystyle \ mathbb {M} (D) = \ Sigma ^ {*} / \ Equiv _ {D}.}

{\ mathbb {M}} (D) = \ Sigma ^ {*} / \ Equiv _ {D}.

Гомоморфизм

ϕ D: Σ ∗ → M (D) {\ Displaystyle \ phi _ {D}: \ Sigma ^ {*} \ to \ mathbb {M} (D)}

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

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

Примеры

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

D = {a, b} × {a, b} ∪ {a, c} × {a, c} = {a, b} 2 ∪ {a, c} 2 = {( a, b), (b, a), (a, c), (c, a), (a, a), (b, b), (c, 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}}}

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

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

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

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

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

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

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

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

Свойства

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

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

Для следов справедлива строгая форма леммы Леви. В частности, если $uv ≡ xy {\ displaystyle uv \ Equiv xy}$ $uv \ Equiv xy$ для строк u, v, x, y, то существуют строки $z 1, z 2, z 3 {\ displaystyle z_ {1}, z_ {2}, z_ {3}}$ $z_ {1}, z_ {2}, z_ {3}$ и $z 4 {\ displaystyle z_ {4}}$ $z_ {4}$ такие, что $(w 2, w 3) ∈ ID {\ displaystyle (w_ {2}, w_ {3}) \ in I_ {D}}$ $(w_ {2}, w_ {3}) \ in I_ {D}$ для всех букв $w 2 ∈ Σ {\ displaystyle w_ {2} \ in \ Sigma}$ $w_ {2} \ in \ Sigma$ и $w 3 ∈ Σ {\ displaystyle w_ {3} \ in \ Sigma}$ $w_ {3} \ in \ Sigma$ так, что $w 2 {\ displaystyle w_ {2 }}$ $w_ {2 }$ встречается в $z 2 {\ displaystyle z_ {2}}$ $z_{2}$ и $w 3 {\ displaystyle w_ {3}}$ $w_ {3}$ встречается в $z 3 {\ displaystyle z_ {3}}$ $z_{3}$ и

u ≡ z 1 z 2, v ≡ z 3 z 4, {\ displaystyle u \ Equiv z_ {1} z_ {2}, \ qquad v \ Equiv z_ {3} z_ {4},}

и \ эквив z_ {1} z_ {2}, \ qquad v \ эквив z_ {3} z_ {4},

x ≡ z 1 z 3, y ≡ z 2 z 4. {\ displaystyle x \ Equiv z_ {1} z_ {3}, \ qquad y \ Equiv z_ {2} z_ {4}.}

x \ эквив z_ {1} z_ {3}, \ qquad y \ эквив z_ {2} z_ {4}.

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

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

ψ: Σ ∗ → M {\ displaystyle \ psi: \ Sigma ^ {*} \ to M}

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

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

ψ (вес) = ψ (ε) {\ displaystyle \ psi (w) = \ psi (\ varepsilon)}

\ psi (w) = \ psi (\ varepsilon)

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

w = ε {\ displaystyle w = \ varepsilon}

w = \ varepsilon

(a, b) ∈ ID {\ displaystyle (a, b) \ in I_ {D}}

(a, b) \ in I_ {D}

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

ψ (ab) = ψ (ba) {\ displaystyle \ psi (ab) = \ psi (ba)}

{\ displaystyle \ psi (ab) = \ psi (ba)}

ψ (ua) = ψ (v) {\ displaystyle \ psi (ua) = \ psi (v)}

{\ displaystyle \ psi (ua) = \ psi (v)}

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

ψ (u) = ψ (v ÷ a) { \ Displaystyle \ psi (u) = \ psi (v \ div a)}

\ psi (u) = \ psi (v \ div a)

ψ (ua) = ψ (vb) {\ displaystyle \ psi (ua) = \ psi (vb)}

{\ displaystyle \ psi (ua) = \ psi (vb)}

a ≠ b {\ displaystyle a \ neq b}

a \ neq b

подразумевает, что

(a, b) ∈ ID {\ displaystyle (a, b) \ in I_ {D}}

(a, b) \ in I_ {D}

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

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

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

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

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

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

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

L = \ bigcup [L] _ {D}

где

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

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

- это замыкание следа набора строк.

Примечания

Ссылки

Общие ссылки

Diekert, Volker; Métivier, Yves (1997), «Частичная коммутация и следы», в Rozenberg, G.; Саломаа, А. (ред.), Справочник по формальным языкам, том. 3; Beyond Words, Springer-Verlag, Berlin, стр. 457–534, ISBN 3-540-60649-1
Lothaire, M. (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, Springer, 1990, ISBN 3-540-53031-2, стр. 9–29
Sándor, Jozsef; Crstici, Borislav (2004), Справочник по теории чисел II, Dordrecht: Kluwer Academic, стр. 32–36, ISBN 1-4020-2546-7, Zbl 1079.11001

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

Пьер Картье и Доминик Фоата, Problèmes combinatoires de commutation et réarrangements, Lecture Notes in Mathematics 85, Springer-Verlag, Berlin, 1969, Бесплатная перепечатка за 2006 год с новыми приложениями
Антони Мазуркевич, Параллельные программные схемы и их интерпретации, DAIMI Report PB 78, Орхусский университет, 1977