Полугрупповое действие

«S-set» перенаправляется сюда. Информацию о парке пригородных поездов см. в наборе Sydney Trains S.

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

Важным частным случаем является моноидное действие или акт , в котором полугруппа является моноидом , а единичный элемент моноида действует как тождественное преобразование множества. С точки зрения теории категорий , моноид — это категория с одним объектом, а акт — это функтор из этой категории в категорию множеств . Это немедленно обеспечивает обобщение моноидных действий на объекты в категориях, отличных от категории множеств.

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

(Примечание по терминологии: терминология, используемая в этой области, варьируется, иногда существенно, от одного автора к другому. Подробности см. в статье.)

Формальные определения

Пусть S — полугруппа. Тогда (левое) полугрупповое действие (или действие ) группы S представляет собой множество X вместе с операцией • : S × X → X , которая совместима с полугрупповой операцией ∗ следующим образом:

• для всех s , t в S и x в X , s • ( t • x ) знак равно ( s * t ) • x .

Это аналог (левого) группового действия в теории полугрупп , эквивалентный гомоморфизму полугруппы в набор функций на X . Действия правой полугруппы определяются аналогичным образом с помощью операции • : X × S → X, удовлетворяющей ( x • a ) • b = x • ( a ∗ b ) .

Если M — моноид, то (левое) моноидное действие (или действие ) M является (левым) полугрупповым действием M с дополнительным свойством, что

• для всех x в X : e • x = x

где e — единичный M. элемент Это соответственно дает моноидный гомоморфизм. Действия правого моноида определяются аналогично. Моноид М , действующий на множестве, также называется операторным моноидом .

Полугрупповое действие S на X можно превратить в моноидное действие, присоединив тождество к полугруппе и потребовав, чтобы оно действовало как тождественное преобразование на X .

Терминология и обозначения

Если S — полугруппа или моноид, то множество X , на котором S действует так, как указано выше (скажем, слева), также известно как (левое) S -действие , S -множество , S -действие , S -операнд или акт над S. левый Некоторые авторы не делают различия между действиями полугруппы и моноида, считая аксиому тождества ( e • x = x ) пустой, когда нет единичного элемента, или используя термин унитарный S -акт для S -акта с тождеством.

Определяющее свойство действия аналогично ассоциативности полугрупповой операции и означает, что все круглые скобки можно опустить. Обычной практикой, особенно в информатике, также являются опускание операций, чтобы и полугрупповая операция, и действие обозначались путем сопоставления. Таким образом, букв из S действуют на X , как в выражении stx для s , t в S и x в X. строки

Также довольно часто приходится работать с правыми действиями, а не с левыми. Однако каждое правое S-действие можно интерпретировать как левое действие над противоположной полугруппой , которая имеет те же элементы, что и S, но где умножение определяется обращением множителей, s • t = t • s , поэтому эти два понятия имеют вид по сути эквивалент. Здесь мы прежде всего стоим на точке зрения левых.

Действия и трансформации

Часто бывает удобно (например, если рассматривается более одного акта) использовать букву, например: $T$, для обозначения функции

$T\colon S\times X\to X$

определение $S$-действие и, следовательно, запись $T(s,x)$ вместо $s\cdot x$. Тогда для любого $s$ в $S$, мы обозначим через

$T_{s}\colon X\to X$

трансформация $X$ определяется

$T_{s}(x)=T(s,x).$

По определяющему свойству $S$-действовать, $T$ удовлетворяет

$T_{s*t}=T_{s}\circ T_{t}.$

Далее рассмотрим функцию $s\mapsto T_{s}$. Это то же самое, что $\operatorname {curry} (T):S\to (X\to X)$ (см. Каррирование ). Потому что $\operatorname {curry}$ является биекцией, действия полугруппы можно определить как функции $S\to (X\to X)$ которые удовлетворяют

$\operatorname {curry} (T)(s*t)=\operatorname {curry} (T)(s)\circ \operatorname {curry} (T)(t).$

То есть, $T$ является полугрупповым действием $S$ на $X$ тогда и только тогда, когда $\operatorname {curry} (T)$ является гомоморфизмом полугруппы из $S$ к полному моноиду преобразования $X$.

S -гомоморфизмы

Пусть X и X ′ — S -полигоны. Тогда S -гомоморфизм из X в X ′ является отображением

$F\colon X\to X'$

такой, что

$F(sx)=sF(x)$ для всех $s\in S$ и $x\in X$.

