Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2111.07551 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929602506522624 |
|---|---|
| author | Jack, Trevor |
| author_facet | Jack, Trevor |
| contents | We investigate the computational complexity of various decision problems related to conjugacy in finite inverse semigroups. We describe polynomial-time algorithms for checking if two elements in such a semigroup are ~p conjugate and whether an inverse monoid is factorizable. We describe a connection between checking ~i conjugacy and checking membership in inverse semigroups. We prove that ~o and ~c are partition covering for any countable set and that ~p, ~p* , and ~tr are partition covering for any finite set. Finally, we prove that checking for nilpotency, R-triviality, and central idempotents in partial bijection semigroups are NL-complete problems and we extend several complexity results for partial bijection semigroups to inverse semigroups. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_07551 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | On the complexity of inverse semigroup conjugacy Jack, Trevor Group Theory We investigate the computational complexity of various decision problems related to conjugacy in finite inverse semigroups. We describe polynomial-time algorithms for checking if two elements in such a semigroup are ~p conjugate and whether an inverse monoid is factorizable. We describe a connection between checking ~i conjugacy and checking membership in inverse semigroups. We prove that ~o and ~c are partition covering for any countable set and that ~p, ~p* , and ~tr are partition covering for any finite set. Finally, we prove that checking for nilpotency, R-triviality, and central idempotents in partial bijection semigroups are NL-complete problems and we extend several complexity results for partial bijection semigroups to inverse semigroups. |
| title | On the complexity of inverse semigroup conjugacy |
| topic | Group Theory |
| url | https://arxiv.org/abs/2111.07551 |