В алгебре и теоретической информатике , в действии или действовать из полугруппы на множестве правило , которое сопоставляет каждый элемент полугруппы преобразований множества таким образом , что произведение двух элементов полугруппы ( с использованием Полугруппы операция ) связана с композицией двух соответствующих преобразований. Терминология передает идею о том, что элементы полугруппы действуют как преобразования множества. С алгебраической точки зрения действие полугруппы является обобщением понятиягрупповое действие в теории групп . С точки зрения информатики, полугрупповые действия тесно связаны с автоматами : набор моделирует состояние автомата, а действия моделируют преобразования этого состояния в ответ на входные данные.
Важный частный случай является моноидным действием или действия , в котором полугруппа является моноид , а единичный элемент моноида действует как тождественное преобразование множества. С теоретико-категориальной точки зрения моноид - это категория с одним объектом, а действие - это функтор из этой категории в категорию множеств . Это сразу же обеспечивает обобщение моноидных воздействий на объекты в категориях, отличных от категории множеств.
Другой важный частный случай - полугруппа преобразований . Это полугруппа преобразований множества, и, следовательно, она имеет тавтологическое действие на этом множестве. Это понятие связано с более общим понятием полугруппы аналогом теоремы Кэли .
(Примечание по терминологии: терминология, используемая в этой области, варьируется, иногда значительно, от одного автора к другому. Подробнее см. В статье.)
Формальные определения
Пусть 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
где е представляет единичный элемент М . Это соответственно дает гомоморфизм моноида. Аналогично определяются действия правого моноида. Моноид M с действием на множестве также называется операторным моноидом .
Действие полугруппы S на X может быть сделано в моноидный акт присоединения единицы к полугруппе и требуя , чтобы она действует как тождественное преобразование на X .
Терминология и обозначения
Если S - полугруппа или моноид, то множество X, на котором S действует, как указано выше (например, слева), также известно как (левое) S -акт , S -множество , S- действие , S -операция или левое действие над S . Некоторые авторы не различают полугрупповые и моноидные действия, рассматривая аксиому тождества ( e • x = x ) как пустую, когда нет элемента идентичности, или используя термин унитарный S -акт для S -акт с тождеством. [1]
Определяющее свойство действия аналогично ассоциативности операции полугруппы и означает, что все круглые скобки могут быть опущены. Обычной практикой, особенно в информатике, является также пропуск операций, так что и операция полугруппы, и действие указываются сопоставлением. Таким образом , строки писем от S действуют на X , так как в выражении STX для х , т в С и х в X .
Также довольно часто работают с правыми действиями, а не с левыми. [2] Однако каждый правый S-акт можно интерпретировать как левый акт над противоположной полугруппой , которая имеет те же элементы, что и S, но где умножение определяется обращением множителей, s • t = t • s , поэтому два понятия по существу эквивалентны. Здесь мы в первую очередь принимаем точку зрения левых действий.
Акты и трансформации
Часто удобно (например, если рассматривается более одного действия) использовать букву, например , для обозначения функции
определение -action и, следовательно, написать на месте . Тогда для любого в , обозначим через
преобразование определяется
По определяющему свойству -действовать, удовлетворяет
Далее рассмотрим функцию . Это то же самое, что и(см. Каррирование ). Так как является биекцией, действия полугруппы можно определить как функции что удовлетворяет
Это, является полугрупповым действием на если и только если является гомоморфизмом полугрупп из к моноиду полного преобразования .
S -гомоморфизмы
Пусть X и X ′ - S -акты. Тогда S -гомоморфизм из X в X ′ - это отображение
такой, что
- для всех а также .
Множество всех таких S -гомоморфизмов обычно записывается как.
Точно так же определяются M -гомоморфизмы M -актов для M моноида.
S -Act и M -Act
Для фиксированной полугруппы S левые S -акты являются объектами категории, обозначаемой S -Act, морфизмы которой являются S -гомоморфизмами. Соответствующую категорию правых S -актов иногда обозначают Act- S . (Это аналогично категориям R -Mod и Mod- R левого и правого модулей над кольцом .)
Для моноида M категории M -Act и Act- M определяются таким же образом.
Примеры
- Любая полугруппа имеет действие на , где . Свойство действия сохраняется благодаря ассоциативности.
- В более общем смысле, для любого гомоморфизма полугрупп , полугруппа имеет действие на дано .
- Для любого набора , позволять - множество последовательностей элементов . Полугруппа имеет действие на дано (где обозначает повторяется раз).
- Полугруппа имеет правильное действие , данный .
Полугруппы преобразований
Соответствие между полугруппами преобразований и действиями полугруппы описано ниже. Если мы ограничиваем его верные действия полугрупповых, он имеет хорошие свойства.
Любую полугруппу преобразований можно превратить в действие полугруппы с помощью следующей конструкции. Для любой полугруппы преобразований из , определим действие полугруппы из на в виде для . Это действие является верным, что эквивалентнобыть инъективным .
Наоборот, для любого действия полугруппы из на , определим полугруппу преобразований . В этой конструкции мы «забываем» множество. равно образом из. Обозначим в виде для краткости. Еслиявляется инъективным , то полугруппа изоморфизм из к . Другими словами, есливерен, то ничего важного не забываем. Это утверждение уточняется следующим наблюдением: если мы обратимся вернуться в действие полугруппы из на , тогда для всех . а также "изоморфны" через , т. е. мы практически восстановили . Таким образом, некоторые авторы [3] не видят различия между точными действиями полугруппы и полугруппами преобразований.
Приложения к информатике
Полуавтоматы
Полугруппы преобразований имеют существенное значение для структурной теории конечных автоматов в теории автоматов . В частности, полуавтомат - это тройка ( Σ , X , T ), где Σ - непустое множество, называемое входным алфавитом , X - непустое множество, называемое множеством состояний, а T - функция
называется функцией перехода . Полуавтоматы возникают из детерминированных автоматов , игнорируя начальное состояние и набор принимаемых состояний.
Для полуавтомата обозначим через T a : X → X для a ∈ Σ преобразование X, определяемое формулой T a ( x ) = T ( a , x ). Тогда полугруппа преобразований X, порожденная { T a : a ∈ Σ }, называется характеристической полугруппой или системой переходов ( Σ , X , T ). Эта полугруппа является моноидом, поэтому этот моноид называется характеристическим или переходным моноидом . Иногда его также рассматривают как Σ ∗ -акт на X , где Σ ∗ - свободный моноид строк, порожденный алфавитом Σ , [примечание 1], а действие строк расширяет действие Σ посредством свойства
Теория Крона – Родса
Теория Крона – Родса, иногда также называемая теорией алгебраических автоматов , дает сильные результаты декомпозиции для полугрупп конечных преобразований путем каскадирования более простых компонентов.
Заметки
- ^ Операция моноида - это конкатенация; элементом идентичности является пустая строка.
Рекомендации
- А. Х. Клиффорд и Дж. Б. Престон (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