Computing Embeddings and Isomorphisms of Finite Semigroups (extended version)
International Journal of Networking and Computing · 2026 · 16 (2) · 147-165
DOI: 10.15803/ijnc.16.2_147 ↗Kurz gefasst
Fachartikel in der Zeitschrift International Journal of Networking and Computing, 2026. Verfasst von James East und 3 weiteren Autor:innen. Die Arbeit nennt 43 Literaturangaben.
Abstract (Originalsprache)
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, various improvements and optimizations. 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 for three types of diagram semigroups and work on an open problem of embedding into 2-generated subsemigroups.
Zitieren
APA
East, J., Egri-Nagy, A., Francis, A. R., & Mitchell, J. D. (2026). Computing Embeddings and Isomorphisms of Finite Semigroups (extended version). International Journal of Networking and Computing, 16(2), 147-165. https://doi.org/10.15803/ijnc.16.2_147
Vancouver
East J, Egri-Nagy A, Francis AR, Mitchell JD. Computing Embeddings and Isomorphisms of Finite Semigroups (extended version). International Journal of Networking and Computing. 2026;16(2):147-165. doi:10.15803/ijnc.16.2_147
BibTeX
@article{East2026,
author = {East, James and Egri-Nagy, Attila and Francis, Andrew R. and Mitchell, James D.},
title = {Computing Embeddings and Isomorphisms of Finite Semigroups (extended version)},
journal = {International Journal of Networking and Computing},
year = {2026},
volume = {16},
number = {2},
pages = {147--165},
doi = {10.15803/ijnc.16.2_147}
}
EUVIMED