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

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

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

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

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

• 1 Формальные определения
  • 1.1 Терминология и обозначения
  • 1.2 Действия и преобразования
  • 1.3 S-гомоморфизмы
  • 1.4 S-Act и M-Act
• 2 Примеры
• 3 Полугруппы преобразований
• 4 Приложения к информатике
  • 4.1 Полуавтоматы
  • 4.2 Теория Крона – Родса
• 5 Примечания
• 6 Ссылки

Пусть S - полугруппа. Тогда (слева) полугрупповое действие (или act ) группы 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 - моноид, то (левое) действие моноида (или act ) M является (левым) полугрупповым действием M с дополнительным свойством что

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

, где e - единичный элемент M. Это, соответственно, дает гомоморфизм моноида. Аналогично определяются действия правого моноида. Моноид 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\; \{\backslash \; displaystyle\; T\}$, для обозначения функции

$T:\; S\; \times \; X\; \to \; X\; \{\backslash \; displaystyle\; T\; \backslash \; двоеточие\; S\; \backslash \; times\; X\; \backslash \; to\; X\}$

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

$T\; s:\; X\; \to \; X\; \{\backslash \; displaystyle\; T\_\; \{s\}\; \backslash \; двоеточие\; X\; \backslash \; to\; X\}$

преобразование $X\; \{\backslash \; displaystyle\; X\}$, определяемое как

$T\; s\; (x)\; =\; T\; (s,\; x).\; \{\backslash \; displaystyle\; T\_\; \{s\}\; (x)\; =\; T\; (s,\; x).\}$

По определяющему свойству $S\; \{\backslash \; displaystyle\; S\}$-act, $T\; \{\backslash \; displaystyle\; T\}$удовлетворяет

$T\; s\; \ast \; t\; =\; T\; s\; \circ \; T\; t.\; \{\backslash \; displaystyle\; T\_\; \{s\; *\; t\}\; =\; T\_\; \{s\}\; \backslash \; circ\; T\_\; \{t\}.\}$

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

$curry\; (T)\; (s\; \ast \; t)\; =\; curry\; (T)\; (s)\; \circ \; curry\; (T)\; (t).\; \{\backslash \; displaystyle\; curry\; (T)\; (s\; *\; t)\; =\; curry\; (T)\; (s)\; \backslash \; circ\; curry\; (T)\; (t).\}$

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

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

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

