Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2021
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2111.07551 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
Inhaltsangabe:
- 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.