On the Complexity of Properties of Transformation Semigroups
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2018
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909401424592896 |
|---|---|
| author | Fleischer, Lukas Jack, Trevor |
| author_facet | Fleischer, Lukas Jack, Trevor |
| contents | We investigate the computational complexity for determining various properties of a finite transformation semigroup given by generators. We introduce a simple framework to describe transformation semigroup properties that are decidable in $\mathsf{AC^0}$. This framework is then used to show that the problems of deciding whether a transformation semigroup is a group, commutative or a semilattice are in $\mathsf{AC^0}$. Deciding whether a semigroup has a left (resp.right) zero is shown to be $\mathsf{NL}$-complete, as are the problems of testing whether a transformation semigroup is nilpotent, $\mathcal{R}$-trivial or has central idempotents. We also give $\mathsf{NL}$ algorithms for testing whether a transformation semigroup is idempotent, orthodox, completely regular, Clifford or has commuting idempotents. Some of these algorithms are direct consequences of the more general result that arbitrary fixed semigroup equations can be tested in~$\mathsf{NL}$. Moreover, we show how to compute left and right identities of a transformation semigroup in polynomial time. Finally, we show that checking whether an element is regular is $\mathsf{PSPACE}$-complete. \ |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1811_00060 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | On the Complexity of Properties of Transformation Semigroups Fleischer, Lukas Jack, Trevor Group Theory 20M20 We investigate the computational complexity for determining various properties of a finite transformation semigroup given by generators. We introduce a simple framework to describe transformation semigroup properties that are decidable in $\mathsf{AC^0}$. This framework is then used to show that the problems of deciding whether a transformation semigroup is a group, commutative or a semilattice are in $\mathsf{AC^0}$. Deciding whether a semigroup has a left (resp.right) zero is shown to be $\mathsf{NL}$-complete, as are the problems of testing whether a transformation semigroup is nilpotent, $\mathcal{R}$-trivial or has central idempotents. We also give $\mathsf{NL}$ algorithms for testing whether a transformation semigroup is idempotent, orthodox, completely regular, Clifford or has commuting idempotents. Some of these algorithms are direct consequences of the more general result that arbitrary fixed semigroup equations can be tested in~$\mathsf{NL}$. Moreover, we show how to compute left and right identities of a transformation semigroup in polynomial time. Finally, we show that checking whether an element is regular is $\mathsf{PSPACE}$-complete. \ |
| title | On the Complexity of Properties of Transformation Semigroups |
| topic | Group Theory 20M20 |
| url | https://arxiv.org/abs/1811.00060 |