$F:\; X\; \to \; X\; \prime \; \{\backslash \; displaystyle\; F\; \backslash \; двоеточие\; X\; \backslash \; to\; X\; \text{'}\}$

такое, что

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

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

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

S-Act и M-Act

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

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

• Любая полугруппа $(S,\; \ast )\; \{\backslash \; displaystyle\; (S,\; *)\}$имеет действие на $S\; \{\backslash \; displaystyle\; S\}$, где $\cdot \; =\; \ast \; \{\backslash \; displaystyle\; \backslash \; cdot\; =\; *\}$. Свойство действия сохраняется благодаря ассоциативности $\ast \; \{\backslash \; displaystyle\; *\}$.
• В более общем смысле, для любого гомоморфизма полугрупп $F:\; (S,\; \ast )\; \to \; (T,\; \oplus )\; \{\backslash \; displaystyle\; F\; \backslash \; двоеточие\; (S,\; *)\; \backslash \; rightarrow\; (T,\; \backslash \; oplus)\}$, полугруппа $(S,\; *)\; \{\backslash \; displaystyle\; (S,\; *)\}$действует на $T\; \{\backslash \; displaystyle\; T\}$, задаваемый $s\; \cdot \; t\; =\; F\; (s)\; \oplus \; t\; \{\backslash \; displaystyle\; s\; \backslash \; cdot\; t\; =\; F\; (s)\; \backslash \; oplus\; t\}$.
• для любой набор $X\; \{\backslash \; displaystyle\; X\}$, пусть $X\; \ast \; \{\backslash \; displaystyle\; X\; ^\; \{*\}\}$будет набором последовательностей элементов $Икс\; \{\backslash \; Displaystyle\; X\}$. Полугруппа $(N,\; \times )\; \{\backslash \; displaystyle\; (\backslash \; mathbb\; \{N\},\; \backslash \; times)\}$имеет действие на $X\; \ast \; \{\backslash \; displaystyle\; X\; ^\; \{*\}\}$задается $n\; \cdot \; s\; =\; sn\; \{\backslash \; displaystyle\; n\; \backslash \; cdot\; s\; =\; s\; ^\; \{n\}\}$(где $sn\; \{\backslash \; displaystyle\; s\; ^\; \{n\}\}$обозначает $s\; \{\backslash \; displaystyle\; s\}$повторяется $n\; \{\backslash \; displaystyle\; n\}$раз).

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

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

И наоборот, для любого действия полугруппы $T\; \{\backslash \; displaystyle\; T\}$из $S\; \{\backslash \; displaystyle\; S\}$на $X\; \{\backslash \; displaystyle\; X\}$, определить полугруппу преобразований $S\; \prime \; Знак\; равно\; \{T\; s\; \mid \; s\; \in \; S\}\; \{\backslash \; displaystyle\; S\; \text{'}=\; \backslash \; \{T\_\; \{s\}\; \backslash \; mid\; s\; \backslash \; in\; S\; \backslash \}\}$. В этой конструкции мы «забываем» набор $S\; \{\backslash \; displaystyle\; S\}$. $S\; \prime \; \{\backslash \; displaystyle\; S\; \text{'}\}$, равный изображению из $карри\; (T)\; \{\backslash \; displaystyle\; curry\; (T)\}$. Для краткости обозначим $c\; u\; r\; r\; y\; (T)\; \{\backslash \; displaystyle\; curry\; (T)\}$как $f\; \{\backslash \; displaystyle\; f\}$. Если $curry\; (T)\; \{\backslash \; displaystyle\; curry\; (T)\}$равно injective, то $f\; \{\backslash \; displaystyle\; f\}$является полугруппой изоморфизм от $S\; \{\backslash \; displaystyle\; S\}$до $S\; \text{'}\{\backslash \; displaystyle\; S\text{'}\}$. Другими словами, если $T\; \{\backslash \; displaystyle\; T\}$верен, мы не забываем ничего важного. Это утверждение уточняется следующим наблюдением: если мы превратим $S\; \prime \; \{\backslash \; displaystyle\; S\; \text{'}\}$обратно в действие полугруппы $T\; \prime \; \{\backslash \; displaystyle\; T\text{'}\}$из $S\; \prime \; \{\backslash \; displaystyle\; S\; \text{'}\}$на $X\; \{\backslash \; displaystyle\; X\}$, затем $T\; \prime \; (f\; (s),\; x)\; =\; T\; (s,\; x)\; \{\backslash \; displaystyle\; T\; \text{'}(f\; (s),\; x)\; =\; T\; (s,\; x)\}$для всех $s\; \in \; S,\; x\; \in \; X\; \{\backslash \; displaystyle\; s\; \backslash \; in\; S,\; x\; \backslash \; in\; X\}$. $T\; \{\backslash \; displaystyle\; T\}$и $T\; \prime \; \{\backslash \; displaystyle\; T\; \text{'}\}$«изоморфны» через $f\; \{\backslash \; displaystyle\; f\}$, т.е. мы фактически восстановили $T\; \{\backslash \; displaystyle\; T\}$. Таким образом, некоторые авторы не видят различия между точными действиями полугруппы и полугруппами преобразований.

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

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

$T\; :\; \Sigma \; \times \; X\; \to \; X\; \{\backslash \; Displaystyle\; T\; \backslash \; двоеточие\; \backslash \; Sigma\; \backslash \; times\; X\; \backslash \; to\; X\}$

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

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

$T\; vw\; =\; Т\; ш\; \circ \; Т\; v.\; \{\backslash \; displaystyle\; T\_\; \{vw\}\; =\; T\_\; \{w\}\; \backslash \; circ\; T\_\; \{v\}.\}$

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

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

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