Decidability of Krohn-Rhodes complexity $c = 1$ of finite semigroups and automata
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911621991890944 |
|---|---|
| author | Margolis, Stuart Rhodes, John Schilling, Anne |
| author_facet | Margolis, Stuart Rhodes, John Schilling, Anne |
| contents | When decomposing a finite semigroup into a wreath product of groups and aperiodic semigroups, complexity measures the minimal number of groups that are needed. Determining an algorithm to compute complexity has been an open problem for almost 60 years. The main result of this paper proves decidability of Krohn-Rhodes complexity $c = 1$ of finite semigroups and automata. This is achieved by showing the lower bounds in work by Henckell, Rhodes and Steinberg from 2012 is sharp using profinite methods and results of McCammond from 1991 and 2001. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2110_10373 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Decidability of Krohn-Rhodes complexity $c = 1$ of finite semigroups and automata Margolis, Stuart Rhodes, John Schilling, Anne Group Theory Primary 20M07, 20M10, 20M20, Secondary 54H15 When decomposing a finite semigroup into a wreath product of groups and aperiodic semigroups, complexity measures the minimal number of groups that are needed. Determining an algorithm to compute complexity has been an open problem for almost 60 years. The main result of this paper proves decidability of Krohn-Rhodes complexity $c = 1$ of finite semigroups and automata. This is achieved by showing the lower bounds in work by Henckell, Rhodes and Steinberg from 2012 is sharp using profinite methods and results of McCammond from 1991 and 2001. |
| title | Decidability of Krohn-Rhodes complexity $c = 1$ of finite semigroups and automata |
| topic | Group Theory Primary 20M07, 20M10, 20M20, Secondary 54H15 |
| url | https://arxiv.org/abs/2110.10373 |