Automatic semigroups vs automaton semigroups

∗

Matthieu Picantin
IRIF, UMR 8243 CNRS & Univ. Paris Diderot, 75013 Paris, France
picantin@irif.fr

arXiv:1609.09364v3 [math.GR] 18 Jan 2017

Abstract
We develop an effective and natural approach to interpret any semigroup admitting a special
language of greedy normal forms as an automaton semigroup, namely the semigroup generated
by a Mealy automaton encoding the behaviour of such a language of greedy normal forms under
one-sided multiplication. The framework embraces many of the well-known classes of (automatic)
semigroups: finite monoids, free semigroups, free commutative monoids, trace or divisibility
monoids, braid or Artin-Tits or Krammer or Garside monoids, Baumslag-Solitar semigroups,
etc. Like plactic monoids or Chinese monoids, some neither left- nor right-cancellative automatic
semigroups are also investigated, as well as some residually finite variations of the bicyclic monoid.
It provides what appears to be the first known connection from a class of automatic semigroups
to a class of automaton semigroups. It is worthwhile noting that, in all these cases, "being
an automatic semigroup" and "being an automaton semigroup" become dual properties in a
very automata-theoretical sense. Quadratic rewriting systems and associated tilings appear as a
cornerstone of our construction.
1998 ACM Subject Classification F.1.1 Models of Computation, F.4.3 Formal Languages.
Keywords and phrases Mealy machine, semigroup, rewriting system, automaticity, selfsimilarity.
Digital Object Identifier 10.4230/LIPIcs.X.2016.23

1

Introduction

The half century long history of the interactions between (semi)group theory and automata
theory went through a pivotal decade from the mid-eighties to the mid-nineties. Concomitantly and independently, two new theories truly started to develop and thrive: automaton
(semi)groups on the one hand with the works of Aleshin [2, 3] and Grigorchuk [24, 25] and
the book [43], and automatic (semi)groups on the other hand with the work of Cannon
and Thurston and the book [21]. We refer to [49] for a clear and short survey on the known
interactions groups/automata. A deeper and more extended survey by Bartholdi and Silva
can be found out in two chapters [5, 6] of the forthcoming AutoMathA handbook. We can
refer to [12, 41] for automaton semigroups and to [15, 29] for automatic semigroups.
As their very name indicates, automaton (semi)groups and automatic (semi)groups share a
same defining object: the automaton or the letter-to-letter transducer in this case. Beyond
this common origin, these two topics until now happened to remain largely distant both in
terms of community and in terms of tools or results. Typically, any paper on one or the
other topic used to contain a sentence like "it should be emphasized that, despite their similar names, the notions of automaton (semi)groups are entirely separate from the notions of

∗

This work was partially supported by the French Agence Nationale pour la Recherche, through the
project MealyM ANR-JS02-012-01.

© Matthieu Picantin;
licensed under Creative Commons License CC-BY
42nd Conference on Very Important Topics (CVIT 2016).
Editors: John Q. Open and Joan R. Acces; Article No. 23; pp. 23:1–23:18
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

23:2

From automatic semigroups to automaton semigroups

automatic (semi)groups". This was best evidenced by the above-mentioned valuable handbook chapter [5] which splits into exactly two sections (automatic groups and automaton
groups) without any reference between one and the other appearing explicitly.

automatic
AIM Self-similar groups
& conformal dynamics [11]

automaton

?

groups

hyperbolic groups

Grigorchuk groups

h a, b : [a, b]2 i

Gupta-Sidki groups

m

h a, b : ab = bm a i

h a, b : ab

some Artin groups
Kourovka notebook [40]

finite groups

m

=b ai

free (abelian) groups

?

finite semigroups

semigroups

bicyclic monoid

free (abelian) semigroups

Artin or Garside monoids

Baumslag-Solitar monoids
Artin-Krammer monoids

plactic or Chinese monoids
Theorem 13
Figure 1 The big picture: comparing the classes of automatic vs automaton (semi)groups.

A significant problem is to recognize whether a given (semi)group is self-similar, that is, an
automaton (semi)group. Amongst the unsolved problems in group theory of the Kourovka
Notebook [40], there is the one (with number 16.84) asked by Sushchanskii (see also [36]):
Can the n-strand braid group Bn act faithfully on a regular rooted tree by finite-state
automorphisms?
This amounts to ask whether the braid group is a subgroup of some automaton group.
Amongst the thirty-odd listed problems from [11], we can pick the one with the number 1.1:
It seems quite difficult to show whether a given group is self-similar.
Are Gromov hyperbolic groups self-similar?
Find obstructions to self-similarity.
All these questions can be meaningfully rephrased in terms of semigroups or monoids.
Our aim here is to establish a possible connection between being an automatic semigroup
and being an automaton semigroup. Preliminary observations are that these classes intersect
non trivially and that none is included in the other (see Figure 1). Like the Grigorchuk group
for instance, many automaton groups are infinite torsion groups, hence cannot be automatic
groups. By contrast, it is an open question whether every automatic group is an automaton
group. The latter is related to the question whether every automatic group is residually
finite, which remains open despite the works by Wise [51] and Elder [20]. Like the bicyclic
monoid, some automatic semigroups are not residually finite, hence cannot be automaton
semigroups (see [12] for instance).

M. Picantin

23:3

