EUVIMEDEUVIMED entdecken
Crossref

Computing Embeddings and Isomorphisms of Finite Semigroups (extended version)

James East, Attila Egri-Nagy, Andrew R. Francis, James D. Mitchell

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →