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

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

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

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

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

Формальные определения [ править ]

Пусть 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 -акта с тождеством. ^[1]

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

Также довольно часто приходится работать с правыми действиями, а не с левыми действиями. ^[2]Однако каждое правое 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$ . Таким образом, некоторые авторы ^[3] не видят различия между точными действиями полугрупп и полугруппами преобразований.

Приложения к информатике [ править ]

Полуавтоматы [ править ]

Полугруппы преобразований имеют существенное значение для структурной теории конечных автоматов автоматов теории . В частности, полуавтомат — это тройка (Σ, 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 , где Σ ^∗ – свободный моноид строк, порожденный алфавитом Σ, ^{[примечание 1]} а действие струн расширяет действие Σ посредством свойства

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

Теория Крона-Родса [ править ]

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

Примечания [ править ]

^ Операция моноида — это конкатенация; элементом идентификации является пустая строка.

Ссылки [ править ]

^ Килп, Кнауэр и Михалев, 2000, страницы 43–44.
^ Килп, Кнауэр и Михалев, 2000.
^ Арбиб, Майкл А., изд. (1968). Алгебраическая теория машин, языков и полугрупп . Нью-Йорк и Лондон: Академическая пресса. п. 83.

А. Х. Клиффорд и ГБ Престон (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

[4] Операция моноида — это конкатенация; элементом идентификации является пустая строка.

[1] Килп, Кнауэр и Михалев, 2000, страницы 43–44.

[2] Килп, Кнауэр и Михалев, 2000.

[3] Арбиб, Майкл А., изд. (1968). Алгебраическая теория машин, языков и полугрупп . Нью-Йорк и Лондон: Академическая пресса. п. 83.

[1]

[2]

[3]

[примечание 1]