Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

Teoria Automatów


Semigroup decomposition and semigroup transformers

Prelegent: Michał Gajda

2023-07-05 14:15

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.