Nie jesteś zalogowany | Zaloguj się

Semigroup decomposition and semigroup transformers

Prelegent(ci)
Michał Gajda
Afiliacja
MigaMake Pte Ltd, Singapur
Termin
5 lipca 2023 14:15
Pokój
p. 5050
Seminarium
Seminarium „Teoria automatów”

Krohn-Rhodes theorem claims that every semigroup can be decomposed into finite groups, and aperiodic semigroups. This theorem has been generalized from finite semigroups to infinite ones, but uses a hairy construct of a wreath product, and is rather hard to follow in its full grace (over hundred pages). We propose an alternative decomposition of semigroups. We start with prime automata and semiautomata, then prime transducers (or monoid transudcers). We propose a decomposition of semigroups into prime transducers. We use this decomposition that every finite (prime) semigroup may be "rebuilt" as an injective semigroup, that is one that is strictly injective on the output. If time permits, I will also mention "rebuilding" of a semigroup to make it monotonic according to monoidal preorders, and differentiation, and semigroup descent algorithm.