CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
  location:  PublicationsjournalsCMB
Publications        
Abstract view

Merge decompositions, two-sided Krohn-Rhodes, and aperiodic pointlikes

  • Benjamin Steinberg,
    Department of Mathematics, City College of New York , New York, New York 10031, USA
  • Samuel J. van Gool,
    Department of Mathematics, City College of New York , New York, New York 10031, USA
Format:   LaTeX   MathJax  

Abstract

This paper provides short proofs of two fundamental theorems of finite semigroup theory whose previous proofs were significantly longer, namely the two-sided Krohn-Rhodes decomposition theorem and Henckell's aperiodic pointlike theorem, using a new algebraic technique that we call the merge decomposition. A prototypical application of this technique decomposes a semigroup $T$ into a two-sided semidirect product whose components are built from two subsemigroups $T_1,T_2$, which together generate $T$, and the subsemigroup generated by their setwise product $T_1T_2$. In this sense we decompose $T$ by merging the subsemigroups $T_1$ and $T_2$. More generally, our technique merges semigroup homomorphisms from free semigroups.
Keywords: Krohn-Rhodes theorem, aperiodic pointlikes Krohn-Rhodes theorem, aperiodic pointlikes
MSC Classifications: 20M07, 20M35, 68Q70 show english descriptions Varieties and pseudovarieties of semigroups
Semigroups in automata theory, linguistics, etc. [See also 03D05, 68Q70, 68T50]
Algebraic theory of languages and automata [See also 18B20, 20M35]
20M07 - Varieties and pseudovarieties of semigroups
20M35 - Semigroups in automata theory, linguistics, etc. [See also 03D05, 68Q70, 68T50]
68Q70 - Algebraic theory of languages and automata [See also 18B20, 20M35]
 

© Canadian Mathematical Society, 2018 : https://cms.math.ca/