A LANGUAGE HIERARCHY AND KITCHENS-TYPE THEOREM FOR
SELF-SIMILAR GROUPS

arXiv:1710.02886v1 [math.GR] 8 Oct 2017

ANDREW PENLAND AND ZORAN ŠUNIĆ
Abstract. We generalize the notion of self-similar groups of infinite tree automorphisms
to allow for groups which are defined on a tree but do not act faithfully on it. The elements
of such a group correspond to labeled trees which may be recognized by a tree automaton
(e.g. Rabin, Büchi, etc.), or considered as elements of a tree shift (e.g. of finite type, sofic)
as in symbolic dynamics. We give examples to show that the various classes of self-similar
groups defined in this way do not coincide. As the main result, extending the classical
result of Kitchens on one-dimensional group shifts, we provide a sufficient condition for a
self-similar group whose elements form a sofic tree shift to be a tree shift of finite type. As
an application, we show that the closure of certain self-similar groups of tree automorphisms
are not Rabin-recognizable.

1. Introduction
In this paper, we consider regular, rooted trees with vertices labeled by elements of some
finite alphabet. Our goal is to connect the computational, dynamical, and group-theoretic
perspectives of these objects. As background and motivation for the present work, let us
briefly describe some different perspectives on labeled trees, as well as how these perspectives
are already known to relate to one another.
For our purposes, a k-regular, rooted tree is an infinite directed graph with no cycles which
has a distinguished vertex called the root, such that each vertex has k distinct children. (A
vertex v is a child of a vertex w if there is an edge from w to v.) Such a tree occurs as the
right Cayley graph of a finitely generated free monoid, as follows. If X is a finite set, then
we write X ∗ for the set of all finite words in X. This set forms a monoid with concatenation
as the binary operation and the empty word ǫ as the identity. The right Cayley graph of
this monoid has all words w ∈ X ∗ as its vertices, with a directed edge between v and vx for
all v ∈ X ∗ and x ∈ X; this graph clearly forms an |X|-regular tree whose root is the empty
word ǫ.
When |X| = 1, the free monoid on X is infinite cyclic and thus is isomorphic to the set of
nonnegative integers under addition. The corresponding graph has the structure of a rooted,
1-regular tree, i.e. an infinite, one-way path where each vertex has exactly one child. We
shall refer to this as the one-dimensional case.
Given a fixed k-regular, rooted tree T and a finite alphabet A, one may consider the space
of all A-labelings of T , i.e. all possible functions from the vertices of T to A, which we
Date: March 6, 2018.
2010 Mathematics Subject Classification. 20E08, 37B10, 20E18, 37B50, 68Q45, 03D05.
Key words and phrases. self-similar groups, tree shifts, rooted tree automorphisms, tree automata, finitely
constrained groups, branch groups, Rabin automata.
1

denote by AT . Such spaces appear in many different areas of mathematics; here we give a
non-exhaustive list.
• Computation Theory. In the theory of computation, a subset of AT is called a
language. There is a large body of work on these languages and the tree automata which
accept them. In particular, the one-dimensional case of a one-way, infinite path has been
extensively studied in theoretical computer science. Labelings of this path correspond to
sequences or right-infinite words over the finite alphabet A, with finite connected subgraphs
viewed as finite words over A. Hence, this is where one finds the classical notions of codes,
languages, and various classes of automata which accept either finite or infinite words (such
as in [18]).
• Symbolic Dynamics. Labeled trees also occur in modern symbolic dynamics, which
is concerned with the properties of shift spaces on arbitrary groups or semigroups (as in [9]
and [11]). If T is a semigroup and A is a finite alphabet, the full shift AT is defined as the
space of all functions from T to A. The full shift is equipped with the so-called prodiscrete
topology, as well as a shift action σt for each element t ∈ T . Each such shift action is a
continuous self-mapping of the prodiscrete topological space AT , and a subset X ⊆ AT is
called shift-invariant if σt (x) ∈ X for each t ∈ T and x ∈ X. A subset of the full shift AT is
called a shift space if it is both shift-invariant and topologically closed as a subspace in the
prodiscrete topology.
A pattern p is a function from a finite subset of T to A. It is well-known that any shift
space can be defined by declaring some collection of forbidden patterns which do not appear
in any configuration in the space. If a finite collection of forbidden patterns may be used,
the shift is called a shift of finite type.
For any finite set X there is a corresponding free monoid X ∗ whose right Cayley graph
has the structure of a tree. Hence, for a finite alphabet A, configurations of the full shift
∗
AX over this monoid correspond to the type of labeled trees which we consider.
Again, in this area, the one-dimensional case has been extensively studied. The study of
the connections between properties of one-dimensional shift spaces whose allowed or forbidden patterns form certain languages is well-established (see, for instance, the early chapters
of [21]) and remains active. In the more general case of a rooted k-regular tree, Aubrun
and Beal have examined algebraic and algorithmic aspects of various classes of tree languages(see [2], [3], [5], [4]). Ceccherini-Silberstein, Coornaert, Fiorenza, and the second
author have studied decision problems and automata related to sofic tree shifts [10].
• Group Theory. Another mathematical source for the labeled trees which we study is
the area of groups of tree automorphisms. Such groups, including the well-known Grigorchuk
group (introduced in [13]) and Gupta-Sidki group (introduced in [17]), which are included in
a class of groups now sometimes called GGS-groups. These groups have risen to prominence
in the last few decades after they have been used as the solution to several decades-old
open problems in group theory (see [15] for an overview for the first Grigorchuk group).
Particularly interesting classes of groups in this area include self-similar groups (see the
monograph [22] for a comprehensive overview) and branch groups (a thorough overview of
which is in [6]).
If X is a finite set, an automorphism of the right Cayley graph of X ∗ is called an
X ∗ -automorphism. The set of all X ∗ -automorphisms forms a group, which we denote by
Aut(X ∗ ). For each k ≥ 0, the set X [k] consists of all words in X ∗ whose length is at most
2

