Computing Embeddings and Isomorphisms of Finite Semigroups
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2016
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909996065751040 |
|---|---|
| author | East, James Egri-Nagy, Attila Francis, Andrew R. Mitchell, James D. |
| author_facet | East, James Egri-Nagy, Attila Francis, Andrew R. Mitchell, James D. |
| contents | Semigroup theory is a branch of abstract algebra, and it provides mathematical tools for the theory of computation. Finite semigroups can describe state transition systems and thus they model physically realizable computers. Engineering questions like `What is the minimal number of states to realize a particular computation?' and `Which type of computation is more capable?' translate into the algebraic tasks of constructing isomorphisms and embeddings between semigroups of different representations. The underlying problem is (sub)graph isomorphism, which is computationally difficult in general. We describe variations of backtrack search algorithms that exploit the algebraic properties of semigroups, and we carry out computational experiments to extend our algebraic knowledge. In particular, we report new computational results on transformation semigroups and on the more general family of diagram semigroups. We study the minimal degree representation problem, count distinct embeddings and work on an open problem of embedding into 2-generated subsemigroups. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1603_06204 |
| institution | arXiv |
| publishDate | 2016 |
| record_format | arxiv |
| spellingShingle | Computing Embeddings and Isomorphisms of Finite Semigroups East, James Egri-Nagy, Attila Francis, Andrew R. Mitchell, James D. Group Theory 20M35, 68Q70 Semigroup theory is a branch of abstract algebra, and it provides mathematical tools for the theory of computation. Finite semigroups can describe state transition systems and thus they model physically realizable computers. Engineering questions like `What is the minimal number of states to realize a particular computation?' and `Which type of computation is more capable?' translate into the algebraic tasks of constructing isomorphisms and embeddings between semigroups of different representations. The underlying problem is (sub)graph isomorphism, which is computationally difficult in general. We describe variations of backtrack search algorithms that exploit the algebraic properties of semigroups, and we carry out computational experiments to extend our algebraic knowledge. In particular, we report new computational results on transformation semigroups and on the more general family of diagram semigroups. We study the minimal degree representation problem, count distinct embeddings and work on an open problem of embedding into 2-generated subsemigroups. |
| title | Computing Embeddings and Isomorphisms of Finite Semigroups |
| topic | Group Theory 20M35, 68Q70 |
| url | https://arxiv.org/abs/1603.06204 |