As for the intersection, we know that at least finite semigroups, free semigroups (of rank at
least 2, see [9, 10]), free abelian semigroups happen to be both automatic semigroups and
automaton semigroups. We propose here a new and natural way to interpret algorithmically
each semigroup from a wide class of automatic semigroups—encompassing all the abovementioned classes—as an automaton semigroup (Theorem 13). Furthermore, it is worthwhile
noting that, in all these cases, "being an automatic semigroup" and "being an automaton
semigroup" become dual properties in a very automata-theoretical sense (Corollary 16).
The structure of the paper is as follows. As a simple preliminary, Section 2 illustrates
in a deliberately informal manner how a single Mealy automaton can be used in order
to define both selfsimilar structures and automatic structures (via a principle of duality).
In Section 3, we set up the notations for Mealy automata and recall necessary notions of
dual automaton, cross-diagram, and selfsimilar structure. In Section 4, we recall basics
about normal forms and automatic structures, and we give necessary notions of quadratic
normalisation, square-diagram, and Garside family. Section 5 is devoted to our main result
(Theorem 13 and Corollary 16), while Section 6 finally gathers several carefully selected
examples and counterexamples.

2

A preliminary example

As their very name indicates, automaton (semi)groups and automatic (semi)groups share a
same defining object. In both cases, a Mealy automaton (see Definition 1) basically allows
to transform words into words.
1|0
0|0

0

0|0
1

1|1

2|1
2

0|1

1|1

0|0
1|2

0

1

1|0
2|2

0|1

Figure 2 Two (dual) Mealy automata: the left-hand one computes the division by 3 in base 2
(most significant digit first) vs the right-hand one computes the multiplication by 2 in base 3 (least
significant digit first).

The Mealy automaton displayed on Figure 2 (left) became one of the most classical examples
of a transducer (see [47] for a delightfully alternate history): when starting from the state 0
and reading any binary word u (most significant digit first), it computes the division by 3
in base 2 by outputting the (quotient) binary word v (most significant digit first) satisfying

(u)2 = 3 × (v)2 + f

(1)

where f ∈ {0, 1, 2} corresponds to the arrival state of the run, and where (w)b conventionally
denotes the number that is represented by w in base b.
For the current preliminary section, let us now focus on this basic example and consider the
two different viewpoints described as follows. On the one hand, it seems natural to consider
the set of those functions (from binary words to binary words) thus associated with each
state, then to compose them with each other, and finally to study the (semi)group which is
generated by such functions.

23:4

From automatic semigroups to automaton semigroups

For instance, the function u 7→ v associated with the state 0 can be squared, cubed, and so
on, to obtain functions, which can be again interpreted as the division by 9, 27, . . . (in base 2
with most significant digit first). One can show here that the generated semigroup is the
rank 3 free semigroup {0, 1, 2}+ (provided that the three states and their induced functions
are identified).
This simple idea coincides with the notion of automaton (semi)groups or selfsimilar structures (see Definition 2). With this crucial standpoint, we can compute (semi)group operations by manipulating the corresponding Mealy automaton (see [4, 5, 31, 42]), and
hopefully foresee some combinatorial and dynamical properties by examining its shape
(see [7, 8, 16, 22, 23, 30, 33, 34, 50] for instance).
On the other hand, it may be also natural to simply iterate the runs. The starting language
is again over the (input/output) alphabet, now the images of the transformations are some
languages over the stateset.
For instance, restarting again from the state 0, the previously output word v (satisfying
Equation (1)) can be read in turn, and so on. The successive arrival states can be then
collected and concatenated in order to obtain here the decomposition of (u)2 in base 3
(least significant digit first).
This second idea coincides with the fundamental notion of automatic (semi)groups (see
Definition 3).
To conclude this preliminary section, let us mention that states and letters of any Mealy
automaton play a symmetric role, and that several properties can be beneficially derived
from the so-called dual (Mealy) automaton, obtained by exchanging the stateset and the
alphabet (see [32] for an overview).
For instance, Figure 2 displays a pair of dual automata. While the left-hand automaton
allows to compute the division by 3 in base 2 (most significant digit first) as we have seen
just above, its dual automaton (right) essentially computes the multiplication by 2 in base 3
(least significant digit first). More precisely, its state 0 induces the function x 7→ 2 × x,
while its state 1 induces the function x 7→ 2 × x + 1: they together generate the rank 2 free
semigroup. Now, the induced functions happen to be invertible and to generate a group
which is isomorphic with the so-called Baumslag-Solitar group
BS(2, 1) = h α, δ : δα2 = αδ i
where δ denotes the doubling action induced by the state 0 and α is defined as the product
of the inverse of δ and the action induced by the state 1, hence α corresponds to the adding
function x 7→ x + 1 (see [7] for further details).
Besides, such a Mealy automaton (right) can be used to compute the base 2 representation
from the base 3 representation of the fractional part of any non-negative rational number,
by iterating runs as explained above. For instance, iterated runs from the state 0 and the
initial word 12 produce the word (110001)ω , both words representing (the fractional part
of) the real 97 10 in base 3 (least significant digit first) and in base 2 (most significant digit
first) respectively.
This innocuous example allows to illustrate the quite simple machineries associated both
with automaton semigroups and with automatic semigroups. It also aims to give an informal glimpse on their behaviours through the duality principle: for instance, division vs
multiplication, factor vs base, least vs most significant digit first, integer part vs fractional
part.

M. Picantin

3

23:5

Mealy automata and selfsimilar structures

We first recall the formal definition of an automaton.
I Definition 1. A (finite, deterministic, and complete) automaton is a triple Q, Σ, τ =
(τi : Q → Q)i∈Σ , where the stateset Q and the alphabet Σ are non-empty finite sets, and
where the τi ’s are functions.

A Mealy automaton is a quadruple Q, Σ, τ = (τi : Q → Q)i∈Σ , σ = (σx : Σ → Σ)x∈Q such
that both (Q, Σ, τ ) and (Σ, Q, σ) are automata.
In other terms, a Mealy automaton is a complete, deterministic, letter-to-letter transducer
with the same input and output alphabet.
The graphical representation of a Mealy automaton is standard, see Figures 2, 8, and 11.
In a Mealy automaton A = (Q, Σ, τ, σ), the sets Q and Σ play dual roles. So we may
consider the dual (Mealy) automaton defined by d(A) = (Σ, Q, σ, τ ):
x|y