k; this set inherits a subgraph structure from that of X ∗ , and we write Aut(X [k]) for the
automorphisms of this subgraph. There is a natural group homomorphism πk : Aut(X ∗ ) →
Aut(X [k] ) given by restriction of the action of an automorphism to this finite subset. The
kernel of πk consists of elements which fix each element of X [k] and is denoted by Stab(k).
There is also an obvious homomorphism Aut(X [k+1] ) → Aut(X [k] ) for each k ≥ 0, and this
system of finite quotients and homorphisms may be used to define Aut(X ∗ ) as a profinite
topological group.
Each element g ∈ Aut(X ∗ ) corresponds a labeling of X ∗ by the finite alphabet Sym(X);
this labeling is called the portrait of g. Portraits provide a way to visualize the action of a
particular automorphism, as well as a bijective mapping from the group Aut(X ∗ ) to a full
shift over X ∗ with alphabet Sym(X). In Section 5 of [15], Grigorchuk observed that the
portraits of the closure of the first Grigorchuk group in the profinite topology on Aut(X ∗ )
formed a shift of finite type in the corresponding full shift. This led him to define a group of
finite type as a group of tree automorphisms whose portraits form a shift of finite type when
∗
considered as a subshift of (Sym(X))X .
Groups of finite type, also known as finitely constrained groups of tree automorphisms, are
characterized in the following theorem.
Theorem 1. Let G be a level-transitive group of tree automorphisms of X ∗ and s ≥ 0. The
following are equivalent.
(i) The group G is the closure of some self-similar, regular branch group H, branching
over the level s stabilizer of H.
(ii) The group G is a finitely constrained group defined by forbidden patterns of size s + 1.
The direction (i) → (ii) was proven by the second author in [27], and the direction (ii) →
(i) was shown by Grigorchuk in [15]. In [28], the second author strengthened the result (ii) →
(i) by proving that the group H may be chosen to be countable. The proofs of these results
are easily adapted to a more general definition of self-similar groups which we consider here;
for the sake of completeness, we include a proof of the more general theorem in an appendix.
Bondarenko and Samoilovych provided criteria to establish that a finitely constrained
group is topologically finitely generated [7]. In [23], the present authors applied these criteria
to show that finitely constrained groups having a certain Hausdorff dimension were not
topologically finitely generated. Additionally, the results of Fernández-Alcober and ZugadiReizabal in [12] show that if G is a GGS-group acting on a p-regular tree where p is an
odd prime, and if G has a non-constant defining vector, then G is finitely constrained (this
follows from Lemma 3.4 of [12] and Theorem 1 in that paper).
The connection between group theory and subshifts in the one-dimensional case deserves
mention as well. If the finite alphabet A is a group, then the one-sided, one-dimensional full
shift
Y over the alphabet A gains a natural group structure isomorphic to the direct product
A with elementwise group multiplication: (gh)n = gn hn for any g, h ∈ AN . An argument
n∈N

given by Kitchens in [19] for two-sided shifts over Z is easily adapted to one-sided shifts over
N to give the following theorem.

Theorem 2 (Kitchens, 1987). Let A be a finite alphabet. If G is a subset of AN which is
both a subshift and a subgroup of AN , then G is a shift of finite type.
3

Our results. In this paper, we further investigate these connections between the computational, symbolic dynamics, and group-theoretic aspects of labeled trees. Section 2 contains
the necessary details and background on the three areas outlined in the Introduction. For
∗
each action of a finite group A on a finite set X, we show how to give the full shift AX the
structure of a group, thus introducing a more general notion of self-similar groups acting
on rooted trees. In Section 3, we present examples which show that various classes of tree
languages corresponding to self-similar groups are in fact distinct, including an example to
show that Theorem 2 does not hold for shifts over arbitrary trees. However, we do not have
an example of a self-similar group whose portraits form a sofic tree shift but do not form a
tree shift of finite type, and it is possible that these two classes coincide for all self-similar
groups. Section 4 is dedicated to proving our main result, which provides sufficient conditions to show that a self-similar group corresponding to a sofic tree shift is also a finitely
constrained group.
It should be noted that, referencing an earlier version of this work, Grigorchuk and
Kravchenko showed that the portraits of the Lamplighter group do not form a sofic tree
shift( [16]).
Acknowledgements: The authors would like to thank David Carroll and Rostislav Grigorchuk for their comments on earlier versions of this work.
2. Background
2.1. Tree Shifts and Unrestricted Rabin Automata. In this section, we review background related to symbolic dynamics and computation on labeled trees, giving rigorous
definitions of some notions from the Introduction. Much of the material in this section may
be found in [10] or [26]. In some cases we will utilize the notation of [20] or [9].
Let X be a non-empty finite set. For n ≥ 0, we define X n as the set of all words of length
n in X, writing |w| = n to indicate w ∈ X n . We let
X (n) =

