Digraphs and the semigroup of all functions on a finite set. (English) Zbl 0634.20034

Let \(T_ n\) denote the full transformation semigroup on the finite set \(\bar n=\{1,2,...,n\}\); that is the set of all selfmaps on \(\bar n\) under composition. In a previous paper [Can. Math. Bull. 29, 344-351 (1986; Zbl 0552.20045)] the author introduced an algorithm that constructed all square roots of a given member of \(T_ n\) as an alternative to the necessary and sufficient conditions by M. Snowden and J. Howie for a map to be a square [Glasg. Math. J. 23, 137-149 (1982; Zbl 0486.20040)]. In this paper the method, which uses the representation of members of \(T_ n\) as digraphs with functional components, is extended to furnish to algorithms that find all solutions to the equations \(ax^ mb=c\) and \(ax=xb(a,b,c\) in \(T_ n)\). Examples are used to motivate and illustrate the successive steps in the algorithm. As an application the members of \(T_ n\) which commute with no members of \(T_ n\) other than the powers of a are determined.
Reviewer: P.M.Higgins


20M20 Semigroups of transformations, relations, partitions, etc.
20M05 Free semigroups, generators and relations, word problems
05C20 Directed graphs (digraphs), tournaments
Full Text: DOI


[1] Howie, Proc. Roy. Soc. Edinburgh, Sect. A 81 pp 317– (1978) · Zbl 0403.20038
[2] DOI: 10.1112/jlms/s1-41.1.707 · Zbl 0146.02903
[3] Snowden, Glasgow Math. J. 23 pp 137– (1982)
[4] Harary, Graph theory (1969)
[5] Clifford, The algebraic theory of semigroups I (1961)
[6] Higgins, Bull. Canad. Math. Soc. 29 pp 344– (1986) · Zbl 0552.20045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.