Random ubiquitous transformation semigroups

DOI10.1007/S00233-018-09992-7MaRDI QIDQ2009658zbMATH OpenOpenAlexFDO

Authors J. Jonušas, Sascha Troscheit

Publication date 29 November 2019

Published in Semigroup Forum (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1705.05709

zbMATH Keywords

asymptotic behaviortransformation monoidscomputational semigroup theory

Mathematics Subject Classification ID

Semigroups of transformations, relations, partitions, etc. (20M20) Free semigroups, generators and relations, word problems (20M05)

Abstract: A smallest generating set of a semigroup is a generating set of the smallest cardinality. Similarly, an irredundant generating set $X$ is a generating set such that no proper subset of $X$ is also a generating set. A semigroup $S$ is ubiquitous if every irredundant generating set of $S$ is of the same cardinality. We are motivated by a na"{i}ve algorithm to find a small generating set for a semigroup, which in practice often outputs a smallest generating set. We give a sufficient condition for a transformation semigroup to be ubiquitous and show that a transformation semigroup generated by $k$ randomly chosen transformations asymptoticly satisfies the sufficient condition. Finally, we show that under this condition the output of the previously mentioned na"{i}ve algorithm is irredundant.

Recommendations

• Generating sets of the semigroup \(K(n,r)\)
• On the semigroup of transformations of a finite set generated by random generators*
• Generating sets of finite transformation semigroups \(PK(n,r)\) and \(K(n,r)\).
• Generators and factorisations of transformation semigroups
• Irreducible generating sets of complete semigroups of unions.

Cites work

• scientific article; zbMATH DE number 789816 (Why is no real title available?)
• Algorithms for computing finite semigroups
• Computing finite semigroups
• Dixon's theorem and random synchronization
• On limited nondeterminism and the complexity of the V-C dimension
• On the Lambert \(w\) function
• On the ranks of certain finite semigroups of transformations
• On the ranks of certain semigroups of order-preserving transformations
• The Complexity of Quasigroup Isomorphism and the Minimum Generating Set Problem
• The minimal number of generators of a finite semigroup.
• Two variants of the Froidure-Pin algorithm for finite semigroups

Describes a project that uses

Uses Software

• Semigroups
• Smallsemi
• GAP

This page was built for publication: Random ubiquitous transformation semigroups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2009658)