n−1
[
i=0

X i,

X [n] =

n
[

Xi

i=0

and

X∗ =

∞
[

X i.

i=0
∗

As we have previously seen, the elements of X can be identified with the vertices of a
regular rooted |X|-ary tree where the empty word ǫ is the root, and each vertex w ∈ X ∗ has
the set {wx}x∈X as its children. The set X n is called level n of the tree X ∗ , and the set
wX ∗ = {wu | u ∈ X ∗ } is the subtree rooted at w. A ray r in X ∗ is a subset of X ∗ that
forms an infinite directed path beginning at ǫ.
Given a finite alphabet A, a configuration is a map f : X ∗ → A. The image of w ∈ X ∗
∗
under f is called the label of f at w and is denoted by f(w) . The set AX of all configurations
is called the full tree shift.
∗
∗
For w ∈ X ∗ , the shift map at w is denoted σw : AX → AX and is defined by (σw (f ))(u) =
f(wu) . We abbreviate σw (f ) as fw . (One must be careful not to confuse fw and f(w) .) A
∗
subset S of AX is called shift-invariant if σw (S) ⊆ S for all w ∈ X ∗ .
∗
The set AX can be viewed as a compact metric space. Many alternative (but topologically
equivalent) metrics are in use; a common choice is the metric d given by d(f, g) = 0 if f = g,
and
1
d(f, g) = n , where n = inf{ k ∈ N | f|X [k] 6= g|X [k] }
2
4

if f 6= g. The set of all rays forms a compact metric space called the boundary of X ∗ , denoted
∂X ∗ .
Definition 3. A subset of a full tree shift which is topologically closed and shift-invariant
is called a tree shift.
∗

A pattern is a map p : M → A, where M is some finite, non-empty subset of AX . If
the domain of a pattern p is X (n) for some n, we say that p is a block of size n. Given
∗
a configuration f in AX , a pattern p with domain M, and some w ∈ X ∗ , we say that p
appears in f at w if fw |M = p. Given a set F of forbidden patterns, the set
XF = {f ∈ AX

∗

| for all p ∈ F , p does not appear in f }

defines a tree shift. Conversely, any tree shift X can be defined by declaring the forbidden
patterns to be those that do not appear in any configuration of X . Different sets of forbidden
patterns may define the same tree shift. In the case that there exists a finite set of forbidden
patterns F such that X = XF , we say that X is a tree shift of finite type. By extending
patterns as necessary, we may assume that the forbidden patterns are all blocks of the same
size.
∗
When |X| = 1, the shift AX may be viewed as the one-sided full shift over N. In that
case, a shift X is called sofic if the blocks of X form a regular language (accepted by some
finite state automaton). Analogously, we define sofic tree shifts to be those which can be
accepted by a particular type of tree automaton.
Definition 4. An unrestricted Rabin graph is a 4-tuple A = (S, X, A, T ) with X and A
non-empty finite sets, S a non-empty set, and T a subset of S × A × S X . X is called the
tree alphabet, S is called the state set or vertex set, A is called the label alphabet, and T is
called the set of transition bundles.
Definition 5. An unrestricted Rabin automaton is an unrestricted Rabin graph with a finite
state set.
∗

To any configuration f ∈ AX , we can associate an unrestricted Rabin graph Af =
(X ∗ , X, A, Tf ) with
Tf = {(w; f(w) ; (wx)x∈X ) | w ∈ X ∗ }.
Given two unrestricted Rabin graphs A1 = (S1 , X, A, T1 ) and A2 = (S2 , X, A, T2 ), a
homomorphism from A1 to A2 is a map α : S1 → S2 such that (α(s); a; (α(sx))x∈X ) ∈ T2
whenever (s; a; (sx )x∈X ) ∈ T1 . We may also say, in an overloading of notation, write the
homomorphism α as α : A1 → A2 .
∗

Definition 6. Let A be an unrestricted Rabin automaton. An element f of AX is accepted
by A if there exists a homomorphism αf : Af → A. The language A is the set of all
configurations accepted by A. A tree shift X is called sofic if there exists an unrestricted
Rabin automaton A such that X = XA .
The class of sofic tree shifts is equal to the class of tree shifts which are the image of some
tree shift of finite type under a continuous, shift-equivariant map called a cellular automaton
(see [10, Theorem 1.7] for the equivalence). From this it follows that the language of an
unrestricted Rabin automaton A is a tree shift; we denote this shift by XA . Cellular automata
are a very interesting and active area of study, but they will not enter into the rest of our
discussion.
5

2.2. Other Classes of Tree Automata. In this subsection, we introduce two additional
classes of tree automata, Büchi automata and Rabin automata. They were initially introduced (under different names) by Rabin in [25] and [24], respectively. (Note that what we
call Büchi automata are also called special automata.)
Definition 7. Let A be a finite alphabet and X be a finite, non-empty set. A Büchi automaton B (over X with alphabet set A) is a 6-tuple B = (S, X, A, T , I, F ) where (S, X, A, T )
is an unrestricted Rabin automaton, I is a non-empty subset of S (called the set of initial
states) and F ⊂ S (called the set of accepting states).
Definition 8. Let A be a finite alphabet and X be a finite, non-empty set. A Rabin
automaton R (over X with alphabet set A) is a 6-tuple R = (S, X, A, T , I, F ), where
(S, X, A, T ) is an unrestricted Rabin automaton, I is a non-empty subset of S (called the
set of initial states) and F (the set of accepting sets) is a collection of subsets of S.
Acceptance in these classes of automata is based on the notion of a successful run.
∗

Definition 9. Let f ∈ AX be a configuration and A = (S, X, A, T , I, F ) be either a Büchi
or Rabin automaton over X with alphabet A. A run of A on f is a map r : X ∗ → S such
that
• r is a homomorphism from the unrestricted Rabin automaton Af to the unrestricted
Rabin automaton (S, X, A, T )
• r(ǫ) ∈ I
∗

For a configuration f ∈ AX , a ray π ∈ ∂X ∗ , and a run r of either a Büchi or Rabin
automaton, let r∞ (π, f ) = {s ∈ S | r −1 (s) ∩ π is infinite }. A run r of a Büchi automaton
B on a configuration f is called successful if r∞ (π, f ) ∩ F =
6 ∅, for all π ∈ ∂X ∗ . For a
∗
Rabin automaton R, a run r is successful if for all π ∈ ∂X , there exists F ∈ F (which may
depend on π) such that r∞ (π, f ) = F . A configuration f is accepted by a Rabin (or Büchi)
automaton A if there exists a successful run r of A on f .
For a Rabin (Büchi) automata A, the language of A is written as L(A) and defined as
L(A) = {f ∈ AX

∗

| there exists a successful run r of A on f }.

∗

A set W ⊂ AX is Rabin (Büchi) recognizable if there exists a Rabin (Büchi) automaton A
such that W = L(A).
It is a standard exercise to show that both Rabin and Büchi languages are closed under
taking finite unions, finite intersections, and projections. It is well-known, but much more
challenging to prove, that Rabin languages are closed under taking complements, while Büchi
languages are not.
We may view any Büchi tree automaton B = (S, X, A, T , I, F ) as a Rabin tree automaton
R = (S, X, A, T , I, F ′ ) where F ′ = {F ⊆ S | F ∩ F =
6 ∅}, so any Büchi recognizable set
is Rabin recognizable. Similarly, any sofic shift is Büchi recognizable, since we may consider
an unrestricted Rabin automaton as a Büchi automaton by taking all states to be both
initial and final (initial and final states are not needed to accept a closed, shift-invariant set
– see [10, Section 9] for more details). Also, any tree shift of finite type is a sofic tree shift
(see [10, Theorem 1.9]).
6

2.3. Group Structure. When A is a finite group which acts on a set X, the elements in
the infinite iterated wreath product A ≀X A ≀X . . . correspond to labeled trees in the full tree
∗
shift AX . In this subsection, we give the details of this construction and discuss background
from the case of tree automorphisms. The construction we give here is a generalization of
self-similar groups of tree automorphisms. In this case, the alphabet is a subgroup Sym(X),
the full symmetric group on X, with its standard faithful action on X. Here, the infinitely
iterated permutational wreath product
Sym(X) ≀X Sym(X) ≀X Sym(X) ≀ . . .
yields a group of tree automorphisms of X ∗ . However, there is no reason why one absolutely
must restrict the alphabet of tree shift to be a subgroup of Sym(X), and we would like to
be able to discuss meaningful group structures for any tree subshift. .
For any group G, we will write eG for the identity of G.
Let A be a group. Given a set X, a (left) group action is a map A × X → X, given
by (g, x) → gx such that ex = x and g(hx) = (gh)x for all g, h ∈ A and x ∈ X. Right
actions are defined analogously. Given x ∈ X and g ∈ A, we denote a left action
Q of g on x
g
X
by g(x) and a right action of g on x by x . If B is a group, the set B = x∈X B of all
functions from X to B is a group with componentwise multiplication. The left action of A
on X induces a right action of A on B X given by
(ba )x = ba(x) .
This action of A on B X allows us to define the semi-direct product A ⋉ B X , whose
underlying set is A × B X and where multiplication is given by
(a1 , b1 )(a2 , b2 ) = (a1 a2 , ba12 b2 )
for a1 , a2 ∈ A and b1 , b2 ∈ B X . The group A ⋉ B X is called the permutational wreath product
of (A, X) and B, and is denoted A ≀X B.
In the case where A, B are groups with left actions on the sets X, Y , respectively, the
group A ≀X B has a left action on the set X × Y , given by
(a, b)(x, y) = (ax, bx y).
If X is a finite set and A is a finite group with some left action φ on X, the permutational
(2)
wreath product A ≀X A corresponds naturally to the set AX and acts on X 2 . The action of
A on X naturally induces an action of A on (A ≀X A)X , leading to the permutational wreath
product
A ≀X (A ≀X A),
(3)

which acts on X 3 and is identified with AX . The groups (A ≀X A) ≀X A and A ≀X (A ≀X A) are
canonically isomorphic, so we will omit parentheses. Iterating this construction n times yields
a group which acts on X n . It is clear from the construction that the action of A ≀ A ≀ . . . ≀ A
|
{z
}
n times

on X n preserves prefixes of words. Thus this group also has a well-defined action on X k for
0 ≤ k ≤ n, which extends to an action on X (n+1) . The infinitely iterated wreath product
A ≀X A ≀X A . . . ,
7

naturally acts on X n for each n ≥ 1, and thus it acts on X ∗ . The infinite iterated wreath
product group whose construction we have just described will henceforth be denoted by
F (A, X, φ) and called the full tree shift group with alphabet A, action φ and space X.
Note that
G = F (A, X, φ) = A ≀X A ≀X A . . . = A ≀X (A ≀X A ≀X A . . .) = A ≀X G = A ⋉ GX ,
and thus any element g can be uniquely expressed as (a, (gx )x∈X ), with a ∈ A and gx ∈ G.
For each x ∈ X, the element gx is the section of g at x. We define gǫ = g, and for a nontrivial
word w = vx ∈ X ∗ with v ∈ X ∗ and x ∈ X, we recursively define gvx = (gv )x .
Note that when writing the elements in the semi-direct product A ⋉ GX , we often omit
the outside parentheses and simply write the element as a(gx )x∈X , When |X| = 2, we write
elements in the form a(g0 , g1 ).
Definition 10. A subgroup H of G = F (A, X, φ) is self-similar if hw ∈ H for all h ∈ H
and w ∈ X ∗ .
There is a homomorphism αǫ : F (A, X, φ) → A given, for g = (a, (gx )x∈X ) by
αǫ (g) = a.
We call αǫ (g) called the root label of g, and we define αw : F (A, X, φ) → A by αw (g) = αǫ (gw ).
∗

Definition 11. The portrait map α : F (A, X, φ) → AX is defined by
[α(g)](w) = αw (g),
and α(g) is called the portrait of g.
The portrait map is a bijection, and whenever useful, we identify an element of F (A, X, φ)
∗
with its portrait in AX . In particular, we endow F (A, X, φ) with a metric topology induced
∗
by its identification with AX . This allows us to view subgroups of F (A, X, φ) as subspaces
∗
of AX , and to study the properties of subgroups as spaces of portraits. Often, if the action
∗
φ is understood or unimportant, we may simply write F (A, X, φ) as AX .
It is an important to note that the portrait of a section, α(gv ), corresponds to the shift of
a portrait σv (α(g)), so that a subgroup of F (A, X, φ) is self-similar if and only if its portraits
∗
form a shift-invariant subset of AX . Thus, the portrait and section maps provide the correspondence between the group structure of the infinite iterated wreath product F (A, X, φ)
∗
and the structure of AX as a shift space.
Again, it should be noted the self-similar groups we consider here are a generalization of
the usual case of tree automorphisms. The following facts are well-known for self-similar
groups of tree automorphisms, and also hold in the more general case discussed here.
Lemma 12. Let X be a finite set and A be a finite group acting on X via φ. Let g, h ∈
F (A, X, φ), x ∈ X, and u, v, w ∈ X ∗ . Then the following hold.
(1) (gh)w = gh(w) hw
(2) (gh)(w) = g(h(w)) h(w)
(3) (gu )v = guv
(4) (g −1)(v) = (gg−1 (v) )−1
(5) Let supp(g) = {w ∈ X ∗ | g(w) 6= eA }. If supp(g) ⊆ wX ∗ and supp(h) ⊆ vX ∗ with
wX ∗ ∩ vX ∗ = ∅, then gh = hg.
8

A self-similar group which is a tree shift of finite type (under the portrait map α) is called
a finitely constrained group, and a self-similar group which is also a sofic tree shift (under
the portrait map α) is called a sofic tree shift group. The reader should be warned that the
term sofic is used differently in group theory, as in [29]. However, we use the word sofic to
describe the tree shift, as in the traditional sense of symbolic dynamics.
∗
For the rest of this section, we write AX for F (A, X, φ). For u ∈ X ∗ and a subgroup
∗
H ≤ AX , we define the stabilizer of u as
StabH (u) = {f ∈ AX

∗

| f (u) = u}.

and the level n stabilizer (for n ≥ 0) is the subgroup defined as
StabH (n) = {f ∈ AX

∗

| f (u) = u for all u ∈ X n } =

\

StabH (u).

u∈X n
∗

The subgroup Triv(n) of AX is given by
Triv(n) = {f ∈ AX

∗

| f(u) = eA whenever |u| < n},
∗

∗

Triv(n) is always a normal subgroup of AX . For a subgroup H ≤ AX , we define
TrivH (n) = Triv(n) ∩ H.
The group TrivH (n) is a normal subgroup of H. Note that TrivH (n) is always a subgroup
of StabH (n); if the action of A on X is faithful, then the two groups coincide.
Definition 13. A subgroup H of Aut(X ∗ ) is a regular branch group over StabH (n) if and
only if it is level-transitive and for all h0 , . . . , hk−1 ∈ StabH (n), the element (h0 , h1 , . . . , hk−1 )
is also an element of StabH (n).
∗

Definition 14. A subgroup H of AX is a symbolic branch group, symbolically branching
over TrivH (n) if and only if h0 , . . . , hk−1 ∈ TrivH (n), the element (h0 , h1 , . . . , hk−1) is also
an element of TrivH (n).
In the case of a faithful, level-transitive action, a group H is a regular branch group
over StabH (n) precisely when it is a symbolic branch group, symbolically branching over
TrivH (n). This distinction is important because level-transitivity is necessary for many
results on branch groups of tree automorphisms, but will not be necessary for our more
general definition of finitely constrained groups.
∗
∗
For each u ∈ X ∗ and subgroup H ≤ AX , there is a homomorphism φu : StabH (u) → AX
given by g 7→ gu . A self-similar group H is self-replicating if the map φu is surjective onto
∗
H for all u ∈ X ∗ . In other words, a subgroup H of AX is self-replicating if it is self-similar
and for any u ∈ X ∗ and any g ∈ H, we can find h ∈ StabH (u) such that hu = g. A subgroup
∗
H ≤ AX is level-transitive if its action on X ∗ is transitive on each X n .
3. Tree Languages for Portraits of Self-Similar Groups
In this section, we consider the portraits of self-similar groups as tree languages recognized
by various classes of infinite tree automata. In general, the different classes of configuration
subspaces discussed so far form a hierarchy as follows:
SFT ( SOFIC ( BÜCHI RECOGNIZABLE ( RABIN RECOGNIZABLE.
9

Our goal is to explore this hierarchy for the portrait spaces of self-similar groups. Henceforth, whenever A is a finite group which has a left action φ on a finite set X, we will write
∗
the iterated wreath product F (A, X, φ) as AX (suppressing reference to φ).
We begin by showing that there are Büchi-recognizable tree shift groups which are not
sofic tree shift groups.
Example 15 (A Büchi-recognizable self-similar group which is not a sofic tree shift group).
∗
Let G = AX be a full tree shift group for some finite set X, some finite group A, and some
left action φ. Let B be a proper subgroup of A. We define the subset HB to be
∗

HB = {h ∈ AX | there exists an Nh such that |v| > Nh implies that h(v) ∈ B}.
When B is the trivial group and the action φ is faithful, this corresponds to the group of
finitary tree automorphisms(as discussed in [8]) . Note that HB is self-similar. We will show
that HB is a subgroup of G. If g, h ∈ HB , then there exists N1 , N2 such that g(v) ∈ B
whenever |v| > N1 , and there exists N2 such that h−1 (v) ∈ B whenever |v| > N2 . Then,
taking N = max{N1 , N2 }, it follows that whenever |v| > N, we have
gh−1(v) = g(h−1 (v)) (h(h−1 (v)) )−1 ∈ B,
as |h−1 (v)| = |v|. Also, it is clear that HB is self-similar and self-replicating. Moreover, if
the action of H on X is transitive, then HB is level-transitive, as well. However, HB is not
closed. In fact, HB is dense in G, since for any g ∈ G, we can obtain an element h ∈ HB
which is arbitrary close to g by by choosing the appropriate n and setting h(w) = g(w) for
w ∈ X [n] , hw = eA if |w| > n . Since HB is not topologically closed, it is not sofic.
We will show that HB is Büchi. Consider the Büchi automaton B = (S, X, A, T , I, F ),
where
• S = {s1 , s2 }
• T consists of transition bundles of the following forms:
for all a ∈ A, T1,a = (s1 ; a; (s1 )x∈X ) ∈ T ;
for all b ∈ B, T1,2,b = (s1 ; b; (s2 )x∈X ) ∈ T ;
for all b ∈ B, T2,b = (s2 ; b; (s2 )x∈X ) ∈ T
• I = {s1 }
• F = {s2 }
The computation of B can be described as follows. The automaton begins in the initial
state s1 . It can remain in s1 by reading any element of A, or it can transition to s2 by
reading any element of B. Once in s2 , it will remain at s2 , at which point it can only read
elements of B. Thus a configuration is accepted by B if there exists a run which eventually
reaches s2 along every ray and never leaves that state. We claim that the set of elements
accepted by B is the same as the subgroup HB .
If h ∈ HB , with Nh such that h(v) ∈ H whenever |v| > Nh , we can define a successful run
rh : Ah → B by
(
s1 , |v| ≤ Nh
.
rh (v) =
s2 , |v| > Nh
Thus HB ⊂ L(B).
Now suppose h ∈ L(B). Let rh be a successful run of h on B. By the definition of Büchi
acceptance, each ray π must take the value s2 infinitely often. However, every transition
10

bundle in B which begins at s2 also ends at s2 , so rh (w) = s2 implies that rh (wx) = s2 for
all x ∈ X. It follows from induction that for every ray π, there is a w ∈ π such that rh only
takes the value s2 on wX ∗ . Since each ray π is contained in some such wX ∗ , and the sets
wX ∗ are open in the topology of ∂X ∗ , these sets form an open cover of ∂X ∗ . Since ∂X ∗ is
compact, we can take a finite collection {w1 , w2 , . . . , wn } such that each ray π is contained in
at least one open set from the finite collection {wi X ∗ }ni=1 and such that for each v ∈ wi X ∗ ,
rh (v) = s2 . Taking
N = max{|w1|, |w2 |, . . . , |wn |},
we have that rh (v) = s2 whenever |v| > N. However, the only transition bundles from s2
to itself are labeled by elements of B, so we have that v(h) ∈ B whenever |v| > N. Thus
h ∈ HB .
The next example utilizes the standard construction of a Rabin recognizable subset which
is not Büchi recognizable. The key observation is that this tree language describes the
portraits of a self-similar group.
Example 16 (A Rabin-recognizable tree shift group which is not Büchi-recognizable). Let
X = {0, 1} be a finite set and A = C2 = {id, σ} be the cyclic group of order 2 acting
transitively on X. Let
∗

H = {g ∈ AX | every ray in g has only finitely many vertices with nontrivial label}.
The set H is a well-known example of a tree language which is Rabin but not Büchi
(see [26]). It is clear that H is self-similar.
∗
∗
Notice that H is a subgroup of AX , since an element h ∈ AX is in H if and only if for
every ray π, there exists an N such that for all v ∈ π with |v| > N, h(v) = id. Let g, h ∈ H,
and let π be a ray in gh−1 . Since g ∈ H and h−1 (π) is a ray in X ∗ , there exist an N1 such
that (g)(h−1 (v)) is the identity whenever |h−1 (v)| = |v| > N1 . Since h ∈ H, there exists an
N2 such that h(v) is the identity whenever |v| > N2 . Taking N = max{ N1 , N2 }, it follows
that whenever |v| > N
gh−1 (v) = g(h−1 (v)) (h(h−1 (v)) )−1 = id,
Thus H is a self-similar, self-replicating, level-transitive subgroup which is Rabin-recognizable
but is not Büchi-recognizable.
The next example shows that there exist tree shift groups over {0, 1}∗ which are not finitely
constrained groups, in contrast to the one-dimensional case considered by Kitchens([19]).
Example 17 (A tree shift group which is not finitely constrained). Let X = {0, 1}, A =
∗
Sym(X) = {id, σ}, and let A act faithfully on X by permutations, so that the group AX =
Aut(X ∗ ). We use id to represent the identity of C2 so that e can be reserved here for the
identity of Aut(X ∗ ). Let a = σ(e, a) ∈ Aut(X ∗ ). In terms of labels,
(
σ, if w = 1n for some n
a(w) =
.
id, otherwise .
Any section of a is either the identity or a, so the group generated by {1, a} is self-similar.
This group O is called the odometer group, as it “rolls over” any word consisting of all 1’s.
We claim that O is not a finitely constrained group. However, we will present a different
proof which uses the structure of the portraits of O.
11

It follows by induction that
a2n = id(an , an )
and
a2n+1 = σ(an , an+1 ).
n
2n+1
= id, while a(ǫ)
= σ. We also observe that a2 ∈ Triv(n) for all

Also, we note that a2n
(ǫ)
n ∈ N.
Since O is self-similar, the closure O is a tree shift group, We will show that O is not
finitely constrained. Suppose that O is finitely constrained by some set F of forbidden blocks
∗
of size n + 1. Consider the element g ∈ AX with root label gǫ = id and sections given by
n
g0 = 1G , g1 = a2 . Each pattern in g is a pattern contained in a, so g must be in the shift
space XF .
Since we assumed XF = O, there must be a sequence of elements in O which converge to g.
Since gǫ = id, this sequence must eventually consist of even powers of a, so
a2ni → g.
Then (a2ni )0 → g0 and (a2ni )1 → g1 . However, (a2ni )0 = (a2ni )1 , but g0 6= g1 . Therefore
we have a contradiction, and O is not finitely constrained.
This result can also be shown using a stronger result that relies on the stucture of regular
branch groups.
Proposition 18. Let G be a level-transitive group of tree automorphisms such that G satisfies an algebraic law or has a nontrivial center. The topological closure G is not finitely
constrained.
Proof. If a group G satisfies an algebraic law or has a nontrivial center, then so does its
closure G. If G is finitely constrained, it must be a regular branch group by Theorem 1. It
follows from a result in [1] that a group that satisfies a law can not be a branch group. It is
also known that the center of a regular branch group must be trivial [14, Theorem 2(c)]. 
At present, we do not know if all sofic tree shift groups are finitely constrained, and that
question will be addressed in the next section.
4. Sofic Tree Shift Groups and Finitely Constrained Groups
The remainder of this paper will be dedicated to describing sufficient conditions to ensure
that a sofic tree shift group is finitely constrained.
4.1. Branching Structure and Sofic Tree Shift Groups. In this part, we outline the
structure of certain elements and subgroups of sofic tree shift groups. We begin by introducing the idea of grafting one labeled tree onto another (see [18, page 266])
∗

Definition 19. Let a, b ∈ AX and v ∈ X ∗ . The grafting of b onto a at v is the element
∗
g[a,b,v] of AX given by
(

b(u) , w = vu ∈ vX ∗
g[a,b,v] (w) =
a(w) , w 6∈ vX ∗

Lemma 20 (Grafting Lemma). Let A be an unrestricted Rabin automaton and suppose
a, b ∈ L(A) and v ∈ X ∗ such that
12

(i) a(v) = b(ǫ)
(ii) there exist homomorphisms αa : X ∗ → S by which A accepts a and αb : X ∗ → S by
which A accepts b such that αa (v) = αb (ǫ).
Then A accepts the grafting of b on a at v.
Proof. Define a map α[a,b,v] : X ∗ → S by
(
α[a,b,v] (w) =

αb (u), w = vu ∈ vX ∗
αa (w), w 6∈ vX ∗

.

We claim that this is a homomorphism by which A accepts g[a,b,v] . We must
show that for

∗
any w ∈ X , the transition bundle α[a,b,v] (w); g[a,b,v](w); (α[a,b,v] (wx))x∈X ∈ T .
There are three cases. If w ∈ vX ∗ and w = vu, then we have


α[a,b,v] (w); (g[a,b,v])(w) ; (α[a,b,v] (wx))x∈X = αb (u)); b(u) ; (αb (ux))x∈X ,

and (αb (u)); b(u) ; (αb (ux))x∈X ) ∈ T since αb accepts b. If w 6∈ vX ∗ and wx 6= v for any
x ∈ X, then α[a,b,v] (w) = αa (w), and


α[a,b,v] (w); g[a,b,v] )(w) ; (α[a,b,v] (wx))x∈X = αa (w); a(w); (α[a,b,v] (wx))x∈X

where αa (w); a(w) ; (α[a,b,v] (wx))x∈X ) ∈ T since αa accepts a. Finally, if v = wx for some
x ∈ X, then using the fact that α[a,b,v] (wx) = αb (v) = αa (v) gives that


α[a,b,v] (w); (g[a,b,v])(w) ; (α[a,b,v] (wx))x∈X = αa (w); a(w) ; (αa (wx))x∈X

and, again, αa (w); a(w) ; (αa (wx))x∈X ∈ T since αa accepts a. This completes the proof.

∗

Definition 21. For v ∈ X ∗ and f ∈ AX , we denote g[eG ,f,v] by δv (f ). Note that from the
definition, δv (g) is given by
(
g(z) , w = vz for some z ∈ X ∗
(δv (g))(w) =
eA , otherwise
The following useful properties of the δ operator are easily verified.
∗

Lemma 22. For all g, h ∈ AX and v, w ∈ X ∗ , the following hold.
(i) If w = vu, then [δw (g)]v = δu (g)
(ii) δv (δw (g)) = δvw (g)
(iii) If |w| = k and g ∈ TrivG (n), then δw (g) ∈ TrivG (n + k).
(iv) δv (gh) = δv (g)δv (h)
These δ operators provide the appropriate dynamical viewpoint for a regular branch group
in this setting.
∗

Definition 23. Let G be a subgroup of the full tree shift AX , and k ≥ 1. We say that G
is a symbolic branch group, symbolically branching over TrivG (k) if δx (g) ∈ TrivG (k + 1) for
all g ∈ TrivG (k) and x ∈ X.
13

Proposition 24. Let G be a subgroup of Aut(X ∗ ).Then G is a regular branch group if it is
level-transitive and it is a symbolic branch group over TrivG (k).
Using this notion, Theorem 1 may be generalized to the case of self-similar groups which
are considered here. The proof is essentially a reproduction of those found in [15] and [27];
we include it in the Appendix for the sake of completeness.
For the remainder of this subsection, we assume A is a finite group with identity element
eA , and let X be a finite alphabet. We also fix an action φ of A on X, and identify the
∗
full tree shift group F (A, X, φ) with the full tree shift AX . Also, we let G be a subgroup
∗
∗
of F (A, X, φ) = AX such that the portraits of G form a sofic tree subshift of AX . The
identity of G is denoted by eG . Additionally, we let A = (S, X, A, T ) be an unrestricted
Rabin automaton so that G = L(A), and assume that |S| = N.
Lemma 25. If g ∈ G and αg : X ∗ → S is a homomorphism by which A accepts g, then
there exists an integer k = k(g) satisfying the following conditions:
(i) for any w ∈ X k , the restriction of α to the vertices in the path from ǫ to w is not
injective
(ii) |αg (X [k] )| = |αg (X [k+1])|
(iii) 1 ≤ k ≤ 2N − 1.
Proof. Condition (i) is satisfied for any n ≥ N, by applying the Pigeonhole Principle to the
labels of the vertices in the path from ǫ to a vertex w ∈ X n . To see (ii), note that the map
ψ : n 7→ |α(X [n])| is a nondecreasing function, bounded above by N, with ψ(N) ≥ 1. Thus,
there must be a k ≤ 2N − 1 such that conditions (i) and (ii) are satisfied.

Henceforth, if g, we will write k(g) for the minimal k from Lemma 25.
Lemma 26. If g ∈ TrivG (2N) via a homomorphism αg , then there exists a homomorphism
αe that accepts the identity such that αe and αg agree on X [k(g)] .


Proof. Let k = k(g). By the previous lemma, αg X [k] = αg X [k+1] . Note that for all w ∈
X [k] , the transition bundle (αg (w); eA ; (αg (wx))x∈X ) must be in T . For each s ∈ αg (X [k] ),
choose a word v ∈ X [k] such that αg (v) = s and denote v by βg (s). We now define a
homomorphism αe : X ∗ → S by which A accepts eG . If w ∈ X [k] , set αe (w) = αg (w). For
n ≥ k + 1, we recursively define αe on X n by setting αe (wx) = αg (βg (αe (w))x).
To see that αe is a homomorphism by which A accepts the identity, note that αg and αe
agree on X [k] , and that for all v of length greater than k, we must have the transition bundle
(αe (v); eA ; (αe (vx))x∈X ) ∈ T , since by construction
(αe (v); eA ; (αe (vx))x∈X )) = (αg (v ∗ ); eA ; (αg (v ∗ x))x∈X )
where v ∗ ∈ X k denotes βg (αe (v)). This completes the proof.



Proposition 27. Assume g ∈ TrivG (2N), k = k(g), and v ∈ X [k] and u is a prefix of v. If
there exists a homomorphism αg : X ∗ → S by which A accepts g such that αg (u) = αg (v),
then δv (gu ) ∈ TrivG (2N + |v| − |u|).
Proof. Assume αg (u) = αg (v) = t ∈ S. By the previous Lemma, there exists αe which
accepts eG such that αe and αg agree on X [k] . Since G is self-similar, there is a homomorphism
14

αgu by which A accepts gu such that αgu (ǫ) = αg (u). (The map αgu given by αgu (w) = αg (uw)
is easily seen to be such a homomorphism.) Now we have that
αgu (ǫ) = αe (u) = αe (v)
and
(gu )(ǫ) = g(u) = eA = (eG )(v) .
Applying the Grafting Lemma yields the desired result.



Corollary 28. Assume g ∈ TrivG (2N) , k = k(g), and u, v ∈ X [k] with u a proper prefix of
v and |u| = j. If there exists a homomorphism αg : X ∗ → S by which A accepts g such that
αg (u) = αg (v), then there exists u′ ∈ X j+1 such that δu′ (gu ) ∈ TrivG (2N + 1)
Proof. By the previous proposition, we know that δv (gu ) ∈ Triv(2N + |v| − |u|). Since v > u,
can write v = v1 u′ where v1 is some word (possibly empty) and |u′| = |u| + 1. Then we have

that [δv (gu )]v1 = δu′ (gu ).
Recall that for any group, conjugation is a right action of the group on itself given by
∗
g = h−1 gh. Given G ≤ AX , the normalizer of G, denoted byNAX ∗ (G), consists of the
∗
elements of AX which leave G fixed under conjugation; i.e.,
h

NAX ∗ (G) = {h ∈ AX

∗

| g h ∈ G for all g ∈ G}.

The following lemma is proven in [28, Lemma 1] for self-similar groups of tree automorphisms. We will not reproduce the proof here, since it is a lengthy computation which is
easily generalized to our current setting.
∗

Lemma 29. Let g, h ∈ AX and u ∈ X ∗ . Then (δu (h))g = δv (h(gv ) ), where v = g −1 (u).
We use this Lemma in the following Proposition.
∗

Proposition 30. Let G be a subgroup of AX such that NAX ∗ (G) contains a self-similar,
self-replicating, level-transitive subgroup. If δu (g) ∈ G for some g ∈ G and u ∈ X n , then
δv (g) ∈ G for all v ∈ X n .
Proof. Suppose δu (g) ∈ G for some u ∈ X n and g ∈ G. Let v ∈ X n be arbitrary. Let
N = NAX ∗ (G) be the normalizer of G, and assume that N contains a self-similar, selfreplicating, level-transitive subgroup M. Since M is level-transitive, there exists f ∈ M
such that f (v) = u. Since M is self-similar, (fv )−1 ∈ M, and since M is self-replicating,
′
there exists f ′ ∈ StabM (v) such that (f ′ )v = (fv )−1 . Then (δu (g))f f ∈ G since M normalizes
G. Moreover, from these observations and Lemma 29, it follows that
f ′
′
(δu (g))f f = (δu (g))f
f ′
= δv (g fv )
since v = f −1 (u)


−1
since v = (f ′ )−1 (v)
= δv g fv (fv )
= δv (g)


15

4.2. Main Results. We now have the necessary framework in place to prove our desired
results.
∗

Theorem 31. Let G be a subgroup of AX . If NAX ∗ (G) contains a self-similar, selfreplicating, level-transitive subgroup, then G is a sofic tree shift group if and only if G is
a finitely constrained group.
Proof. Since every finitely constrained group is a sofic tree shift group, we only need to prove
one direction. Since G is a sofic tree shift group, there exists an unrestricted Rabin automaton
AG such that L (A) = G. Assume that AG has a state set S such that |S| = N. We will
prove that G is a regular branch group over the subgroup TrivG (2N). Let g ∈ TrivG (2N)
and αg : X ∗ → S be a homomorphism by which A accepts g. Let k = k(g).
For w ∈ X k , let µ(w) be the shortest prefix of w such that the state αg (µ(w)) is repeated
in the path from ǫ to w. Let
Bg = {µ(w) | w ∈ X k },
and construct a set Cg from Bg as follows: if b, b′ ∈ Bg with b a proper prefix of b′ , remove b′ .
It is clear that after the inevitable termination of this procedure, Cg satisfies the following
conditions
(i) for any u ∈ X k , there is a prefix of u in C
(ii) no word in C is a prefix of another word in C
Q
Then, for any g ∈ TrivG (2N), we can write g = c∈C(g) δc (gc ). For distinct elements
c, c′ ∈ C, the element δc (gc ) and δc′ (gc′ ) commute, as they are supported on disjoint subtrees.
Let x ∈ X. By Corollary 28 and Proposition 30, the element
Q δxc (gx ) ∈ TrivG (2N + 1) for all
c ∈ C. Hence TrivG (2N + 1) also contains the product c∈C δxc (gc ). Further, we note that
Y
Y
δxc (gc ) =
δx (δc (gc ))
c∈C

c∈C

= δx

Y

c∈C

δc (gc ))

!

= δx (g)

Therefore G is a regular branch group over the subgroup TrivG (2N), and G is finitely constrained.

Corollary 32. The closure of the odometer is not a sofic tree shift group.
Proof. Let O represent the odometer group. Since O is a self-similar, self-replicating, leveltransitive subgroup of O and we have shown that O is not finitely constrained, this result
follows immediately from Theorem 31.

Proposition 33. Let G be a self-similar, level-transitive group of tree automorphisms such
that G, or its normalizer in Aut(X ∗ ), contains a self-replicating,level-transitive subgroup. If
G satisfies an algebraic law, or G has a nontrivial center, then the topological closure G is
not Rabin-recognizable.
Proof. Note that G is self-similar, level-transitive, and topologically closed. Suppose G is
Rabin-recognizable. Then it would be a sofic tree shift by [10, Theorem 1.7], and hence, by
16

Theorem 31, a finitely constrained group. By Proposition 18, this implies that G can not
obey an algebraic law or have a nontrivial center.

References
[1] Miklós Abért. Group laws and free subgroups in topological groups. Bulletin of London Mathematical
Society, 37(4):525–534, 2005.
[2] Nathalie Aubrun and Marie-Pierre Béal. Decidability of conjugacy of tree-shifts of finite type. In Susanne
Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris Nikoletseas, and Wolfgang Thomas, editors,
Automata, Languages and Programming, volume 5555 of Lecture Notes in Computer Science, pages 132–
143. Springer Berlin Heidelberg, 2009.
[3] Nathalie Aubrun and Marie-Pierre Béal. Sofic and almost of finite type tree-shifts. In Farid Ablayev
and ErnstW. Mayr, editors, Computer Science Theory and Applications, volume 6072 of Lecture Notes
in Computer Science, pages 12–24. Springer Berlin Heidelberg, 2010.
[4] Nathalie Aubrun and Marie-Pierre Béal. Tree algebra of sofic tree languages. Soumis, 2011.
[5] Nathalie Aubrun and Marie-Pierre Béal. Sofic tree-shifts. Theory of Computing Systems, 53(4):621–644,
2013.
[6] Laurent Bartholdi, Rostislav I. Grigorchuk, and Zoran Sunik. Branch groups. In Handbook of Algebra,
volume 3, pages 989–1112. North-Holland, Amsterdam, 2003.
[7] Ievgen V. Bondarenko and Igor O. Samoilovych. On finite generation of self-similar groups of finite type.
International Journal of Algebra and Computation, 23(01):69–79, 2013.
[8] A.M. Brunner and Said Sidki. On the automorphism group of the one-rooted binary tree. Journal of
Algebra, 195(2):465–486, 1997.
[9] Tullio Ceccherini-Silberstein and Michael Coornaert. Cellular Automata and Groups. Springer, Berlin,
2010.
[10] Tullio Ceccherini-Silberstein, Michael Coornaert, Francesca Fiorenzi, and Zoran Šunić. Cellular automata between sofic tree shifts. Theoretical Computer Science, 506:79–101, 2013.
[11] Michel Coornaert and Athanase Papadopoulos. Symbolic dynamics and hyperbolic groups. Springer,
1993.
[12] Gustavo A. Fernández and Amaia Zugadi-Reizabal. GGS-groups: Order of congruence quotients and
Hausdorff dimension. Transactions of the American Mathematical Society, 366(4):1993–2017, 2014.
[13] R.I. Grigorchuk. On Burnside’s problem on periodic groups. Funktsionalyi Analiz i ego Prilozheniya,
14(1):53–54, 1980.
[14] R.I. Grigorchuk. Just infinite branch groups. In Marcus du Sautoy, Dan Segal, and Aner Shalev, editors,
New Horizons in pro-p Groups, volume 184 of Progress in Mathematics, pages 121–179. Birkhuser
Boston, 2000.
[15] Rostislav Grigorchuk. Solved and unsolved problems around one group. In Laurent Bartholdi, Tullio
Ceccherini-Silberstein, Tatiana Smirnova-Nagnibeda, and Andrzej Zuk, editors, Infinite Groups: Geometric, Combinatorial and Dynamical Aspects, volume 248 of Progress in Mathematics, pages 117–218.
Birkhuser Basel, 2005.
[16] Rostislav Grigorchuk and Rostyslav Kravchenko. On the lattice of subgroups of the lamplighter group.
International Journal of Algebra and Computation, 24(06):837–877, 2014.
[17] Narain Gupta and Saı̈d Sidki. On the Burnside problem for periodic groups. Mathematische Zeitschrift,
182(3):385–388, 1983.
[18] Bakhadyr Khoussainov and Amil Nerode. Automata Theory and Its Applications. Birkhäuser, 2001.
[19] Bruce P. Kitchens. Expansive dynamics on zero-dimensional groups. Ergodic Theory and Dynamical
Systems, 7(2):249–261, 1987.
[20] Bruce P. Kitchens. Symbolic Dynamics. One-Sided, Two-Sided, and Countable State Markov Shifts.
Universitext, Berlin, 1998.
[21] Douglas Lind and Brian Marcus. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, New York, 1995.
[22] Volodymyr Nekrashevych. Self-Similar Groups, volume 117 of Mathematical Surveys and Monographs.
American Mathematical Society, 2005.
17

[23] Andrew Penland and Zoran Šunić. Finitely constrained groups of maximal Hausdorff dimension. Journal
of The Australian Mathematical Society, 100, 2016.
[24] Michael Rabin. Decidability of second-order theories and automata on infinite trees. Transactions of the
American Mathematical Society, 141:1–35, 1969.
[25] Michael Rabin. Weakly definable relations and special automata. Studies in Logic and the Foundations
of Mathematics, 59:1–23, 1970.
[26] Wolfgang Thomas. Automata on infinite objects. In Jan van Leeuwen, editor, Handbook of theoretical
computer science (vol. B), pages 133–191. MIT Press, Cambridge, MA, USA, 1990.
[27] Zoran Šunić. Hausdorff dimension in a family of self-similar groups. Geometriae Dedicata, 124(1):213–
236, 2007.
[28] Zoran Šunić. Pattern closure in groups of tree automorphisms. Bulletin of Mathematical Sciences,
(1):115–127, 2011.
[29] Benjamin Weiss. Sofic groups and dynamical systems. Sankhy: The Indian Journal of Statistics, Series
A, 62(3):pp. 350–359, 2000.

Appendix A. Characterization of Finitely Constrained Groups
∗

Theorem 34. Let G be a subgroup of the full tree shift AX . G is a finitely constrained
group defined by patterns of size n ≥ 1 if and only if G is the closure of group H which is a
symbolic branch group branching symbolically over TrivH (n − 1).
Proof. Let A be a finite group and X = {x1 , x2 , . . . , xm } be a finite set on which A acts.
Assume that G is a finitely constrained group defined by a set F of forbidden patterns of
size n. Let g ∈ TrivG (n − 1) and x ∈ X. Observe that δx (g) ∈ Triv(n), and we must show it
is also in G. Note that all labels on X [s] are trivial, so no elements of F occur at any word of
length less than n − 1 for δx (g). The sections of δx (g) are either g or trivial, so the sections
do not contain any elements of F , either. As no forbidden patterns occur anywhere in δx (g),
it follows that δx (g) ∈ G. Thus G is a symbolic branch group, symbolically branching over
TrivG (n − 1).
Suppose that G = H, where H is a regular branch group, branching over TrivH (n − 1).
Recall that the quotient group H/ TrivH (n) is finite, and its elements coincide with the
patterns of size n which appear in X [n−1] in H. By self-similarity, these are exactly the same
patterns of size n which appear in H.
[n−1]
Let F be the set of elements which are in AX
but not in H/ TrivH (n − 1). We let the
tree shift group GF be the set of all elements which do not contain any patterns from F .
We claim that G = GF . First, we show that G ≤ GF . Suppose that a forbidden pattern
appears at v in some element g ∈ G. This pattern appears at the root of gv , which is in G
by self-similarity. Since G = H, there is a sequence of elements {hn } in H which converge
to gv . But then, for some m, (hm )|X [n] = gv on the restriction to X [n] , so the pattern appears
in H/T rivH (n − 1). This is a contradiction, so we must have G ≤ GF .
Now we show that GF ⊆ G. For any g ∈ GF , we will exhibit a sequence {hn } of elements
in H which converges to g. The construction is by induction on s + j. Suppose g ∈ GF ,
then since g avoids the forbidden patterns at the root, g|X [n] = (h1 )|X [n] for some h1 ∈ H.
Now suppose that there exists hk such that gh−1
k ∈ TrivH (n) whenever n ≤ s + k, and let
n = s + k + 1.
Let f = h−1
n−1 g, This is in Triv H (n − 1), and since hn−1 ∈ H ⊆ GF , and g ∈ GF , it follows
that f ∈ GF . Since GF is self-similar, this implies that the sections gx ∈ GF for all x ∈ X.
18

Each section fx is in TrivH (n−2), so by the induction hypothesis, for all x ∈ X, there exist
fx′ such that (fx′ )−1 fx ∈ Triv(n−1). Therefore,
fx′ ∈ TrivH (s−1). Since H is a regular branch
Q
group, this implies that there exists f ′ = x∈X δx (fx′ ) = (fx′ 1 , fx′ 2 , . . . , fx′ m ) ∈ TrivH (s − 1).
Then f ′−1 f ∈ Triv(n), so f and f ′ agree on their restriction to X [n] . But we note that
f ′−1 f = (f ′ )−1 h−1
n−1 g.

Therefore, if we set hn = hn−1 f ′ , we have that h−1
n g ∈ Triv(n + 1), so hn and g agree on
[n+1]
X
. Thus the sequence hn converges to g, and GF ≤ H = G.

Department of Mathematics and Computer Science, Western Carolina University, Cullowhee, NC 28723 USA
E-mail address: adpenland@email.wcu.edu
Department of Mathematics, Hofstra University, Hempstead, NY 11549 USA
E-mail address: zoran.sunic@hofstra.edu

19

