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

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

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

Аналог теоремы Кэли показывает, что любую полугруппу можно реализовать как полугруппу преобразований некоторого множества.

В теории автоматов некоторые авторы используют термин «полугруппа преобразований» для обозначения полугруппы , действующей точно на множестве «состояний», отличном от базового множества полугруппы. ^[1] Между этими двумя понятиями существует соответствие .

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

Полугруппа преобразований — это пара ( X , S ), где X — множество, а S — полугруппа преобразований X. Здесь преобразование X — это просто функция из подмножества X в X , не обязательно обратимая, и поэтому S — это просто множество преобразований X , замкнутое относительно композиции функций . Множество всех частичных функций на заданном базовом множестве X образует регулярную полугруппу , называемую полугруппой всех частичных преобразований (или полугруппой частичных преобразований на X ), обычно обозначаемую как . ^[2] ${\displaystyle {\mathcal {PT}}_{X}}$

Если S включает в себя тождественное преобразование X , то оно называется моноидом преобразований . Очевидно, что любая полугруппа преобразований S определяет моноид преобразований M , взяв объединение S с тождественным преобразованием. Моноид преобразований, элементы которого обратимы, называется группой перестановок .

Множество всех преобразований X является моноидом преобразований, называемым полным моноидом преобразований (или полугруппой ) X. Он также называется симметрической полугруппой X и обозначается T _X. Таким образом, полугруппа преобразований (или моноид) является просто подполугруппой (или подмоноидом ) полного моноида преобразований X.

Если ( X , S ) — полугруппа преобразований, то X можно превратить в полугрупповое действие S с помощью вычисления:

${\displaystyle s\cdot x=s(x){\text{ for }}s\in S,x\in X.}$

Это моноидное действие, если S — моноид преобразования.

Характерной особенностью полугрупп преобразований, как действий, является то, что они точны , т.е. если

${\displaystyle s\cdot x=t\cdot x{\text{ for all }}x\in X,}$

тогда s = t . Наоборот, если полугруппа S действует на множестве X по формуле T ( s , x ) = s • x , то мы можем определить для s ∈ S преобразование T _s множества X по формуле

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

Отображение, переводящее s в T _s, инъективно тогда и только тогда, когда ( X ,  T ) является точным, и в этом случае образ этого отображения является полугруппой преобразований, изоморфной S .

Представительство Кейли

В теории групп теорема Кэли утверждает, что любая группа G изоморфна подгруппе симметрической группы G ( рассматриваемой как множество), так что G является группой перестановок . Эта теорема напрямую обобщается на моноиды: любой моноид M является моноидом преобразования своего базового множества посредством действия, заданного левым (или правым) умножением. Это действие является точным, потому что если ax = bx для всех x из M , то, приравнивая x к единичному элементу, мы имеем a = b .

Для полугруппы S без (левого или правого) элемента тождества мы берем X в качестве базового множества моноида, соответствующего S, чтобы реализовать S как полугруппу преобразований X. В частности, любая конечная полугруппа может быть представлена ​​как подполугруппа преобразований множества X с | X | ≤ | S | + 1, и если S является моноидом, мы имеем более точную границу | X | ≤ | S |, как в случае конечных групп . ^{[3] : 21}

В области компьютерных наук

В информатике представления Кэли могут применяться для улучшения асимптотической эффективности полугрупп путем повторного связывания нескольких составных умножений. Действие, заданное левым умножением, приводит к правоассоциированному умножению, и наоборот для действия, заданного правым умножением. Несмотря на одинаковые результаты для любой полугруппы, асимптотическая эффективность будет отличаться. Два примера полезных моноидов преобразований, заданных действием левого умножения, — это функциональная вариация структуры данных списка разностей и монадическое преобразование Codensity (представление Кэли монады , которая является моноидом в определенной категории моноидальных функторов ). ^[4]

Моноид преобразования автомата

Пусть M — детерминированный автомат с пространством состояний S и алфавитом A. Слова в свободном моноиде A ^∗ индуцируют преобразования S, приводящие к морфизму моноида из A ^∗ в полный моноид преобразований T _S. Образ этого морфизма — полугруппа преобразований M. [ ^{3] : 78}

Для регулярного языка синтаксический моноид изоморфен моноиду преобразования минимального автомата языка. ^{[3] : 81}

Смотрите также

• Полуавтомат
• Теория Крона–Роудса
• Симметричная обратная полугруппа
• Биоупорядоченное множество
• Специальные классы полугрупп
• Композиция кольца

Ссылки

1. Доминик Перрен; Жан Эрик Пин (2004). Бесконечные слова: автоматы, полугруппы, логика и игры. Academic Press. стр. 448. ISBN 978-0-12-532111-2.
2. Альфред Хоблицелл Клиффорд; GB Preston (1967). Алгебраическая теория полугрупп. Том II. Американское математическое общество. стр. 254. ISBN 978-0-8218-0272-4.
3. Андерсон, Джеймс А. (2006). Теория автоматов с современными приложениями . С участием Тома Хэда. Кембридж: Cambridge University Press . doi :10.1017/CBO9780511607202. ISBN 978-0-521-61324-8. Збл  1127.68049.
4. Ривас, Экзекиель; Джаскелиофф, Мауро (2017). « Понятия вычислений как моноидов ». Журнал функционального программирования . 27 (e21). arXiv : 1406.4823 . doi : 10.1017/S0956796817000132.

• Клиффорд, А. Х.; Престон, ГБ (1961). Алгебраическая теория полугрупп. Том I. Математические обзоры. Том 7. Провиденс, Род-Айленд: Американское математическое общество . ISBN 978-0-8218-0272-4. Збл  0111.03403.
• Хауи, Джон М. (1995). Основы теории полугрупп . Монографии Лондонского математического общества. Новая серия. Том 12. Оксфорд: Clarendon Press . ISBN 978-0-19-851194-6. Збл  0835.20077.
• Мати Килп, Ульрих Кнауэр, Александр В. Михалёв (2000), Моноиды, акты и категории: с приложениями к сплетенным произведениям и графам , Expositions in Mathematics 29 , Вальтер де Грюйтер, Берлин, ISBN 978-3-11-015248-7 .