Полугруппа трансформации

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Представление Кэли

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

Для полугруппы S без (левого или правого) единичного элемента мы берем X в качестве основного множества моноида, соответствующего S, чтобы реализовать S как полугруппу преобразований X . В частности, любую конечную полугруппу можно представить как подполугруппу преобразований множества X с | Х | ≤ | С | + 1, и если S — моноид, мы имеем более точную оценку | Х | ≤ | S |, как и в случае конечных групп .

В информатике

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

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

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

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

См. также

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

Ссылки

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