i|j
x

y

∈A

⇐⇒

i

j

∈ d(A).

We view A = (Q, Σ, τ, σ) as an automaton with an input and an output tape, thus defining
mappings from input words over Σ to output words over Σ. Formally, for x ∈ Q, the
map σx : Σ∗ → Σ∗ , extending σx : Σ → Σ, is defined recursively by:
∀i ∈ Σ, ∀s ∈ Σ∗ ,

σx (is) = σx (i)στi (x) (s) .

(2)

Equation (2) can be easier to understood if depicted by a cross-diagram (see [1]):
s

i
x

τi (x)
σx (i)

τs (τi (x))
στi (x) (s)

By convention, the image of the empty word is itself. The mapping σx for each x ∈ Q is
length-preserving and prefix-preserving. We say that σx is the production function associated
with (A, x). For x = x1 · · · xn ∈ Qn with n > 0, set σx : Σ∗ → Σ∗ , σx = σxn ◦ · · · ◦ σx1 .
Denote dually by τi : Q∗ → Q∗ , i ∈ Σ, the production functions associated with the dual
automaton d(A). For s = s1 · · · sn ∈ Σn with n > 0, set τs : Q∗ → Q∗ , τs = τsn ◦ · · · ◦ τs1 .
I Definition 2. The semigroup of mappings from Σ∗ to Σ∗ generated by {σx , x ∈ Q}
is called the semigroup generated by A and is denoted by hAi+ . When A is invertible,
its production functions are permutations on words of the same length and thus we may
consider the group of mappings from Σ∗ to Σ∗ generated by {σx , x ∈ Q}. This group is
called the group generated by A and is denoted by hAi. In both cases, the term selfsimilar
is used as a synonym.

4

Quadratic normalisations and automatic structures

This section gathers the definitions of some classical notions like normal form or automatic
structure, together with the little more specific notions of a quadratic normalisation (see [19])
and a Garside family (see [17, 18]).

23:6

From automatic semigroups to automaton semigroups

For any set Q, we denote by Q+ the free semigroup over Q (resp. by Q∗ the free monoid
and by 1 its unit element) and call its elements Q-words. We write ||w|| for the length of a
Q-word w, and ww0 for the product of two Q-words w and w0 .
I Definition 3. Let S be a semigroup with a generating subset Q. A normal form for (S, Q)
is a (set-theoretic) section of the canonical projection ev from the language of Q-words
onto S, that is, a map nf that assigns to each element of S a distinguished representative
Q-word:
ev : Q+

S
nf

Whenever nf(S) is regular, it provides a right-automatic structure for S if the language
Lq = { (nf(a), nf(aq)) : a ∈ S } is regular for each q ∈ Q. The semigroup S then can be
called a (right-)automatic semigroup.
We mention here the thorough and precious study in [28] of the different notions (right- or
left-reading vs right- or left-multiplication) of automaticity for semigroups.
I Remark. In his seminal work [21, Chapter 9], Thurston shows how the set of these different
automata recognizing the multiplication—that is, recognizing the languages Lq of those pairs
of normal forms of elements differing by a right factor q ∈ Q—in Definition 3 can be replaced
with advantage by a single letter-to-letter transducer (see Definition 15) that computes the
normal forms via iterated runs, each run both providing one brick of the final normal from
and outputting a word still to be normalised.
One will often consider the associated normalisation n = nf ◦ ev.
I Definition 4. A normalisation is a pair (Q, n), where Q is a set and n is a map from Q+
to itself satisfying, for all Q-words u, v, w:
||n(w)|| = ||w||,
||w|| = 1 ⇒ n(w) = w,
n(u n(w) v) = n(uwv).
A Q-word w satisfying n(w) = w is called n-normal. If S is a semigroup, we say that (Q, n)
is a normalisation for S if S admits the presentation
h Q : { w = n(w) | w ∈ Q+ } i+ .
Following [18], we associate with every element q ∈ Q a q-labeled edge and with a product the
concatenation of the corresponding edges and represent equalities in the ambient semigroup
using commutative diagrams, what we called here square-diagram: for instance, the following
square illustrates an equality q1 q2 = q10 q20 .
q1
q10

q2
q20

For a normalisation (Q, n), we denote by n the restriction of n to Q2 and, for i ≥ 1, by ni
the (partial) map from Q+ to itself that consists in applying n to the entries in position i
and i + 1. For any finite sequence i = i1 · · · in of positive integers, we write ni for the
composite map nin ◦ · · · ◦ ni1 (so ni1 is applied first).

M. Picantin

23:7

···
n

···

q1

n
n

···

n
n

n

q2

n

n
n
n
q3

···
···

n
n

···

Figure 3 From an initial Q-word q1 q2 q3 , one applies normalisations on the first and the second 2factors alternatively up to stabilisation, beginning either on the first 2-factor q1 q2 (right-hand side
here) or on the second q2 q3 . The gray zone corresponds to Condition ( ) as defined in Definition 6.

I Definition 5. A normalisation (Q, n) is quadratic if the two conditions hold:
a Q-word w is n-normal if, and only if, every length-two factor of w is;
for every Q-word w, there exists a finite sequence i of positions, depending on w, such
that n(w) is equal to ni (w).
I Definition 6. As illustrated on Figure 3, with any quadratic normalisation (Q, n) is
associated its breadth (d, p) (called minimal left and right classes in [17, 19]) defined as:
d=

max

(q1 ,q2 ,q3 )∈Q3

