Computing transformation semigroups

DOI10.1006/JSCO.2000.0406MaRDI QIDQ1599539zbMATH OpenOpenAlexFDO

Authors R. Smith

Publication date 11 June 2002

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jsco.2000.0406

zbMATH Keywords

algorithmscomputationfinite transformation semigroupsgeneralized Schützenberger groupsGreen relations

Mathematics Subject Classification ID

General structure theory for semigroups (20M10) Semigroups of transformations, relations, partitions, etc. (20M20) Representation of semigroups; actions of semigroups on sets (20M30) Symbolic computation and algebraic computation (68W30)

Review text

The paper describes data structures and algorithms for performing computations in a finite semigroup \(S\) with identity, generated by a set of transformations. A basic idea behind the algorithms is the partition of \(S\) with the aid of an equivalence relation \(\mathcal R\), one of Green's relations. The paper presents algorithms for performing global computations in \(S\) (like its size and structure), as well as local computations within an \(\mathcal R\)-class, without touching the rest of \(S\), thereby improving existing results by \textit{G. Lallement} and \textit{R. McFadden} [J. Symb. Comput. 10, No. 5, 481-498 (1990; Zbl 0792.20061)]. This approach is bound to result in more efficient computations. The algorithms have been implemented in the GAP computer algebra system, and are available as the share package MONOID. Examples of computations using MONOID are given in the paper.

Recommendations

• On the determination of Green's relations in finite transformation semigroups
• Computing finite semigroups
• Algorithms for computing finite semigroups
• Computing maximal subsemigroups of a finite semigroup
• Computing with semigroups in GAP. -- A tutorial

Cites work

• Groups and actions in transformation semigroups
• scientific article; zbMATH DE number 475362 (Why is no real title available?)
• scientific article; zbMATH DE number 789816 (Why is no real title available?)
• scientific article; zbMATH DE number 3341276 (Why is no real title available?)
• On the computational power of pushdown automata
• On the determination of Green's relations in finite transformation semigroups

Cited in

(18)

• On the determination of Green's relations in finite transformation semigroups
• On the representation of abstract semigroups by transformation semigroups: Computer investigations
• Enumerating transformation semigroups
• Some contributions to the theory of transformation monoids
• Computing finite semigroups
• Codecomposition of a transformation semigroup.
• Two variants of the Froidure-Pin algorithm for finite semigroups
• Computing with semigroups in GAP. -- A tutorial
• Two generalizations of homogeneity in groups with applications to regular semigroups
• scientific article; zbMATH DE number 3867604 (Why is no real title available?)
• A Method for Constructing Square Roots in Finite Full Transformation Semigroups
• Algorithms for computing finite semigroups
• A general approach for generating sets of certain subsemigroups of monotone maps
• Multiscale graph grammars can generate Cayley graphs of groups and monoids
• Mitigating covert channels based on analysis of the potential for communication
• Computing character tables and Cartan matrices of finite monoids with fixed point counting
• Groups that together with any transformation generate regular semigroups or idempotent generated semigroups.
• Minimum transformation representations of diagram monoids

Describes a project that uses

Uses Software

• MONOiD
• GAP

This page was built for publication: Computing transformation semigroups

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