Semigroup decomposition and semigroup transformers

Speaker(s)

Michał Gajda

Affiliation

MigaMake Pte Ltd, Singapur

Date

July 5, 2023, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

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.

---