min{ ` : n(q1 q2 q3 ) = n 212··· (q1 q2 q3 )},
|{z}
length `

and
p=

max

(q1 ,q2 ,q3 )∈Q3

min{ ` : n(q1 q2 q3 ) = n 121··· (q1 q2 q3 )}.
|{z}
length `

Such a breadth is ensured to be finite provided that Q is finite, and then satisfies |d − p| ≤ 1.
For d ≤ 4 and p ≤ 3, (Q, n) is said to satisfy Condition ( ), corresponding to the so-called
domino rule in [17, 18, 19] but with a different reading direction.
The first main result of [19] is an axiomatisation of these quadratic normalisations satisfying
Condition ( ) in terms of their restrictions to length-two words: any idempotent map n
on Q2 that satisfies n2121 = n121 = n1212 extends into a quadratic normalisation (Q, n)
satisfying Condition ( ). For larger breadths, a map on length-two words normalising
length-three words needs not normalise words of greater length.
The second main result of [19] involves termination. Every quadratic normalisation (Q, n)
gives rise to a quadratic rewriting system, namely the one with rules w −→ n(w) for w ∈ Q2 .
By Definition 5, such a rewriting system is confluent and normalising, meaning that, for every
initial word, there exists a finite sequence of rewriting steps leading to a unique n-normal
word, but its convergence, meaning that any sequence of rewriting steps is finite, is a quite
different problem.
I Theorem 7. [19] If (Q, n) is a quadratic normalisation satisfying Condition (
the associated rewriting system is convergent.

), then

More precisely, every rewriting sequence starting from a word of Qp has length at most p(p−1)
2
(resp. 2p − p − 1) in the case of a breadth (3, 3) (resp. either (3, 4) or (4, 3)). Theorem 7 is
essentially optimal since there exist nonconvergent rewriting systems with breadth (4, 4).

23:8

From automatic semigroups to automaton semigroups

The rest of the current section describes a tiny fragment of Garside theory (see [18] for its
foundations). Garside families were recently introduced as a general framework guaranteeing
the existence of normal forms. Even if this notion is not necessary for the understanding of
the main result, its proof, and the whole of Section 5, several examples of Section 6 could
rely on it.
Let S be a monoid. For a, b, c ∈ S, a is a left-divisor of b or, equivalently, b is a right-multiple
of a if b = ab0 holds for some b0 in S; moreover, b is a minimal common right-multiple, or
right-mcm, of a and c if b is a right-multiple of a and c, and no proper left-divisor of b is a
right-multiple of a and c.
Furthermore, S is said to be right-cancellative whenever, for all a, b, c ∈ S, ab = cb implies
a = c, and S admits no nontrivial invertible element whenever ab = 1 implies a = b = 1.
Right-divisor, left-mcm, and left-cancellativity are defined symmetrically.
I Definition 8. If S is a right-cancellative monoid with no nontrivial invertible element, a
(right-)Garside family for S is a generating set closed under left-divisor and under left-mcm.
Various practical characterisations of Garside families are known, depending in particular
on the specific properties of the considered monoid. The following is especially relevant here.
I Theorem 9. [19] Assume that S is a right-cancellative monoid with no nontrivial invertible
element and with a finite (right-)Garside family Q. Then the normalisation (Q, n) defined
by n(ab) = cd for a, b, c, d ∈ Q with d maximal, satisfies Condition ( ).
The results of Section 5 rely on the special Condition ( ) outlined by Dehornoy and Guiraud
(see [19]). However, none of their results (in particular Theorems 7 and 9 mentioned here
for completeness) is neither applied nor needed to establish ours. The current exposition
is thus self-contained and our constructions never require any of their stronger hypotheses
(neither cancellativity nor absence of nontrivial invertible elements). We here emphasize
that Condition ( ) appears as a common denominator for our different approaches.

5

From an automatic structure to a selfsimilar structure

All the ingredients are now in place to effectively and naturally interpret as an automaton
monoid any automatic monoid admitting a special language of normal forms—namely, a
quadratic normalisation satisfying Condition ( ). The point is to construct a Mealy automaton encoding the behaviour of its language of normal forms under one-sided multiplication.
I Definition 10. Assume that S is a semigroup with a quadratic normalisation (Q, n). We
define the Mealy automaton MS,Q,n = (Q, Q, τ, σ) such that, for every (a, b) ∈ Q2 , σb (a) is
the rightmost element of Q in the normal form n(ab) of ab and τa (b) is the left one:
n(ab) = τa (b)σb (a).
The latter correspondence can be simply interpreted via square-diagram vs cross-diagram:
a
b

n
σb (a)

a
τa (b)

τa (b)

b
σb (a)

M. Picantin

23:9

Then, for n(s) = sn · · · s1 and n(sq) = qn s0n · · · s01 , we obtain diagrammatically:

q

s1

s2

n

q1 n

s01

s02

s1
q

q2

qn−1

qn

s0n

s2
q1

s01

sn

sn
qn−1

q2
s02

qn
s0n

We choose on purpose to always draw a normalisation square-diagram backward, such that
it coincides with the associated cross-diagram. The function σq induced by the state q
maps any normal form (read backward) to the normal form of the right-product by q (read
backward).
We now aim to strike reasonable (most often optimal) hypotheses for a quadratic normalisation (Q, n) associated with an original semigroup S to generate a semigroup hMS,Q,n i+ that
approximates S as sharply as possible. Since the generating sets coincide by Definition 10, we
shall first focus on the case where S should be a quotient of hMS,Q,n i+ (top-approximation),
and next, on the case where hMS,Q,n i+ should be a quotient of S (bottom-approximation).
Before establishing our top-approximation statement, we just recall that semigroups could
appear much more difficult to handle, especially when it comes to automaticity (see [28]) or
selfsimilarity (see [9, 10]). To any (not monoid) semigroup S with a quadratic normalisation (Q, n), one obtains a monoid S 1 with a quadratic normalisation (Q1 , n1 ) by adjoining
a unit 1 and then by setting Q1 = Q t {1} and defining n1 by n1 (w) = n(w) and
n1 (1w) = n1 (w1) = 1n(w)

(n)
1

1

for w ∈ Q+ . The choice made for Condition ( n ) becomes natural whenever we think of the
(adjoined or not) unit 1 as some dummy element that simply ensures the length-preserving
property for n1 (see Definition 4 and also [19, Section 2.2]).
1

1

I Lemma 11. Assume that S 1 is a monoid with a quadratic normalisation (Q1 , n1 ) satisfying Condition ( n ). Then the Mealy automaton MS 1 ,Q1 ,n1 generates a monoid of which S 1
is a quotient.
1

1

Proof. Let S 1 = Q∗ / ≡n1 and MS 1 ,Q1 ,n1 = (Q1 , Q1 , τ, σ) as in Definition 10. We have to
prove that any relation in hMS 1 ,Q1 ,n1 i+1 is a relation in S 1 , thereby implying for all u, v ∈ Q∗ :
σu = σv =⇒ u ≡n1 v.
Let σp1 · · · σpk = σq1 · · · σq` be some relation in hMS,Q,n i+1 with pi ∈ Q for 0 ≤ i ≤ k
and qj ∈ Q for 0 ≤ j ≤ `. Any word w over Q1 admits hence the same image under σp1 · · · σpk and under σq1 · · · σq` . By taking w = 1ω (or any sufficiently long power
of 1, precisely any word from 1max(k,`) 1∗ ), such a common image corresponds to their normal forms by very definition of MS 1 ,Q1 ,n1 (see Figure 4). Therefore the resulting letterwise

