Corrigendum for
---
T. Uustalu. A divertimento on MonadPlus and nondeterminism.
J. of Log. and Algebraic Methods in Program., v. 85, n. 5, part 2,
pp. 1086-1094, 2016. doi:10.1016/j.jlamp.2016.06.004
---
p 1091, 3rd parag from bottom: The claims in this paragraph are
erroneous.
The statement "The free band on a set X is given by the set of
square-free nonempty lists over X" is false.
This is because it is not the case that "square-free nonempty lists
make canonical representatives for the equivalence classes [of
nonempty lists wrt. the least congruence containing idempotence] by
serving as unique normal forms".
If the rewrite system on nonempty lists given by the idempotence
equation turned into the rule
ww --> w
were confluent, square-free nonempty lists would work as unique
normal forms.
But it is not confluent. The nonempty list abcbabcbc has two normal
forms abc and abcbabc:
abc <-- abcbc <-- abcbabcbc --> abcbabc
Hence the free band is not the set of square-free nonempty lists, but
a proper quotient of it.
I learned about my error from Ernie Manes and Phil Mulry's paper in
MFPS '18. They refer to
J. M. Howie, An Introduction to Semigroup Theory, Academic Press, 1971
for the correct construction of the free band.
Some relevant papers are
W. Burnside, On an unsettled question in the theory of discontinuous
groups, Quart. J. Pure Appl. Math., v. 33, pp. 230-238, 1902.
J. A. Green and D. Rees, On semi-groups in which x^r = x,
Proc. Cambridge Phil. Soc., v. 48, pp. 35-40, 1952.
D. McLean, Idempotent semigroups, Amer. Math. Monthly, v. 61,
pp. 110-113, 1954.
J. Siekmann and P. Szabó, A noetherian and confluent rewrite system for
idempotent semigroups, Semigroup Forum, v. 25, pp. 83-110, 1982.
J. A. Gerhard, M. Petrich, Free bands and free *-bands,
Glasgow J. Math., v. 28, pp. 161-179, 1986.
N. Dershowitz, Semigroups satisfying x^{m+n} = x^n. In M. Rusinowitch,
J. L. Rémy, eds., CTRS 1992, v. 565 of LNCS, pp. 307-314, Springer,
1993.
The rules of Siekmann and Szabó's system are
ww --> w
uwv --> uv if |w| \subseteq |u| = |v|
where |-| returns the nonempty set of elements of a nonempty list.