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

Higgins, Peter M.

Glasg. Math. J. 30, No. 1, 41-57 (1988).

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

MSC:

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

Keywords:

full transformation semigroup; square roots; digraphs; algorithms; solutions; equations

Citations:

Zbl 0595.20069; Zbl 0552.20045; Zbl 0486.20040

References:

[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