23:10

From automatic semigroups to automaton semigroups

1
p1
p2

n

p1
n

p01

1
1

n

1

1
p02 n

1

(k−1)

p1

1

n

1

1

1

1

1

p02

n p0k

pk

1

1

n

1

n p00
k

1

n

1

n

1
1

(k−1) n

pk

(k−1)

p2

(k−1)

pk

1

1

n

1

1−ω n(p1 · · · pk )
Figure 4 Proof of Lemma 11: any Q-words inducing a same action have normal forms that
coincide.

equality 1−ω n(p1 · · · pk ) = 1−ω n(q1 · · · q` ) (where 1−ω denotes the left-infinite word · · · 111)
implies that the two corresponding Q-words p1 · · · pk and q1 · · · q` represent a same element
in S 1 by definition of n1 .
J
Although specific to a monoidal framework and then requiring the innocuous Condition ( n ),
the previous straightforward proof relies only on the definition of a quadratic normalisation and on the well-fitted associated Mealy automaton (Definition 10). For the bottomapproximation statement, we consider an extra assumption, which happens to be necessary
and sufficient.
1

1

I Proposition 12. Assume that S is a semigroup with a quadratic normalisation (Q, n).
If Condition ( ) is satisfied, then the Mealy automaton MS,Q,n generates a semigroup
quotient of S. The converse holds provided that Condition ( n ) is satisfied.
1

1

Proof. Let S = Q+ / ≡n and MS,Q,n = (Q, Q, τ, σ) as in Definition 10.
(⇐) Assume that Condition ( ) is satisfied and that there exists (a, b, c, d) ∈ Q4 with ab ≡n
cd. We have to prove σab = σcd . Without lost of generality, the word ab can be supposed
to be n-normal, that is, n(ab) = n(cd) = ab holds.
Let u = qv ∈ Qn for some n > 0 and q ∈ Q. We shall prove both σab (u) = σcd (u)
(coordinatewise) and τu (ab) ≡n τu (cd) by induction on n > 0. For n = 1, we obtain the
two square-diagrams on Figure 5 (left). With these notations, we have to prove q000 = q100
and a0 b0 ≡n c0 d0 , the latter meaning n(a0 b0 ) = n(c0 d0 ), that is, with the notations from
Figure 5, the conjunction of a00 = c00 and b00 = d00 . Now these three equalities hold whenever
(Q, n) satisfies Condition ( ), as shown on Figure 5 (right).
This allows to proceed the induction and to prove the implication (⇐).
(⇒) Consider an arbitrary length 3 word over Q, say qcd. Let a, b denote the elements
in Q satisfying n(cd) = ab. By definition, we deduce ab ≡n cd. This implies σab = σcd by
hypothesis. In particular, the images of any word qv under σab and σcd coincide: σab (qv) =
σcd (qv), hence
σab (q) = q000 = q100 = σcd (q)
and
στq (ab) (v) = σa0 b0 (v) = σc0 d0 (v) = στq (cd) (v)

M. Picantin

23:11

(with notations of Figure 5). The last equality holds for any original word v ∈ Q∗ and
implies σa0 b0 = σc0 d0 . Whenever, Condition ( n ) is satisfied, we deduce n(a0 b0 ) = n(c0 d0 )
according to Lemma 11. We obtain
1

1

n121 (qcd) = n2121 (qcd).
Therefore (Q, n) satisfies Condition (

q

J

).

a00

q

a0

q

c0

n

a

0

a

n

c

c

n

q00
b

0

q10
b0 d

n

b0

d0

c00

n
q00

n

a

c

q10
w

n

n

q000

b

00

n
q000

b

n
d

0

d00

n
d

q100

q100

Figure 5 Proof of Proposition 12: initial data (left) can be pasted into Condition (

) (right).

Gathering Lemma 11 and Proposition 12, we obtain the following main result.
I Theorem 13. Assume that S is a monoid with a quadratic normalisation (Q, n) satisfying Conditions ( n ) and ( ). Then the Mealy automaton MS,Q,n generates a monoid
isomorphic to S.
1

1

Proof. By construction, S and hMS,Q,n i+1 share a same generating subset Q. Now, any
defining relation for S maps to a defining relation for hMS,Q,n i+1 by Proposition 12, and
conversely by Lemma 11.
J
I Corollary 14. Any monoid with a quadratic normalisation satisfying Conditions ( n )
and ( ) is residually finite.
1

1

To conclude this main section, we come back to that remark (following Definition 3) about
the original transducer approach by Thurston.
I Definition 15. With any quadratic normalisation (Q, n) is associated its Thurston transducer defined as the Mealy automaton TQ,n with stateset Q, alphabet Q, and transitions as
follows:
a
b|d
b

n

d

a

c

c
I Corollary 16. Assume that S is a monoid with a quadratic normalisation (Q, n) satisfying
Conditions ( n ) and ( ). The Thurston transducer TQ,n and the Mealy automaton MS,Q,n
being dual automaton, S possesses both the explicitly dual properties of automaticity and
selfsimilarity.
1

1

23:12

From automatic semigroups to automaton semigroups

6

Examples and counterexamples

Our very first example is straightforward, but enlightening.
I Example 17. Every finite monoid J (in particular every finite group) is an automaticon
monoid. Consider its quadratic normalisation (J , n) with n(ab) = 1(ab) for every (a, b) ∈
J 2 . Figure 6 shows how to compute its breadth (3, 2), witness of Condition ( ) for applying
Theorem 13.

1

1

a

n

1

a

b

ab

n
n
abc

1

n

1

x

1

n

x

c

a

n
1

1

x

n
b

abc

Figure 6 Computing the breadth (3, 2) for
any finite monoid J as in Example 17.

n

a

n
x

1

n
1

n

bc

x

1

1

1

n
x

Figure 7 Computing the breadth (3, 4) for
the bicylic monoid B from Example 18.

As mentioned in Section 1 and appearing on Figure 1, there exist automatic semigroups
that cannot be automaton semigroups.
I Example 18. The bicyclic monoid B = h a, b : ab = 1 i+1 is known to be automatic and
not residually finite, hence cannot be an automaton monoid. Choose for B the quadratic
normalisation ({a, b, 1}, n) with n(ab) = 11, n(x1) = 1x for x ∈ {a, b}, and n(xy) = xy
otherwise. Figure 7 illustrates the computation (on the witness word xab with x ∈ {a, b}) of
its breadth (3, 4). The Condition ( ) is hence not satisfied and Theorem 13 cannot apply.
Precisely, according to the proof of Proposition 12 and Figure 5, we have σab (x) = 1 6= x =
σ11 (x) for x ∈ {a, b}, hence σab 6= σ1 = σ11 .
By contrast, one of the simplest nontrivial examples could be the following.
I Example 19. The automatic (right-cancellative) monoid h a, b : ab = a i+1 admits Q =
{1, a, b} as a (right-)Garside family. According to Proposition 9 and Theorem 13, it is therefore an automaton monoid. The corresponding Mealy automaton is displayed on Figure 8.
The latter happens to be the common smallest nontrivial member of the family of BaumslagSolitar monoids (see [28] for instance), namely BS+1 (1, 0), and of a wide family of rightcancellative semigroups, that we readily call Artin-Krammer monoids and that have been
introduced and studied in [35] (see also [26, 27, 44]), namely AK+1 (Γ) associated with the
Coxeter-like matrix Γ =


1
2


1
.
1

Examples 20 and 21 describe important members from both these families.
I Example 20. The following Artin-Krammer monoid is emblematic:
AK+1

 1
4
2

3
1
4


2
3
1



*
=

abab = aba +1
a, b, c : ac = ca
.
bcbc = bcb +

M. Picantin

23:13
a|b
a
b|a
b|b

b

1|a
1

1|1
a|a
b|b

1|b
a|a
Figure 8 The Mealy automaton associated with the monoid h a, b : ab = a i+1 from Example 19.

a

ba
ab3
ab4

b4
bab

Figure 9 Theminimal
Garside family of



the monoid

AK+1

1
4
2

3
1
4

2
3
1

from Example 20.

b3

b2
ab2

1
b

ab

Figure 10 The minimal Garside family of
the monoid BS+1(3, 2) from Example 21.

As displayed on Figure 9, its minimal Garside family forms like a flint which encodes its
whole combinatorics and, according to Theorem 13, makes it an automaticon monoid.
I Example 21. Consider the Baumslag-Solitar monoid BS+1(3, 2) = h a, b : ab3 = b2 a i+1 .
Displayed on Figure 10, its minimal Garside family contains eight elements (orange vertices)
and makes it an automaticon monoid. This is an example of a group-embeddable automaton
monoid whose enveloping group is not an automaton group. Indeed, the Baumslag-Solitar
group BS(3, 2) is precisely known as an example of non-residually finite group, hence cannot
be an automaton group. The question remains open for those automaton semigroups whose
enveloping group is a group of fractions.
I Question 22. Is the group of fractions of an automaton monoid an automaton group?
Concerning again group-embeddability, the following gives now an example of a cancellative
automaton semigroup which is not group-embeddable.
I Example 23. The monoid T = h a, b, c, d, a0 , b0 , c0 , d0 : ab = cd, a0 b0 = c0 d0 , a0 d = c0 b i+1
is known (by Malcev work [37, 38, 39]) to be cancellative but not group-embeddable: from
these three relations, we cannot deduce the fourth ad0 = cb0 . The quadratic normalisation ({a, b, c, d, a0 , b0 , c0 , d0 }, n) defined by n(ab) = cd, n(a0 b0 ) = c0 d0 , and n(a0 d) = c0 b for
instance has breadth (3, 3), hence satisfies Condition ( ) and Theorem 13 applies. This
answers in particular a question by Cain [13].
Some classes of neither left- nor right-cancellative monoids have been studied and shown to
admit nice normal forms yielding biautomatic structures (see [14]):
I Example 24. According to Schützenberger [48], plactic monoids are among the most
fundamental monoids. The rank 2 plactic monoid is P2 = h a, b : aba = baa, bab = bba i+1 .
As noted in [17, 19], P2 admits the quadratic normalisation (Q, n) with Q = {1, a, b, ba},

23:14

From automatic semigroups to automaton semigroups

n(ba) = 1(ba), n((ba)a) = a(ba), n((ba)b) = b(ba), n(1x) = x1 for x ∈ Q, and n(xy) = xy
otherwise. The latter has a breadth (3, 3), hence satisfies Condition ( ) and Theorem 13
ensures that P2 is an automaton monoid. Note that, for a higher rank plastic monoid PX , it
suffices similarly to take for Q the set of columns, that is, the strictly decreasing products of
elements of X. Chinese monoids [14] admit also quadratic normalisations with breadth (4, 3),
hence satisfy Condition ( ), and Theorem 13 ensures that they are selfsimilar as well.
To conclude, we would like to completely illustrate the duality between "being an automatic
semigroup" and "being an automaton semigroup" by highlighting a paradigmatic example.
I Example 25. The braid monoids were used by Thurston [21, Chapter 9] to describe
his idea to build a single transducer that computes the now-called Adjan-Garside-Thurston
normal form via iterated runs. The 3-strand braid monoid is
B13+ = h

,

:

=

i+1 .

According to Corollary 16, its Thurston transducer and its Mealy automaton are displayed
on Figure 11: these dual automata make B13+ both an automatic and an automaton monoid.
Such an approach may hopefully shed some light on the question of whether or not the braid
groups are selfsimilar.

M. Picantin

d

23:15

d

Figure 11 The Thurston transducer (top) vs the Mealy automaton (bottom) for the 3-strand
braid monoid B13+ from Example 25.

23:16

From automatic semigroups to automaton semigroups

References
1

2
3
4
5
6
7

8

9
10

11
12
13
14

15
16

17

18

19
20
21

Ali Akhavi, Ines Klimann, Sylvain Lombardy, Jean Mairesse, and Matthieu Picantin. On
the finiteness problem for automaton (semi)groups. Internat. J. Algebra Comput., 22(6):1–
26, 2012.
Stanislas V. Alëšin. Finite automata and the Burnside problem for periodic groups. Mat.
Zametki, 11:319–328, 1972.
Stanislav V. Alëšin. A free group of finite automata. Vestnik Moskov. Univ. Ser. I Mat.
Mekh., 4:12–14, 1983.
Laurent Bartholdi. FR – GAP package “Computations with functionally recursive groups”,
Version 2.1.1, 2014. URL: http://www.gap-system.org/Packages/fr.html.
Laurent Bartholdi and Pedro V. Silva. Groups defined by automata. In J.-É. Pin, editor,
AutoMathA Handbook. Europ. Math. Soc., 2010. "cs.FL/1012.1531".
Laurent Bartholdi and Pedro V. Silva. Rational subsets of groups. In J.-É. Pin, editor,
AutoMathA Handbook. Europ. Math. Soc., 2010. "cs.FL/1012.1532".
Laurent Bartholdi and Zoran Šuniḱ. Some solvable automaton groups. In Topological and
asymptotic aspects of group theory, volume 394 of Contemp. Math., pages 11–29. Amer.
Math. Soc., Providence, RI, 2006.
Ievgen V. Bondarenko, Natalia V. Bondarenko, Saïd N. Sidki, and Flavia R. Zapata. On the
conjugacy problem for finite-state automorphisms of regular rooted trees. Groups Geom.
Dyn., 7(2):323–355, 2013. With an appendix by Raphaël M. Jungers.
Tara Brough and Alan J. Cain. Automaton semigroup constructions. Semigroup Forum,
90(3):763–774, 2015.
Tara Brough and Alan J. Cain. Automaton semigroups: new constructions results and
examples of non-automaton semigroups. Preprint, 2016. URL: http://arxiv.org/abs/
1601.01168.
Kai-Uwe Bux et al. Selfsimilar groups and conformal dynamics - Problem List. AIM workshop 2006. URL: http://www.aimath.org/WWN/selfsimgroups/selfsimgroups.pdf.
Alan J. Cain. Automaton semigroups. Theoret. Comput. Sci., 410(47-49):5022–5038, 2009.
Alan J. Cain. Personal communication, 2016.
Alan J. Cain, Robert D. Gray, and António Malheiro. Rewriting systems and biautomatic
structures for Chinese, hypoplactic, and Sylvester monoids. Internat. J. Algebra Comput.,
25(1-2):51–80, 2015.
Colin M. Campbell, Edmund F. Robertson, Nikola Ruškuc, and Richard M. Thomas. Automatic semigroups. Theoret. Comput. Sci., 250(1-2):365–391, 2001.
Daniele D’Angeli, Thibault Godin, Ines Klimann, Matthieu Picantin, and Emanuele
Rodaro. Boundary action of automaton groups without singular points and Wang tilings.
Submitted, 2016. URL: http://arxiv.org/abs/1604.07736.
Patrick Dehornoy. Garside and quadratic normalisation: a survey. In 19th International
Conference on Developments in Language Theory (DLT 2015), volume 9168 of LNCS, pages
14–45, 2015.
Patrick Dehornoy et al. Foundations of Garside theory. Europ. Math. Soc. Tracts in
Mathematics, volume 22, 2015. URL: http://www.math.unicaen.fr/~garside/Garside.
pdf.
Patrick Dehornoy and Yves Guiraud. Quadratic normalization in monoids. Internat. J.
Algebra Comput., 26(5):935–972, 2016.
Murray Elder. Automaticity, almost convexity and falsification by fellow traveler properties
of some finitely presented groups. PhD thesis, Univ Melbourne, 2000.
David B. A. Epstein, James W. Cannon, Derek F. Holt, Silvio V. F. Levy, Michael S. Paterson, and William P. Thurston. Word processing in groups. Jones and Bartlett Publishers,
Boston, MA, 1992.

M. Picantin

22
23

24
25
26

27
28
29
30

31

32

33

34
35
36

37
38
39
40
41
42

Pierre Gillibert. The finiteness problem for automaton semigroups is undecidable. Internat.
J. Algebra Comput., 24(1):1–9, 2014.
Thibault Godin, Ines Klimann, and Matthieu Picantin. On torsion-free semigroups generated by invertible reversible Mealy automata. In 9th International Conference on Language
and Automata Theory and Applications (LATA 2015), pages 328–339, 2015.
Rostislav I. Grigorchuk. On Burnside’s problem on periodic groups. Funktsional. Anal. i
Prilozhen., 14(1):53–54, 1980.
Rostislav I. Grigorchuk. Degrees of growth of finitely generated groups and the theory of
invariant means. Izv. Akad. Nauk SSSR Ser. Mat., 48(5):939–985, 1984.
Alexander Hess. Factorable monoids: resolutions and homology via discrete Morse theory.
PhD thesis, Univ Bonn, 2012. URL: http://hss.ulb.uni-bonn.de/2012/2932/2932.
pdf.
Alexander Hess and Viktoriya Ozornova. Factorability, string rewriting and discrete morse
theory. Submitted. URL: http://arxiv.org/abs/1412.3025.
Michael Hoffmann. Automatic Semigroups. PhD thesis, Univ Leicester, 2001.
Michael Hoffmann and Richard M. Thomas. Biautomatic semigroups. In Fundamentals of
computation theory, volume 3623 of LNCS, pages 56–67. 2005.
Ines Klimann. The finiteness of a group generated by a 2-letter invertible-reversible Mealy
automaton is decidable. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), volume 20 of LIPIcs, pages 502–513, 2013.
Ines Klimann, Jean Mairesse, and Matthieu Picantin. Implementing computations in automaton (semi)groups. In 17th International Conference on Implementation and Application
of Automata (CIAA 2012), volume 7381 of LNCS, pages 240–252, 2012.
Ines Klimann and Matthieu Picantin. Automaton (semi)groups: Wang tilings and Schreier
tries. In Valérie Berthé and Michel Rigo, editors, Sequences, Groups, and Number Theory.
Trends in Mathematics, 2017.
Ines Klimann, Matthieu Picantin, and Dmytro Savchuk. A connected 3-state reversible
mealy automaton cannot generate an infinite burnside group. In 19th International Conference on Developments in Language Theory (DLT 2015), volume 9168 of LNCS, pages
313–325, 2015.
Ines Klimann, Matthieu Picantin, and Dmytro Savchuk. Orbit automata as a new tool to
attack the order problem in automaton groups. J. Algebra, 445:433–457, 2016.
Daan Krammer. An asymmetric generalisation of Artin monoids. Groups Complex.
Cryptol., 5:141–168, 2013.
Yaroslav Lavrenyuk, Volodymyr Mazorchuk, Andriy Oliynyk, and Vitaliy Sushchansky.
Faithful group actions on rooted trees induced by actions of quotients. Comm. Algebra,
35(11):3759–3775, 2007.
Anatoly I. Malcev. On the immersion of an algebraic ring into a field. Math. Ann.,
113(1):686–691, 1937.
Anatoly I. Malcev. Über die Einbettung von assoziativen Systemen in Gruppen. Rec. Math.
[Mat. Sbornik] N.S., 6 (48):331–336, 1939.
Anatoly I. Malcev. Über die Einbettung von assoziativen Systemen in Gruppen. II. Rec.
Math. [Mat. Sbornik] N.S., 8 (50):251–264, 1940.
Victor D. Mazurov and Evgeny I. Khukhro. Unsolved problems in group theory. The
Kourovka notebook. No 18. URL: http://arxiv.org/abs/1401.0300.
David McCune. Groups and Semigroups Generated by Automata. PhD thesis, Univ
Nebraska-Lincoln, 2011.
Yevgen Muntyan and Dmytro Savchuk. AutomGrp – GAP package for computations in
self-similar groups and semigroups, Version 1.2.4, 2014. URL: http://www.gap-system.
org/Packages/automgrp.html.

