Полугруппа преобразований
- Полугруппа преобразований — совокупность преобразований, замкнутая в соответствии с композицией функций.
- Моноид преобразования (или композиции) является полугрупповым аналогом группы перестановок.
- Полугруппа преобразования множества оказывает тавтологическое полугрупповое действие на это множество.
- Аналог теоремы Кэли показывает, что любая полугруппа может быть реализована как полугруппа преобразования некоторого множества.
- В теории автоматов термин «полугруппа преобразования» используется для обозначения полугруппы, действующей добросовестно в наборе «состояний».
- Полугруппы преобразований и моноиды являются важными понятиями в алгебре и теории автоматов.
- Представление Кэли обобщается на моноиды, утверждая, что любой моноид является моноидом преобразования своего базового множества.
- В информатике представления Кэли могут быть применены для повышения асимптотической эффективности полугрупп.
- Моноид преобразования автомата представляет собой полугруппу преобразований, связанную с детерминированным автоматом с пространством состояний и алфавитом.
Полный текст статьи: