Random ubiquitous transformation semigroups

DOI10.1007/S00233-018-09992-7zbMATH Open1467.20087arXiv1705.05709OpenAlexW2615856205MaRDI QIDQ2009658FDOQ2009658

Authors: J. Jonušas, Sascha Troscheit 

Publication date: 29 November 2019

Published in: Semigroup Forum (Search for Journal in Brave)

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.

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

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.

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)

Cites Work

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

Uses Software

• GAP
• Smallsemi
• Semigroups

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)