23:17

23:18

From automatic semigroups to automaton semigroups

43
44

45
46
47
48
49
50
51

Volodymyr V. Nekrashevych. Self-similar groups, volume 117 of Mathematical Surveys and
Monographs. American Mathematical Society, Providence, RI, 2005.
Viktoriya Ozornova. Factorability, discrete Morse theory, and a reformularion of K(π, 1)conjecture. PhD thesis, Univ Bonn, 2013. URL: http://hss.ulb.uni-bonn.de/2013/
3117/3117.pdf.
Matthieu Picantin. Finite transducers for divisibility monoids. Theoret. Comput. Sci.,
362(1-3):207–221, 2006.
Matthieu Picantin. Tree products of cyclic groups and HNN extensions. Preprint, 2013.
URL: http://arxiv.org/abs/1306.5724.
Jacques Sakarovitch. Elements of Automata Theory. Cambridge University Press, New
York, NY, USA, 2009.
Marcel-Paul Schützenberger. Pour le monoïde plaxique. Math. Inform. Sci. Humaines,
140:5–10, 1997.
Pedro V. Silva. Groups and automata: A perfect match. In Descriptional Complexity of
Formal Systems, volume 7386 of LNCS, pages 50–63. 2012.
Pedro V. Silva and Benjamin Steinberg. On a class of automata groups generalizing lamplighter groups. Internat. J. Algebra Comput., 15(5-6):1213–1234, 2005.
Daniel T. Wise. A non-Hopfian automatic group. J. Algebra, 180(3):845–847, 1996.

