Geodesic
Merge Decompositions, Two-sided Krohn–Rhodes, and Aperiodic Pointlikes
Canadian mathematical bulletin, Tome 62 (2019) no. 1, pp. 199-208

Voir la notice de l'article provenant de la source Cambridge University Press

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. We use 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_{1}T_{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.
DOI : 10.4153/CMB-2018-014-8
Mots-clés : Krohn-Rhodes theorem, aperiodic pointlikes 
Gool, Samuel J. van; Steinberg, Benjamin. Merge Decompositions, Two-sided Krohn–Rhodes, and Aperiodic Pointlikes. Canadian mathematical bulletin, Tome 62 (2019) no. 1, pp. 199-208. doi: 10.4153/CMB-2018-014-8
@article{10_4153_CMB_2018_014_8,
     author = {Gool, Samuel J. van and Steinberg, Benjamin},
     title = {Merge {Decompositions,} {Two-sided} {Krohn{\textendash}Rhodes,} and {Aperiodic} {Pointlikes}},
     journal = {Canadian mathematical bulletin},
     pages = {199--208},
     year = {2019},
     volume = {62},
     number = {1},
     doi = {10.4153/CMB-2018-014-8},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CMB-2018-014-8/}
}
TY  - JOUR
AU  - Gool, Samuel J. van
AU  - Steinberg, Benjamin
TI  - Merge Decompositions, Two-sided Krohn–Rhodes, and Aperiodic Pointlikes
JO  - Canadian mathematical bulletin
PY  - 2019
SP  - 199
EP  - 208
VL  - 62
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CMB-2018-014-8/
DO  - 10.4153/CMB-2018-014-8
ID  - 10_4153_CMB_2018_014_8
ER  - 
%0 Journal Article
%A Gool, Samuel J. van
%A Steinberg, Benjamin
%T Merge Decompositions, Two-sided Krohn–Rhodes, and Aperiodic Pointlikes
%J Canadian mathematical bulletin
%D 2019
%P 199-208
%V 62
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4153/CMB-2018-014-8/
%R 10.4153/CMB-2018-014-8
%F 10_4153_CMB_2018_014_8

[1] Almeida, J., Some algorithmic problems for pseudovarieties . Publ. Math. Debrecen 54(1999), no. suppl., 531–552. Google Scholar

[2] Auinger, K. and Steinberg, B., On the extension problem for partial permutations . Proc. Amer. Math. Soc. 131(2003), no. 9, 2693–2703. . Google Scholar | DOI

[3] Eilenberg, S., Automata, languages, and machines. Vol. B. Pure and Applied Mathematics, 59, Academic Press, New York, 1976. Google Scholar

[4] Gool, S. J. V. and Steinberg, B., Pointlike sets for varieties determined by groups. 2018. arxiv:1801.04638. Google Scholar

[5] Henckell, K., Pointlike sets: the finest aperiodic cover of a finite semigroup . J. Pure Appl. Algebra 55(1988), 85–126. . Google Scholar | DOI

[6] Henckell, K., Lazarus, S., and Rhodes, J., Prime decomposition theorem for arbitrary semigroups: general holonomy decomposition and synthesis theorem . J. Pure Appl. Algebra 55(1988), no. 1–2, 127–172. . Google Scholar | DOI

[7] Henckell, K., Rhodes, J., and Steinberg, B., Aperiodic pointlikes and beyond . Internat. J. Algebra Comput. 20(2010), no. 2, 287–305. . Google Scholar | DOI

[8] Krohn, K. and Rhodes, J., Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines . Trans. Amer. Math. Soc. 116(1965), 450–464. . Google Scholar | DOI

[9] Krohn, K., Rhodes, J., and Tilson, B., Algebraic theory of machines, languages, and semigroups. Academic Press, New York, 1968. Google Scholar

[10] Lee, E. W. H., Rhodes, J., and Steinberg, B., Join irreducible semigroups. 2017. arxiv:1702.03753. Google Scholar

[11] Place, T. and Zeitoun, M., Separating regular languages with first-order logic . Log. Methods Comput. Sci. 12(2016), Paper no. 5. . Google Scholar | DOI

[12] Rhodes, J. and Steinberg, B., Pointlike sets, hyperdecidability and the identity problem for finite semigroups . Internat. J. Algebra Comput. 9(1999), no. 3–4, 475–481. . Google Scholar | DOI

[13] Rhodes, J. and Steinberg, B., The q-theory of finite semigroups. Springer Monographs in Mathematics, Springer, New York, 2009. Google Scholar

[14] Steinberg, B., A strange two-variable recursion. MathOverflow question, answered by M. Fischler. https://mathoverflow.net/q/278517. Google Scholar

[15] Steinberg, B., On pointlike sets and joins of pseudovarieties . Internat. J. Algebra Comput. 8(1998), no. 2, 203–234. . Google Scholar | DOI

[16] Straubing, H., Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science, Birkhäuser Boston Inc., Boston, MA, 1994. . Google Scholar | DOI

[17] Wilke, T., Classifying discrete temporal properties . In: STACS’99, Lecture Notes. in Computer Science, 1563, Springer, 1999, pp. 32–46. . Google Scholar | DOI

Cité par Sources :