Множество всех таких S -гомоморфизмов обычно записывается как $\mathrm {Hom} _{S}(X,X')$.

М -гомоморфизмы М -полигонов, если М Точно так же определяются — моноид.

S -Act и M -Act

Для фиксированной полугруппы S левые S -полигоны являются объектами категории, обозначаемой S -Act, морфизмы которой являются S -гомоморфизмами. Соответствующую категорию правых S -полигонов иногда обозначают Act -S . (Это аналогично категориям R - Mod и Mod- R левых и правых модулей над кольцом .)

Для моноида M категории M -Act и Act- M определяются одинаково.

Примеры

• Любая полугруппа $(S,*)$ имеет действие на $S$, где $\cdot =*$. Свойство действия сохраняется благодаря ассоциативности $*$.
• В более общем смысле, для любого гомоморфизма полугрупп $F\colon (S,*)\rightarrow (T,\oplus )$, полугруппа $(S,*)$ имеет действие на $T$ данный $s\cdot t=F(s)\oplus t$.
• Для любого набора $X$, позволять $X^{*}$ — множество последовательностей элементов $X$. Полугруппа $(\mathbb {N} ,\times )$ имеет действие на $X^{*}$ данный $n\cdot s=s^{n}$ (где $s^{n}$ обозначает $s$ повторенный $n$ раз).
• Полугруппа $(\mathbb {N} ,\times )$ имеет правильное действие $(\mathbb {N} ,\cdot )$, заданный $x\cdot y=x^{y}$.

Полугруппы преобразований

Основная статья: Полугруппа трансформации

Ниже описано соответствие между полугруппами преобразований и действиями полугрупп. Если мы ограничим его действиями точных полугрупп, он будет иметь хорошие свойства.

Любую полугруппу преобразований можно превратить в действие полугруппы с помощью следующей конструкции. Для любой полугруппы преобразований $S$ из $X$, определим полугрупповое действие $T$ из $S$ на $X$ как $T(s,x)=s(x)$ для $s\in S,x\in X$. Это действие является точным, что эквивалентно $curry(T)$ будучи инъективным .

Обратно, для любого полугруппового действия $T$ из $S$ на $X$, определим полугруппу преобразований $S'=\{T_{s}\mid s\in S\}$. В этой конструкции мы «забываем» множество $S$. $S'$ равно изображению ​ $curry(T)$. Обозначим $curry(T)$ как $f$ для краткости. Если $f$ инъективен полугруппы из это изоморфизм , то $S$ к $S'$. Другими словами, если $T$ верен, то мы не забываем ничего важного. Это утверждение уточняется следующим наблюдением: если мы обратимся $S'$ вернуться к полугрупповому действию $T'$ из $S'$ на $X$, затем $T'(f(s),x)=T(s,x)$ для всех $s\in S,x\in X$. $T$ и $T'$ «изоморфны» через $f$, т. е. мы по существу восстановили $T$. Таким образом, некоторые авторы не видят различия между точными действиями полугрупп и полугруппами преобразований.

Приложения к информатике

Полуавтоматы

Основная статья: Полуавтомат

Полугруппы преобразований имеют существенное значение для структурной теории конечных автоматов теории автоматов . В частности, полуавтомат — это тройка (Σ, X , T ), где Σ — непустое множество, называемое входным алфавитом , X — непустое множество, называемое множеством состояний , а T — функция

$T\colon \Sigma \times X\to X$

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

Для полуавтомата пусть T _a : X → X , для a ∈ Σ, обозначает преобразование X, определенное формулой T _a ( x ) = T ( a , x ). Тогда полугруппа преобразований X, порожденная { T _a : a ∈ Σ}, называется характеристической полугруппой или системой переходов (Σ, X , T ). Эта полугруппа является моноидом, поэтому этот моноид называется характеристическим или переходным моноидом . Его также иногда рассматривают как Σ. ^∗ -действовать на X , где Σ ^∗ – свободный моноид строк, порожденный алфавитом Σ, а действие струн расширяет действие Σ посредством свойства

$T_{vw}=T_{w}\circ T_{v}.$

Теория Крона-Родса

Основная статья: теория Крона – Родса

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

Ссылки

• А. Х. Клиффорд и ГБ Престон (1961), Алгебраическая теория полугрупп , том 1. Американское математическое общество, ISBN   978-0-8218-0272-4 .
• А. Х. Клиффорд и ГБ Престон (1967), Алгебраическая теория полугрупп , том 2. Американское математическое общество, ISBN   978-0-8218-0272-4 .
• Мати Килп, Ульрих Кнауэр, Александр В. Михалев (2000), Моноиды, действия и категории: с приложениями к сплетениям и графам , Изложения по математике 29 , Вальтер де Грюйтер, Берлин, ISBN   978-3-11-015248-7 .
• Рудольф Лидл и Гюнтер Пильц, Прикладная абстрактная алгебра (1998), Springer, ISBN   978-0-387-98290-8