On the Complexity of the Word Problem for
Automaton Semigroups and Automaton Groups

arXiv:1611.09541v2 [cs.FL] 28 Jun 2017

Daniele D’Angelia , Emanuele Rodarob,∗, Jan Philipp Wächterc
a Institut

für Diskrete Mathematik,
Technische Universität Graz,
Steyrergasse 30, 8010 Graz, Austria
b Dipartimento di Matematica,
Politecnico di Milano,
Piazza Leonardo da Vinci, 32, 20133 Milano, Italy
c Institut für Formale Methoden der Informatik (FMI),
Universität Stuttgart, Universitätsstraße 38, 70569 Stuttgart, Germany

Abstract
In this paper, we study the word problem for automaton semigroups and automaton groups from a complexity point of view. As an intermediate concept between automaton semigroups and automaton groups, we introduce automatoninverse semigroups, which are generated by partial, yet invertible automata.
We show that there is an automaton-inverse semigroup and, thus, an automaton semigroup with a PSpace-complete word problem. We also show that there
is an automaton group for which the word problem with a single rational constraint is PSpace-complete. Additionally, we provide simpler constructions for
the uniform word problems of these classes. For the uniform word problem for
automaton groups (without rational constraints), we show NL-hardness. Finally, we investigate a question asked by Cain about a better upper bound for
the length of a word on which two distinct elements of an automaton semigroup
must act differently.
A detailed listing of the contributions of this paper can be found at the end of this paper.

Keywords: automaton groups, automaton semigroups, word problem, PSpace
2010 MSC: 20E08, 20F10, 20M05, 20M18, 68Q17, 68Q45, 20M30

1. Introduction
Traditionally, algebraic structures have been presented by specifying generators and relations. There is, however, another kind of presentation based
on finite Mealy automata. Algorithmically, it has a remarkable advantage: it
∗ Corresponding

author
Email addresses: dangeli@math.tugraz.at (Daniele D’Angeli),
emanuele.rodaro@polimi.it (Emanuele Rodaro),
jan-philipp.waechter@fmi.uni-stuttgart.de (Jan Philipp Wächter)

Preprint submitted to Elsevier

June 29, 2017

guarantees decidability of the word problem for the generated groups and semigroups. This stands in contrast to the traditional way of presenting such structures: even if the set of generators and the set of relations are both finite, one
can (finitely) present a group with undecidable word problem (a classical result
due to Boone and Novikov from the mid 50s). This means in particular that
the word problem is not decidable for every group and every semigroup. Thus,
not every group or semigroup is an automaton group or automaton semigroup,
i. e. generated by an automaton. While at first sight this seems to be a severe
limitation, automaton groups and semigroups have proven to have deep connections with many areas of mathematics from the theory of profinite groups and
complex dynamics to theoretical computer science.
Many examples of groups with interesting properties are in fact automaton
groups. The most notable example is probably Grigorchuk’s first example of a
group of intermediate (i. e. super-polynomial but sub-exponential) growth (see
e. g. [12] for an accessible introduction). The existence of such a group answers
the classical Milnor problem. This group is also an example of an infinite, finitely
generated torsion group (Burnside problem) and an amenable non-elementary
amenable group (von Neumann problem). Its discovery led to the development
of a new and exiting branch of research in group theory by Grigorchuk and
others: the study of finitely presented groups that act (transitively) on each
level of an infinite regular rooted tree (see e. g. [16]). This is just a different way
of describing automaton groups.
Decidability of the word problem for automaton groups is most often proven
by giving a (deterministic) exponential time algorithm. The idea behind this
algorithm is that one can give an exponential upper bound on the level of the
tree on which two distinct group elements act differently. For some special subclasses of automaton groups, there is a better upper bound on how many paths
in the tree need to be checked (see e. g. [2] for polynomial-activity automata, [3]
for Hanoi Tower groups, [16] for contracting automaton groups). However, as
Steinberg notes in [24], there is a more straightforward – at least from a computer science perspective – nondeterministic algorithm requiring linear space
(and, thus, also yielding a deterministic exponential time algorithm). This algorithm leads Steinberg to the question whether there is an automaton group
with a PSpace-complete word problem.
In this paper, we give some partial answers to Steinberg’s question. We
do not only consider automaton groups but also automaton semigroups. This
class is a generalization where the generating automata are not required to
be invertible. While it is less studied than automaton groups, it has attracted
quite some interest recently (for example in [1, 7, 8, 9, 11] or in the work of Cain
[6], and Cain and Brough [4, 5]). Indeed, Gillibert showed that the finiteness
problem for automaton semigroups is undecidable [10] while an answer to the
corresponding question for automaton groups is yet unknown. It turns out
that Steinberg’s algorithm is actually an algorithm for automaton semigroups
(which, of course, can also be applied for automaton groups); a fact, which
we state in Proposition 2 together with a precise analysis of its complexity.
This is interesting since we show PSpace-hardness of the word problem for
2

automaton semigroups in the uniform and non-uniform case (Proposition 5 and
Proposition 6).
Unfortunately, these proofs transfer to automaton groups only in the presence of at least a single rational constraint. To bridge this gap between automaton semigroups and automaton groups, we introduce the concept of automatoninverse semigroups.1 These semigroups are generated by invertible automata
which, however, are not necessarily complete anymore. Since we can prove that
the word problem is still PSpace-complete in that case (again, uniform and
non-uniform), we have the hope that this intermediate concept is useful when
transferring other results from automaton semigroups to automaton groups as
well.
For the uniform word problem for automaton groups (without rational constraints), we give a simple construction which shows NL-hardness (Proposition 7).
Additionally, we consider a question asked by Cain in [6, Open problem 3.6]:
is there a better upper bound on the first level of the tree on which two distinct
elements of an automaton semigroup act differently than the trivial one? This
question is related to the PSpace-completeness of the word problem and, therefore, it is probably not surprising that this upper bound cannot be significantly
lower: it must be exponential (Proposition 4).
2. Preliminaries
Fundamentals. We use A ⊔ B to denote the disjoint union of two sets A and B.
The set N is the set of natural numbers including 0 and Z is the set of integers.
Finally, R is the set of real numbers.
An alphabet Σ is a non-empty finite set of letters. By Σ∗ , we denote the
set of all finite words over the alphabet Σ, including the empty word, which we
denote by ε. Furthermore, we set Σ+ = Σ∗ \ {ε}.
We assume the reader to be familiar with basic algebra notions such as that
of a semigroup, a monoid, a group and neutral elements (for more information,
see for example the book by Howie [13]). However, we want to emphasize the
difference between a (semigroup) inverse and a group inverse. An element s of
a semigroup S is called (semigroup) inverse to another element s ∈ S if sss = s
and sss = s. In contrast, an element m of a monoid M (which may be a group)
is a group inverse of another element m ∈ M if mm = mm = 1, where 1 is the
neutral element of M . Note that in this case, m is also a (semigroup) inverse
of m but that the converse does not hold in general. For instance, consider the
monoid {1, 0} with the multiplication 1 · 1 = 1 and 1 · 0 = 0 · 1 = 0 · 0 = 0 (i. e.
1 is the neutral element and 0 is a zero element). In this monoid, both, 0 and
1, are their own (semigroup) inverses, respectively. However, 0 does not have
a group inverse! In this paper, inverse always refers to a semigroup inverse. A
1 This concept also appeared for example in [17] and a similar concept was studied by
Olijnyk, Sushchansky and Slupik (see [18] for this line of research).

3

semigroup S is called an inverse semigroup if every element s ∈ S has a unique
inverse s (see e. g. [13, 20] for more information on inverse semigroups).
Inverse semigroups are closely related to partial functions (or partial maps).
We write f : A →p B for a partial function from the set A to the set B. By
dom f , we denote the domain of f , i. e. the set of a ∈ A such that f (a) is defined.
The image of f , i. e. the subset f (dom f ) of B, is denoted by im f . If dom f = A,
then we say f is total and write f : A → B. A partial function f : B →p A is
inverse to another partial function f : A →p B if dom f = im f , im f = dom f
and f (f (f (a))) = f (a) for all a ∈ dom f as well as f (f (f (b))) = f (b) for all
b ∈ im f ; in slight abuse of terminology, we say that f is a group inverse of f
if dom f = im f , im f = dom f and f (f (a)) = a for all a ∈ dom f as well as
f (f (b)) = b for all b ∈ im f . Note that in the latter case both functions are
injective and the group inverse is unique.
Complexity and Decidability. In this paper, we use only basic and well-known
parts of computability and complexity theory; for an introduction on the subject
see any textbook (e g. [19]). We also assume the reader to be familiar with Big
O Notation.
We say a (non-deterministic) Turing Machine is bounded in space by a function s : N → N if, on input of a problem instance of length n, all computations
(whether accepting or not) use at most s(n) positions on any tape.
Let f : N → R be a function. Then NSpace(f ) is a set of decision problems:
a problem is in NSpace(f ) if it can be decided by a non-deterministic Turing
Machine which is bounded in space by a function s ∈ O(f ). Analogously, a
decision problem is in DSpace(f ) if it can be decided by a deterministic Turing
Machine which is bounded in space by a function s ∈ O(f ). PSpace is the
union of NSpace(p) for all polynomials p, which, by Savitch’s Theorem [22],
coincides with the union of DSpace(p) for all polynomials p. NL is the class
NSpace(log).
A problem P is (many-one) reducible to a problem R if there is a computable
(total) function f that maps an instance i of P to an instance f (i) of R in such
a way that i has a positive answer if and only if so has f (i). If f can be
computed by a deterministic Turing Machine that is bounded in space by a
function s ∈ O(log), then P is log-space reducible to R. It is well known that
log-space reducibility is transitive.
We say a decision problem P is hard (under many-one log-space reduction)
for a class C of decision problems if all problems R ∈ C are log-space reducible
to P . Most of the time, we will show hardness of a problem P for a class C
by showing that a known C-hard problem is log-space reducible to P (using the
transitivity of log-space reducibility).
Automata. A synchronous finite-state transducer (without initial or final states),
or simply automaton, is a tuple T = (Q, Σ, Γ, δ) where Q is a non-empty finite
set, Σ and Γ are alphabets and δ is a subset of Q × Σ × Γ × Q. The elements
of Q are called states, Σ is the input alphabet, Γ is the output alphabet and an
element (q, a, b, p) ∈ δ, which, from now on, we write as q a/b p, is a transition from q to p with input a and output b. The size |T | of an automaton T
4

is its number of states. Often, automata are represented graphically. In such a
graphical representation, we use
q

a/b

p

to indicate that the automaton has a transition q a/b p.
An automaton T = (Q, Σ, Γ, δ) is deterministic if
n
o
da (q) = q a/b p | q a/b p ∈ δ, b ∈ Γ, p ∈ Q ≤ 1
for all a ∈ Σ and q ∈ Q; it is complete if da (q) ≥ 1 for all a ∈ Σ and q ∈ Q.
A deterministic automaton T = (Q, Σ, Γ, δ) induces a partial right action of
Σ∗ on Q defined by q · a = p if q a/b p ∈ δ for some b ∈ Γ; the action is total
if T is complete. Additionally, it induces a partial map ◦ : Q × Σ∗ →p Γ∗ that
is defined inductively: let ◦(q, ε) = ε and ◦(q, a) = b if q a/b p ∈ δ for some
p ∈ Q; for u ∈ Σ+ , let ◦(q, ua) be the concatenation of ◦(q, u) and ◦(q · u, a) (if
defined). Again, the map is total if T is complete. For convenience, we write
q ◦ u instead of ◦(q, u) and consider q ◦ as the partial map q ◦ : Σ∗ →p Γ∗ with
q ◦ (u) = q ◦ u. Note that these partial maps are length-preserving (where they
are defined).
We also define “inverse” versions for these notions; here, we change the role
of input and output. For any automaton T = (Q, Σ, Γ, δ), we define its inverse automaton T = (Q, Γ, Σ, δ) where Q is a disjoint copy of Q and δ is
defined by swapping input and output: δ = {q b/a p | q a/b p ∈ δ}. We
say an automaton T is inverse-deterministic if T is deterministic and T is
inverse-complete if T is complete. Note that, for a deterministic and inversedeterministic automaton, q ◦ (where q is a state) and q ◦ (where q is a state of
the inverse automaton) are injective and mutually group inverse.
An automaton T = (Q, Σ, Γ, δ) is reversible if
n
o
d¯a (p) = q a/b p | q a/b p ∈ δ, b ∈ Γ, q ∈ Q ≤ 1
for all a ∈ Σ and p ∈ Q (i. e. if it is co-deterministic with respect to the input).
Graphically, T is reversible if
q

a/b

p

and

q′

a/c

p

implies q = q ′ for every a ∈ Σ and every p ∈ Q. It is bireversible if, additionally,
its inverse is reversible (i. e. if T is co-deterministic with respect to the output).
Graphically, this means that, additionally,
q

a/b

p

and

q′

implies q = q ′ for every b ∈ Γ and every p ∈ Q.
5

c/b

p

Note that reversibility does not imply determinism for non-complete automata. Neither does bireversibility imply inverse-determinism, as the example
in Figure 1 demonstrates.

a/b

c/b

Figure 1: A bireversible but not inverse-deterministic automaton.

For any two automata T1 = (Q1 , Σ1 , Γ1 , δ1 ) and T2 = (Q2 , Σ2 , Γ2 , δ2 ), one
may define their union automaton T1 ∪ T2 = (Q1 ∪ Q2 , Σ1 ∪ Σ2 , Γ1 ∪ Γ2 , δ1 ∪ δ2 ).
Acceptors. A spelling finite-state acceptor, or simply acceptor, is a tuple A =
(Z, Σ, δ, I, F ) where Z is a non-empty finite set, Σ is an alphabet, δ is a subset
of Z × Σ × Z, I ⊆ Z is a set of initial states and F ⊆ Q is a set of final states.
As with automata, the elements of Z are called states, Σ is the (input) alphabet
and an element (z, a, z ′ ) ∈ δ is an a-transition from z to z ′ , written as z a z ′ .
As a shorthand notation, we write z · a for the set {z ′ | z a z ′ ∈ δ} where
z ∈ Z and a ∈ Σ. The size |A| of an acceptor A is its number of states. We
also use the term Σ-acceptor for an acceptor with alphabet Σ. We represent
acceptors similar to automata: we simply omit the output (i. e. the /b part)
and mark final states with double circles (see Figure 4 for an example of a final
state).
An acceptor A = (Z, Σ, δ, I, F ) is deterministic if |I| = 1 and
da (z) = |{z

a

a

z′ | z

z ′ ∈ δ, z ′ ∈ Z}| ≤ 1

for all a ∈ Σ and z ∈ Z; it is complete if da (z) ≥ 1 for all a ∈ Σ and z ∈ Z.
The accepted language L(A) of an acceptor A = (Z, Σ, δ, I, F ) is the set
of words u = a1 a2 . . . an ∈ Σ∗ with a1 , a2 , . . . , an ∈ Σ for n ∈ N such that
ai
there is a sequence (z0 , z1 , . . . , zn ) of states with z0 ∈ I, zi−1
zi ∈ δ for all
i ∈ {1, 2, . . . , n} and zn ∈ F .
Automaton Semigroups and Groups. An S -automaton is a deterministic automaton whose input and output alphabet coincide. For brevity, we write
T = (Q, Σ, δ) instead of the more verbose T = (Q, Σ, Σ, δ) in the case of automata with coinciding input and output alphabet. Let T be an S -automaton
with stateset Q, then the semigroup generated by T , denoted by S (T ), is the
closure of {q ◦ | q ∈ Q} under finite composition of partial maps. A semigroup
is an automaton semigroup 2 if it is isomorphic to the semigroup generated by
some S -automaton.
2 Note that the notion of an automatic semigroup is not related to that of an automaton
semigroup although there is a quite recent attempt to link the two concepts, see [21].

6

An inverse-deterministic S -automaton T = (Q, Σ, δ) is called an S -automaton. As an S -automaton T = (Q, Σ, δ) generates an inverse semigroup
S (T ) = S (T ∪ T ); it is the closure of {q ◦ , q ◦ | q ∈ Q} under composition of
partial maps and, thus, indeed an inverse semigroup. We call a semigroup an
automaton-inverse semigroup if it is isomorphic to S (T ) for an S -automaton
T . Note the difference in definition between “automaton-inverse semigroups”
and “inverse automaton semigroups” (the latter being automaton semigroups
that are inverse semigroups).
If an S -automaton T is complete, it is also inverse-complete. In this case,
the maps q ◦ and q ◦ are total for all states q of T and the automaton T is
called a G -automaton. For a G -automaton T , S (T ) is a group; to emphasize
this fact, we use the notation G (T ) for this group. A group that is isomorphic
to G (T ) for a G -automaton T is an automaton group.
To denote an element of an automaton structure (i. e. an automaton semigroup, automaton-inverse semigroup or automaton group), we omit the ◦ and
simply write q = q1 q2 . . . qn to distinguish it from the partial function q ◦ =
q1 q2 . . . qn ◦ = q1 ◦ q2 ◦ · · · ◦ qn ◦ induced by its action on the set of (output)
words. This is in line with common algebraic notation. In structures where
the inverse is unique, we use the notation · to denote it; for example, we have
q1 q2 = q2 q1 . Note that this is compatible with the notation q for a state of the
inverse automaton.
Example 1. Let T be the following automaton.
1/0

+1

0/1

+0

0/0
1/1

Obviously, +0 ◦ is the identity on {0, 1} and, thus, +0 is a neutral element
in the semigroup generated by T . The map +1 ◦ can be seen as adding one
to the least significant bit first3 binary representation of a natural number. For
example, we have +1 ◦ 010 = 110 and +1 ◦ 110 = 001. So, S (T ) is the monoid
(N, +) and the group G (T ) is the additive group of integers (Z, +).
Example 2. The following complete automaton T = (Σ, Σ, δ) with Σ = {a, b}
b/a
a/a

a

b

b/b

a/b
generates the free semigroup Σ+ . This follows from the fact that q ◦ u is the
prefix4 of length |q| of qu for all q, u ∈ Σ∗ .5 Notice that, here, state sequences
and words come from the same set!
3 This

is the reverse of the normal binary notation.
word u is a prefix of a word w if there is a word v such that w = uv holds.
5 See also [6].

4A

7

If we remove the transition b a/b a, then the resulting automaton is not
complete anymore and b◦ is only defined on words from {b}+. As a consequence,
we have that ba ◦ is undefined on any input word (except for the empty word, of
course). This turns ba into a zero of the semigroup generated by the modified
automaton. Therefore, all non-zero elements are of the form an bm with n, m ∈
N. Since we have bb ◦ = b ◦, b is idempotent in this semigroup, which leaves us
with the elements ba, an and an b for n ∈ N that are pairwise distinct.
Usually, an automaton semigroup is defined as the semigroup generated by
a complete S -automaton. We will call such a semigroup a complete automaton
semigroup. Including semigroups generated by non-complete S -automata is
a natural extension of this notion (which allows for defining automaton-inverse
semigroups as we did above). It is clear that any complete automaton semigroup
is an automaton semigroup (as defined above). On the other hand, if S is an
automaton semigroup, then S 0 , i. e. the semigroup resulting from adjoining a
zero to S, is a complete automaton semigroup.
Proposition 1. If S is an automaton semigroup, then S 0 is a complete automaton semigroup.
Proof. To see this, let T = (Q, Σ, δ) be an S -automaton generating S. We
extend T into a complete automaton T̂ = (Q̂ ⊔ {0}, Σ ⊔ {⊥}, δ̂) where Q̂ is
a disjoint copy of Q, 0 is a new (sink) state and ⊥ is a new symbol. The
new automaton T̂ has all of T ’s transitions (i. e. we have q̂ a/b p̂ ∈ δ̂ if
q a/b p ∈ δ) and, additionally, new transitions q̂ a/⊥ 0 whenever there
is no transition with input a from state q in δ. We also add the transitions
0 a/⊥ 0 and q̂ ⊥/⊥ 0 to δ̂ for all a ∈ Σ ⊔ {⊥} and all q ∈ Q. One may
verify that T̂ is complete and that 0 is a zero of its generated semigroup, i. e.
we have 0q̂ = 0 = q̂0 = 00 for all q ∈ Q in the generated semigroup.
More importantly, we have q = p in S (T ) if and only if q̂ = p̂ in S (T̂ )
where q = qn qn−1 . . . q1 and p = pm pm−1 . . . p1 for arbitrary states q1 , q2 , . . . , qn ,
p1 , p2 , . . . , pm ∈ Q and where q̂ = q̂n q̂n−1 . . . q̂1 and p̂ = p̂m p̂m−1 . . . p̂1 are the
corresponding state sequences for T̂ . Note that, if q ◦ u is defined and equal to
v ∈ Σ∗ for a u ∈ Σ∗ , then, by construction, so is q̂ ◦ u. Now, suppose we have
q 6= p in S (T ). The first case is that there is a u ∈ Σ∗ on which the action of
one is defined (say q) while the other’s is not. As we have just discussed, we
have q ◦ u = q̂ ◦ u ∈ Σ∗ . Furthermore, we have p̂ ◦ u = v ′ ⊥k for some k > 0
and v ∈ Σ∗ because p ◦ u is undefined. This shows q̂ 6= p̂ in S (T̂ ). The second
case is that there is a u ∈ Σ∗ such that both, q ◦ u and p ◦ u, are defined but
we have p ◦ u = vp 6= vq = q ◦ u. However, this implies p̂ ◦ u = vp 6= vq = q̂ ◦ u
and we have p̂ 6= q̂ in S (T̂ ).
For the other direction, note that, if q̂ ◦ u = v ∈ Σ∗ for a u ∈ Σ∗ (i. e. there
is no ⊥ in v), then, by construction, q ◦ u is defined and equal to v. Suppose
we have q̂ 6= p̂ in S (T̂ ). Then, there is a word ua with u ∈ (Σ ⊔ {⊥})∗ and
a ∈ Σ ⊔ {⊥} such that q̂ ◦ u = p̂ ◦ u = v but q̂ ◦ ua = vb 6= vc = p̂ ◦ ua for
b, c ∈ Σ ⊔ {⊥}. Note that T̂ is in state 0 after reading ⊥ and that, therefore, u
cannot contain ⊥. Similarly, T̂ will be in state 0 after an output of ⊥. Thus,
8

v cannot contain ⊥ either and we have q ◦ u = p ◦ u = v. If b, c ∈ Σ, then, by
the same argumentation, we have q ◦ u = vb 6= vc = p ◦ u. If (without loss of
generality) b = ⊥ and c ∈ Σ, then q ◦ ua is undefined while p ◦ ua = vc is not.
In either case, we have q 6= p in S (T ).
This shows that ι : S 0 → S (T̂ ) given by ι(0) = 0 and ι(q) = q̂ for every
q ∈ Q is a well-defined isomorphism and that, thus, S 0 is a complete automaton
semigroup.
We want to point out that the obvious question whether there is an automaton semigroup that is not a complete automaton semigroup is closely related to
a question asked by Cain in [6, Open problem 5.3]: is there a semigroup S such
that S is not a complete automaton semigroup but S 0 is?
3. Complexity of the Word Problem
Before we start discussing the word problem’s complexity, we introduce consistent terminology to distinguish some of its variants more clearly. The variables appearing in the definitions of the problems are used in the same meaning
in the statements and proofs of the propositions below.
Word Problems. The uniform word problem for automaton semigroups with rational constraints is the decision problem:
Input:
an S -automaton T = (Q, Σ, δ),
q1 , q2 , . . . , qn , p1 , p2 , . . . , pm ∈ Q,
Σ-acceptors A1 , A2 . . . , Ar of size at most R
Tr
Question: is qn qn−1 . . . q1 ◦ u = pm pm−1 . . . p1 ◦ u for all u ∈ k=1 L(Ak )?
The uniform word problem for automaton-inverse semigroups with rational constraints is the decision problem:
Input:
an S -automaton T = (Q, Σ, δ),
q1 , q2 , . . . , qn , p1 , p2 , . . . , pm ∈ Q ∪ Q (Q are the states of T ),
Σ-acceptors A1 , A2 . . . , Ar of size at most R
Tr
Question: is qn qn−1 . . . q1 ◦ u = pm pm−1 . . . p1 ◦ u for all u ∈ k=1 L(Ak )?
A variation of this problem is the uniform word problem for automaton groups
with rational constraints where the input S -automaton is known to be a G automaton.
Additionally, all problems also have versions without rational constraints
(then simply called the uniform word problem for . . . ). Here, the acceptors are
omitted from the input and the question is: is qn qn−1 . . . q1 ◦u = pm pm−1 . . . p1 ◦u
for all u ∈ Σ∗ ?
Besides the uniform versions, we also consider the word problems for specific automaton structures. The word problem with rational constraints for an
automaton semigroup is the decision problem:
Constant: an S -automaton T = (Q, Σ, δ)
Input:
q1 , q2 , . . . , qn , p1 , p2 , . . . , pm ∈ Q,
Σ-acceptors A1 , A2 . . . , Ar of size at most R
Tr
Question: is qn qn−1 . . . q1 ◦ u = pm pm−1 . . . p1 ◦ u for all u ∈ k=1 L(Ak )?
9

The word problem with rational constraints for an automaton-inverse semigroup
is the decision problem:
Constant: an S -automaton T = (Q, Σ, δ) and its inverse T = (Q, Σ, δ)
Input:
q1 , q2 , . . . , qn , p1 , p2 , . . . , pm ∈ Q ∪ Q,
Σ-acceptors A1 , A2 . . . , Ar of size at most R
T
Question: is qn qn−1 . . . q1 ◦ u = pm pm−1 . . . p1 ◦ u for all u ∈ rk=1 L(Ak )?
For the word problem with rational constraints for an automaton group, we additionally have that T is a G -automaton. Again, we also have versions without
rational constraints, simply called the word problem for an automaton semigroup/inverse semigroup/group, where the acceptors are omitted from the input
and the question is changed in the same way as for the uniform versions.
3.1. Upper Bounds
An upper bound for a problem’s complexity is usually given in the form of
an algorithm and this is what we do in this subsection. Steinberg [24] noted
that the word problems (without rational constraints) for automaton groups are
decidable in NSpace(n). The algorithm he presented is quite straightforward
and similar to the one we present here. However, we adapt it for automaton
semigroups and automaton-inverse semigroups and extend it to cover rational
constraints.
Proposition 2. The following problems can be decided by a non-deterministic
Turing Machine in space O((n + m) log |T | + r log R) and are, thus, in nondeterministic linear space:
• the uniform word problem for automaton semigroups with rational constraints,
• the uniform word problem for automaton-inverse semigroups with rational
constraints and
• the uniform word problem for automaton groups with rational constraints.
Furthermore, the versions without rational constraints can be decided in nondeterministic space O((n + m) log |T |) and are, thus, also in non-deterministic
linear space.
Proof. We give an algorithm to decide the uniform word problem for automaton
semigroups with rational constraints (as stated above) since this is the most
general case. In fact, we give an algorithm for the problem’s complement. As
non-deterministic space classes are closed under complementation [14, 25], this
proves the proposition.
For the input Σ-acceptors A1 , A2 , . . . , Ar , let Ak = (Zk , Σ, δk , Ik , Fk ). The
algorithm uses the following variables.
• For each input Σ-acceptor Ak , we need a variable zk that stores a state
from Zk . The initial value of these variables may be undefined.
Storing a single state requires space O(log R); storing all of them, thus,
requires space O(r log R).
10

• We also need n+m variables to store states of the input automaton T . We
re-use the names q1 , q2 , . . . , qn , p1 , p2 , . . . , pm for this, their initial values
shall be the respective input values.
Storing a single of these states requires O(log |T |); storing all of them,
thus, requires space O((n + m) log |T |).
• Finally, we need four variables a, a′ , b and b′ to store letters from Σ. Their
space requirement is constant6 .
The general idea of the algorithm is now as follows. We guess a word u ∈
Σ∗ letter by letter (we only store the last guessed letter of the word). The
guessed word should be a witness to prove the inequality of qn qn−1 . . . q1 ◦ and
pm pm−1 . . . p1 ◦ (i. e.T we want to have qn qn−1 . . . q1 ◦ u 6= pm pm−1 . . . p1 ◦ u)
r
and it should be in i=1 L(Ai ). To test the latter, we store, for all acceptors,
one of the states in which the acceptor can be after reading the current prefix
of u; then, we can test whether that state is final, in which case the prefix is
in the acceptor’s language. To test the former, we store the n + m states of
the automaton T in which we are after reading the current prefix of u. After
guessing the next letter a ∈ Σ, we compute successively ai = qi ◦ai−1 and qi ·ai−1
as the new value of qi where a0 = a (without storing the intermediate results).
We do the same for p1 , p2 , . . . , pm and obtain the letter bm in the end. Then,
we compare an and bm . If they are unequal (and the acceptors accept), then we
have found the witness and can return “6=”. The algorithm’s pseudo-code may
be found in Algorithm 1. Its correctness is easy to see: if we have inequality,
then the algorithm guesses a witness, and, if it guesses a witness, then we have
inequality.
Handling automaton-inverse semigroups and groups only requires storing an
additional bit for each state in the automaton that indicates whether we are
in a state q or in a state q; the rest of the algorithm is structurally equal.
The algorithms for the problems without rational constraints do not require the
additional book-keeping for the acceptors and are, thus, even simpler (one can
simply remove the corresponding commands from the algorithm).
There is an interesting observation concerning the last proposition and its
proof: to show that the uniform word problem for automaton groups is in nondeterministic linear space, we nowhere exploit group properties. In fact, we only
give an algorithm for automaton semigroups that can also be applied to groups.
Interestingly, we will see later (in Proposition 5) that the uniform word problem
for automaton semigroups (and automaton-inverse semigroups) is PSpace-hard.
Therefore, the presented simple algorithm – in the sense of complexity – is as
efficient as possible. However, it is also possible that there is a more efficient
algorithm for the uniform word problem for automaton groups without rational
constraints (making use of their group structure).
6 or in O(log |Σ|), depending on one’s point of view. Either way, the algorithm is in nondeterministic linear space in the end.

11

Algorithm 1 Deciding the uniform word problem for automaton semigroups
with rational constraints in NSpace(n)
for all i ∈ {1, 2, . . . , r} do
zi ← guess(Ii ) ⊲ Non-deterministically choose an initial state for each
acceptor.
end for
while true do
a ← guess(Σ)
⊲ Guess the witness’s next letter a0 ∈ Σ.
b←a
for all k ∈ {1, 2, . . . , r} do
zk ← guess(zk · a)
⊲ Guess an accepting run in each acceptor.
end for
for all i ∈ {1, 2, . . . , n} do
a′ ← qi ◦ a
qi ← qi · a
a ← a′
end for
⊲ Here, we have a = qn qn−1 . . . q1 ◦ a0 .
for all j ∈ {1, 2, . . . , m} do
b ′ ← pj ◦ b
pj ← pj · b
b ← b′
end for
⊲ Here, we have b = pm pm−1 . . . p1 ◦ a0 .
if a 6= b and ∀k ∈ {1, 2, . . . , r} : zk ∈ Fk then
return “6=”
⊲ We have found a witness.
end if
end while
The algorithm from the previous proposition’s proof can be adapted to decide
the word problem for a fixed automaton structure. Here, the automaton T is
not considered part of the input. Therefore, we can store a single state of the
automaton in constant space and, as a simple consequence, get the following
proposition.
Proposition 3. These problems can be decided by a non-deterministic Turing
Machine in space O(n + m + r log R) and are, thus, in non-deterministic linear
space:
• the word problem with rational constraints for any automaton semigroup,
• the word problem with rational constraints for any automaton-inverse semigroup and
• the word problem with rational constraints for any automaton group.
Furthermore, the versions without rational constraints can be decided in nondeterministic space O(n + m) and are, thus, also in non-deterministic linear
space.

12

3.2. Lower Bounds
In the last section, we gave a non-deterministic algorithm to decide many
variations of the word problem for automaton structures. As the algorithms
only require linear space, they admit deterministic exponential time algorithms
(see e. g. [19]). While it is a less precise approach from a complexity viewpoint,
such deterministic algorithms are often stated directly by using the fact that
one can give an upper bound for the length of a word on which two distinct
elements of an automaton structure act differently. This path was also taken by
Cain in [6], where he asks whether there is a better upper bound on the word
length than |Q|n+m in the case of automaton semigroups (the notation used
here is the same as in the definitions of the word problems above). In the next
proposition, we handle this question by giving lower bounds on the length.
Proposition 4. Let D = (Q, {a, b}, δ) be the S -automaton7
a/b
b/b

0

1

b/b

a/a
and let n > 0. Then, the elements 0n and 0n−1 of S (D) are distinct but 0n ◦u =
|0n |+|0n−1 |
2

0n−1 ◦ u holds for all u ∈ {a, b}∗ of length smaller than 2n−1 = |Q|
.
Let D′ = (Q′ , {a, b}, δ ′ ) be the S -automaton obtained from D by adding the
state
a/b .
b/b

q

Then, 0n−1 and q are distinct elements of S (D′ ) but 0n−1 ◦ u = q ◦ u holds for
n−1
all u ∈ {a, b}∗ of length smaller than 2n−1 = (|Q′ | − 1)|0 |+|q|−1 .
←−
Proof. For a natural number i ∈ N, let bink (i) denote i’s binary representation
of length k in reverse (i. e. with least significant bit first). One may verify that,
for 0 ≤ i < 2k − 1, we have
←−
bink (i) ◦ a = b,
←−
bink (i) ◦ b = b and

←−
←−
bink (i) · a = bink (i + 1),
←−
←−
bink (i) · b = bink (i).

In other words: an input of a is adding one to the binary representation and
outputs b while an input of b does not change anything and outputs b again.
This shows 0n ◦ u = b|u| = 0n−1 ◦ u = q ◦ u for all u ∈ {a, b}∗ of length up to
7 We want to remark that the presented S -automaton is the so-called dual of the adding
machine depicted in Example 1. For the construction of the dual, states and letters change
roles, just like the operations ◦ and ·.

13

←−
n−1
2n−1 − 1. Additionally, we have 0n−1 · a2 −1 = binn−1 (2n−1 − 1) = 1n−1 and
←
−
n−1
n−1
n−1
0n · a2 −1 = binn (2n−1 − 1) = 01n−1 , which shows 0n−1 ◦ a2
= a2 −1 b 6=
n−1
n−1
n−1
a2
= 0n ◦ b2
= q ◦ a2 .
In some sense, the previous proposition gives a lower bound for the running
time of the often stated algorithm for the word problem that enumerates all
words up to a certain length and tests whether the input elements act differently
on them. In the next proposition, we show a general, algorithm-agnostic lower
bound by showing PSpace-hardness for some versions of the uniform problem.
Please note that these results also follow from Proposition 6 below. However,
the encoding technique used in the next proof is much simpler and more direct.
Therefore, it is interesting in its own right and we feel that it deserves to be
mentioned explicitly.
Proposition 5. These problems are PSpace-hard:
• the uniform word problem for automaton semigroups (with or without rational constraints),
• the uniform word problem for automaton-inverse semigroups (with or without rational constraints),
• the uniform word problem for automaton groups with a single rational
constraints.
Proof. From a classical result of Kozen [15] follows PSpace-hardness of the
following problem.
Constant: Σ = {0, 1}
Input:
r ∈ N, complete and deterministic Σ-acceptors A1 , A2 , . . . , Ar
of T
size at most R
Question: is rk=1 L(Ak ) empty?
We describe how to map an instance A1 , A2 , . . . , Ar of the previous problem to an instance of the uniform word problem for automaton-inverse semigroups (without rational constraints). Let Ak = (Zk , Σ, δk , {z0,k }, Fk ) for k =
1, 2, . . . , r. Without loss of generality, we assume all Zk to be disjoint. For each
k ∈ {1, 2, . . . , r}, let Tk′ be the automaton over the alphabet Γ = {0, 1, #} given
by the graphical representation in Figure 2 (without the dashed transitions).
Note that Tk′ is an S -automaton. The idea of the construction is to ensure that
an input word is (a prefix of a word) of the form {0, 1}k−1 1{0, 1}r−k #1, that
is a block of length r consisting of 0s and 1s, where the k th letter is 1, followed
by #1. This k th letter is switched from 1 to 0 while all other letters are left
unchanged.
Besides Tk′ , we also define Tk′′ , a disjoint copy of Tk′ where the transition
(k − 1) 1/0 k is changed to (k − 1) 1/1 k , meaning that the 1 at position
k is checked but not changed. Furthermore, we define Tk to be the automaton
obtained from the acceptor Ak by changing all transitions z a z ′ into transitions z a/a z ′ , that is we add to each transition an output which is equal to
the input. Note that the resulting automata are S -automata; in fact, they are
G -automata.
14

Figure 2: a schematic representation of Tk′ and the transitions to make it complete
#/#
0

0/0
1/1

#/#
1

0/0
1/1

0/1
#/#

#/#
2

...
0/0
1/1

k−1

1/0

#/#

#/#
k

k+1

0/0
1/1

0/0
1/1

#/#
k+2

...
0/0
1/1

0/0
1/1
#/#

r
0/0
1/1

#/#
1/1
0/0
#/#

Finally, we define T ′ to be given by the graphical representation in Figure 3
(without the dashed transitions). Clearly, it is an S -automaton. Most interesting are the states c (“check”) and d (“disable”). On a word of the form
{0, 1}∗#{0, 1}r #1, c checks whether any of the letters in the {0, 1}r block is 0.
In that case, it switches the trailing 1 into a 0; otherwise, it does not change
the word at all. The behavior of d is similar. However, it always changes the
trailing 1 into a 0.
Combining these automata, we define T as the disjoint union of T ′ ,T1 , T2 , . . . ,
Tk , T1′ , T2′ , . . . , Tk′ and T1′′ , T2′′ , . . . , Tk′′ where we add, for each k ∈ {1, 2, . . . , r},
transitions with input # and output # from the non-final states z ∈ Zk \ Fk to
the 0-labeled state of Tk′ (in T ) and from the final states z ∈ Fk to the 0-labeled
state of Tk′′ . We give a schematic representation of T in Figure 4.
We are going to use T as the automaton in the instance of the uniform
word problem for automaton-inverse semigroups. Therefore, one should verify

Figure 3: a graphical representation of T ′ and the transitions to make it complete

#/#
c

#/#

0

1/1

0/0

#/#
1

0/0
1/1

0/0
1/1
#/#
#/#

0′′

1/1
0/0

1/1

r

0/0

0/0
1/1

#/#
2′

#/#
1′′

...

2

#/#
1′

d

1/1

0/0

#/#

1/1
0/0

...
0/0
1/1

r′

#/#
2′′

...
1/1
0/0

15

r′′

0/0
1/1

0/0
#/#

#/#

1/1

0/0
1/1

0/1
#/#

#/#

1/0

0/0
1/1

0/1
#/#

#/#

1/0

0/0
1/1
#/#

0/0
1/1
#/#

0/0
1/1
#/#

Figure 4: Schematic representation of T

Tk (from Ak )

0

Tk′′

#/#

0

Tk′

#/#
T′

that T is an S -automaton and can be computed from A1 , A2 , . . . , Ar in logarithmic space. Besides T , we also need two finite sequences of its states to
form a proper problem instance. As the sequence on the left hand size, we use
cz0,r z0,r−1 . . . z0,1 and, on the right hand size, we use dz0,r z0,r−1 . . . z0,1 .
It remains to show that we haveTcz0,r z0,r−1 . . . z0,1 ◦u = dz0,r z0,r−1 . . . z0,1 ◦u
r
for all u ∈ {0, 1, #}∗ if and only if k=1 L(Ak ) = ∅. For this, we first investigate
the behavior on a word u that is not a prefix of a word from {0, 1}∗#1r #1. By
construction, we have that z0,r z0,r−1 . . . z0,1 ◦ u is undefined because either u
is not even a prefix of a word from {0, 1}∗#{0, 1}r #1 – in which case z0,1 ◦ u
is already undefined – or it has a prefix in {0, 1}∗#1s 0 for an s ∈ N. Let this
prefix be w#1s 0. Then, we have z0,s z0,s−1 . . . z0,1 ◦ u = u′ ∈ w#{0, 1}s 0. But
on such a word,
Tr z0,s+1 ◦ is undefined.
Next, let k=1 L(Ak ) = ∅. By the previous discussion and due to the behavior of automata, we only have to show cz0,r z0,r−1 . . . z0,1 ◦u = dz0,r z0,r−1 . . . z0,1 ◦
u for all words from {0, 1}∗#1r #1. Let u = w#1r #1 be such a word. Let k0
be the smallest number such that w 6∈ L(Ak0 ). By construction of T , we have
zk ◦ u = u for 1 ≤ k < k0 : no automaton Tk changes the w part of u and,
by the choice of k0 , we continue at the 0-labeled state of Tk′′ after reading the
first # in u; this does not change the 1r #1 part of u either. Thus, we have
z0,k0 −1 z0,k0 −2 . . . z0,1 ◦ u = u. Now, applying z0,k0 ◦ u, again, leaves the w part
unchanged (due to the construction of Tk0 ) but switches the k th 1 in the #1r #1
part to 0 (because, after reading w#, we enter Tk′ in T ). In the end, we have
z0,r z0,r−1 . . . z0,1 ◦ u = u′ ∈ w#1k0 −1 0{0, 1}r−k0 #1. Now, both, c ◦ and d ◦ ,
′
′
′
only switch the trailing
Tr 1 in u into a zero. Thus,r we have c ◦ u = d ◦ u .
Finally, let w ∈ k=1 L(Ak ). Define u = w#1 #1. For each k ∈ {1, 2, . . . , r},
we have z0,k ◦ u = u because we are in a final state after reading w in Ak and,
thus, continue in Tk′′ which does not change u. Therefore, we have z0,r z0,r−1 . . .
z0,1 ◦ u = u. Because there is no 0 in the 1r block of u, c ◦ will not change
the trailing 1 into a 0 but d ◦ will, which shows cz0,r z0,r−1 . . . z0,1 ◦ u 6=
dz0,r z0,r−1 . . . z0,1 ◦ u and concludes the proof.
We have shown the first two items of the proposition’s assertion. For the

16

uniform word problem for automaton groups, we have to turn T into a complete
automaton while keeping it deterministic and reverse deterministic. It is already
complete in its Tk parts. In the T ′ and Tk′ parts, we include the dashed transitions from Figure 3 and Figure 2. We may do the same for Tk′′ ; here, however,
we have to change the (dashed) transition (k − 1) 0/1 k to (k − 1) 0/0 k.
One should verify that this new version of T is a G -automaton. We only want to
show PSpace-hardness of the uniform word problem for automaton groups with
a single rational constraints. The rational constraint we are going to use is that
we only consider words from {0, 1}∗#1r #1. We may construct an according
acceptor similar to the d branch in Figure 3 in logarithmic space. This allows
us to use the same proof as for the case of automaton-inverse semigroups above
because the constraint ensures that we never use any of the dashed transitions
(the new version of T behaves like the old version on all relevant words).
The last proof shows PSpace-hardness of the stated uniform word problems
even if one restricts the automata to the fixed ternary alphabet {0, 1, #}. We
want to remark that the result also holds for the stricter restriction to the binary
alphabet {a, b}. This can be shown by encoding 0 as aa, 1 as ab and # as bb and
adapting the previous automata accordingly. It is important to note that, using
this encoding, we preserve inverse-determinism; in particular, it is still possible
to toggle 0/aa and 1/ab without reading and outputting two letters in one go.
Next, we show a generalization of the previous proposition: we make the
transition from the uniform to the non-uniform problems. This generalization,
however, comes at the cost of increased complexity in the encoding techniques
and the proof as a whole.
Proposition 6. The following holds:
• There is an automaton semigroup for which the word problem is PSpacehard.
• There is an automaton-inverse semigroup for which the word problem is
PSpace-hard.
• There is an automaton group for which the word problem with a single
rational constraint is PSpace-hard (where the rational constraint is part
of the input).
Proof. The first assertion is an implication of the second one. Therefore, we
start with the inverse semigroup case and show the group case later.
The Automaton-Inverse Semigroup Case. There exists a (deterministic) onetape, PSpace-universal Turing Machine M0 , i. e. a Turing Machine that halts
on input of a word w and the encoding of another PSpace machine M if and
only if M halts on w; furthermore, the space used by M0 on input of length
n is bounded by a polynomial p(n). Let Γ be the tape alphabet of M0 , Z its
state set, z0 its initial state and its blank symbol. Without loss of generality,
we may assume that M0 never visits a tape position to the left of its initial
17

position, which we call position 0. Of course, M0 neither visits a position to
the right of position p(n) − 1 (on input of length n). Equally without loss of
generality, we may assume that the computation of M0 never stops (even in the
case of acceptance). The machine accepts an input word if the corresponding
(infinite) computation passes a final state; let E be the set of these final states.
Suppose, at time step t, M0 ’s tape contains the symbols γ0 γ1 . . . γp(n)−1 ,
its head is at position i and it is in state z, then, we write its configuration as
γ0 γ1 . . . γi−1 (γi , z)γi+1 γi+2 . . . γp(n)−1 , which we consider to be a word of length
p(n) over the alphabet ∆ = Γ ∪ (Γ × Z). For example, on input a0 a1 . . . an−1
(where a0 , a1 , . . . , an−1 are single letters), the initial configuration, i. e. that at
time 0, of M0 is written as (a0 , z0 )a1 a2 . . . an−1 . . . .
Note that the letter at position i in the configuration for time step t is
uniquely determined by the letters at positions i − 1, i and i + 1 of the configuration at time step t − 1. Here, the symbols at position −1 (the one left to
the initial position) and at position p(n) are implicitly considered to be blanks.
This yields the transition map τ : ∆3 → ∆, which only depends on M0 . The
general idea of this proof is to create an automaton with a “checker” state which
encodes the finite map τ to check a sequence of configurations u = c1 #c2 # . . .
separated by the new symbol # 6∈ ∆ for valid transitions in each position. Let
(t)
(t)
(t) (t)
ct = γ0 γ1 . . . γp(n)−1 with γi ∈ ∆ for all 0 ≤ i < p(n) and t > 0. The
first application of the checker state to u will check all zeroth positions, i. e.
(1)
(2)
γ0 , γ0 , . . . . If the transition is valid, it will put a check-mark on the corresponding letter in u. When applying the checker state for the second time, it
will ignore all zeroth positions since they already have a check-mark and check
all first positions; see Figure 5. If we repeat this p(n) times, we know whether
the sequence of configurations is a valid computation of M0 . This approach
has a drawback, however: putting a check-mark on the next letter that, so-far,
does not have one is an operation which results in a non-inverse-deterministic
automaton. So, we cannot use this approach for automaton-inverse semigroups
and automaton groups directly.
Figure 5: Illustration of the check-mark approach.
(1)

γ1

(1)

γ1

γ0
checker

γ0

X

checker

(1)

γ0

X

(1)

γ2

(1)

γ2

(1)

γ1

X

γ1

(2)

γ1

. . . γp(n)−1 # γ0

(1)

. . . γp(n)−1 # γ0

(1)

γ2

(1)

(2)

(1)

(1)

X
(2)

(1)

. . . γp(n)−1 # γ0

X

(2)

γ2

(2)

γ2

(2)

γ2

γ1

X

(2)

. . . γp(n)−1 # . . .

(2)

(2)

. . . γp(n)−1 # . . .

(2)

. . . γp(n)−1 # . . .

(2)

(2)

Check-Marking using S -Automata. To overcome this, we are going to use a
modified version of the additive automaton from Example 1 and add a digit
block after each configuration symbol. The construction will ensure that the
block is always sufficiently long; this means a length of about log2 p(n) but the
18

exact length does not matter. For this block, we need two new symbols 0, 1 6∈ ∆.
Instead of putting a check-mark on a symbol, we are going to do a +1 on its
digit block. A symbol is considered to have a check-mark if and only if its block
contains a 1. For technical reasons, we will later also need to add a $00 . . . 0$0
suffix to our configuration sequences,8 where $ is another new symbol, so we
end up with the alphabet Σ = ∆ ⊔ {0, 1, #, $}. The length of the block at the
front of the suffix is again “long enough”. Summing this up, our automaton is
designed to operate on words of the form
(1)

(1)

γ0 00 . . . 0

γ1 00 . . . 0

ë

(2)
γ0 00 . . . 0

(2)
γ1 00 . . . 0

ë

(T )
γ0 00 . . . 0

(T )
γ1 00 . . . 0

(1)

...

γp(n)−1

#

...

(2)
γp(n)−1

#

(T )
γp(n)−1

...

...

#

$00 . . . 0$0

(t)

where T is some number and γi ∈ ∆ for all 1 ≤ t ≤ T and all 0 ≤ i < p(n).
The automaton in Figure 6 – more precisely, its X state – puts a checkmark in the sense described above on the first symbol without one in each
configuration in the sequence. A transition label idX means that, for every
x ∈ X, there is such an x/x-labeled transition. Note that the automaton is
deterministic and inverse-deterministic but not complete.
id{0,1,$}
$/$
id∆∪{0,1}

“Skip everything up to the next
configuration”

$/$
0/0

id∆

#/#

#/#

“So far, the original input digit
block of this symbol did not contain a 1.”

1/1
0/1

X

id∆

0/0
1/1

id∆
1/0

0/1
“The last symbol’s digit block
contained at least one 1.”
1/0

Figure 6: The automaton used for generalized check-marking

8 Strictly

speaking, this is only necessary for the group case.

19

Checking the Validity. For the checking part of the automaton, we use the
′
following states for each γ−1 , γ0 , γ1 , γ−1
, γ0′ ∈ ∆.

0

γ−1 ,
′
,
γ−1

γ0 ,
γ0′

γ1

1

γ−1 ,
′
,
γ−1

γ0 ,
γ0′

γ1

γ−1 ,

γ0 ,

γ1

The idea behind these states is the following. We have check-marked (in the
more general sense mentioned above) the positions 0, 1, . . . , i − 1 for all time
steps in our configuration sequence, i. e. we now want to check the respective ith
position for all time steps. Suppose further that we already have successfully
done this checking of position i for the time steps up to and including t − 1.
When we did the checking for time step t − 1, we stored the symbols at position
i − 1, i and i + 1 in the state. For storing this information, we use the upper row,
i. e. the entires γ−1 , γ0 , γ1 . Now, we start reading the configuration (with the
digit-blocks for each symbol) for time step t. During the reading, we remember
the last two seen symbols of the configuration in the lower row. Whenever a
new symbol begins, we have not seen its digit-block yet and, therefore, cannot
know whether it is the first positions which has not been check-marked yet (i. e.
position i). To handle this, we use the distinction between the circled 0 and
circled 1 states. We are in the circled 0 state just after we have read γ0′
and before we begin to read the corresponding digit-block. As long as we only
see 0 in this block, we stay in the 0 state. If we see a 1, we know that the
symbol has already been check-marked and we move to the 1 state where we
′
skip everything up to the next symbol (updating γ−1
and γ0′ accordingly). If
we see the next symbol before we see a 1, we know that γ0′ is indeed the symbol
at position i of the time step t and we can check the validity of the transition
from step t − 1 to step t at position i using τ . If the transition is valid, we want
to skip the rest of the configuration at time step t and begin again for time
step t + 1. However, while we do the skipping, we have to store the symbols at
positions i − 1, i and i + 1 correctly for the next time step. This is what the last
type of states (the ones with only a blank symbol in the lower row) is used for.
We can also check the validity if we see one of the end markers # and $ instead
of the next symbol before we see a 1. In the case of #, we store the implicit
as the symbol at position i + 1 and continue normally. In the case of $, we skip
to the end of the word.
These ideas are implemented by the transitions which are schematically de′
picted in Figure 7. We have these transitions for every γ−1 , γ0 , γ1 , γ−1
, γ0′ ∈ ∆.
′
The dashed transitions exist only if τ (γ−1 , γ0 , γ1 ) = γ0 ; if this is the case, then
the transition labeled γ1′ /γ1′ exists for every γ1′ ∈ ∆. The dotted γ/γ transition
exists for every γ ∈ ∆ and the dotted states are equivalent to the non-dotted
′
states for the corresponding other values of γ−1 , γ0 , γ1 , γ−1
, γ0′ ∈ ∆ (their outgoing edges are not drawn). Note that the functions given by the states always
behave like the identity on values where they are defined and that the automaton
is an S -automaton.

20

1

′
γ−1
,
,

γ0′ ,

0/0

0

γ−1 ,
′
γ−1
,

$/$
γ0 ,
γ0′

γ−1 ,
′
γ−1
,

γ0 ,
γ0′

γ1

idΓ∪Γ×Z∪{0,1}

$/$
γ1′ /γ1′

1/1
1

′
γ−1
,

γ1

γ/γ

0

γ−1 ,
γ0′ ,

γ0 ,
γ

0/0
1/1

$/$

#/#
0/0
1/1

0/0
1/1

γ0′ ,

γ1′

#/#
γ1

′ ,γ ′ ,γ ′ =
qγ−1
0 1

′
γ−1
,
,

1

γ0′ ,

γ1′

Figure 7: Schematic representation of the transitions used for the checking part of the automaton and the definition of qγ−1 ,γ0 ,γ1

Behavior on Words Encoding Configuration Sequences. We will have a closer
look on how the automaton behaves on a sequence of configurations next. Sup(0) (0)
(0)
pose M0 starts its computation in the initial configuration γ0 γ1 . . . γp(n)−1 =
(a0 , z0 )a1 a2 . . . an−1 . . . on input a0 a1 . . . an−1 (where a0 , a1 , . . . an−1 are let(t)
(t) (t)
(t)
ters). Furthermore, let ct = γ0 γ1 . . . γp(n)−1 with γi ∈ ∆ for all 0 ≤ i < p(n)
be the configuration at time t > 0 of this computation. Note that this configuration is well-defined for all t ≥ 0 (by assumption on M0 ’s structure).
(t)
(t)
At the border, we define γ−1 = γp(n) =
for all t ≥ 0. Finally, we de(t)

(t)

(t)

fine c′t = γ0 0k γ1 0k . . . γp(n)−1 0k as the result of adding the digit-blocks to
ct . Here, we set k = ⌈log2 p(n)⌉, i. e. the digit-blocks allow us to count up
to p(n). Now, we consider the behavior of the automaton on the input word
u = c′1 #c′2 # . . . #c′T $0k $0 (for an arbitrary T > 0). Note that the word starts
with the (modified) configuration for t = 1, not with the initial configuration
(t = 0). Instead, the initial configuration is encoded in the element
qc0 = Xqγ (0)

p(n)−2

(0)

(0)

,γp(n)−1 ,γp(n)

. . . Xqγ (0) ,γ (0) ,γ (0) Xqγ (0) ,γ (0) ,γ (0)
0

1

2

−1

0

1

(for the definition of qγ−1 ,γ0 ,γ1 please refer to Figure 7). What happens if we
apply qc0 ◦ to u? One may verify, that qγ (0) ,γ (0) ,γ (0) ◦ u is defined and, thus,
1
−1 0
equal to u because the configurations describe a valid computation. Applying
21

X ◦ to u next results in the word
−
−
←−
−
(1)
(1) ←
(1) ←
(1) ←
u1 = γ0 bink (1) γ1 bink (0) γ2 bink (0) . . . γp(n)−1 bink (0)#
−
−
←−
−
(2)
(2) ←
(2) ←
(2) ←
ë
γ0 bink (1) γ1 bink (0) γ2 bink (0) . . . γp(n)−1 bink (0)# . . . #
−
−
−
←−
(T ) ←
(T ) ←
(T ) ←
(T )
ë
γ0 bink (1) γ1 bink (0) γ2 bink (0) . . . γp(n)−1 bink (0)$0k $0,
←−
where bink (i) is the reverse binary representation of i ∈ N with length k. Ap(t)
plying qγ (0) ,γ (0) ,γ (0) ◦ to u1 will check all γ1 for validity. Again, the result will
0
1
2
be u1 . After the next X ◦ , we have

ë
ë

−
−
−
←−
(1) ←
(1) ←
(1) ←
(1)
u2 = γ0 bink (2) γ1 bink (1) γ2 bink (0) . . . γp(n)−1 bink (0)#
←−
−
−
−
(2)
(2) ←
(2) ←
(2) ←
γ0 bink (2) γ1 bink (1) γ2 bink (0) . . . γp(n)−1 bink (0)# . . . #
−
←−
−
−
(T )
(T ) ←
(T ) ←
(T ) ←
γ0 bink (2) γ1 bink (1) γ2 bink (0) . . . γp(n)−1 bink (0)$0k $0.

This continues and, in the end, we have

ë
ë

−
−
←−
(1) ←
(1) ←
(1)
up(n) = γ0 bink (p(n)) γ1 bink (p(n) − 1) . . . γp(n)−1 bink (1)#
−
−
←−
(2) ←
(2) ←
(2)
γ0 bink (p(n)) γ1 bink (p(n) − 1) . . . γp(n)−1 bink (1)# . . . #
−
−
←−
(T ) ←
(T ) ←
(T )
γ0 bink (p(n)) γ1 bink (p(n) − 1) . . . γp(n)−1 bink (1)$0k $0.

For comparison, we will now look at what happens if we start with a sequence of (valid) configurations which, however, is not a valid computation
of M0 : assume, there is a (smallest) position 0 ≤ i < p(n) such that there
exits (a minimal) t > 0 for which the transition is not valid, i. e. we have
(t)
(t−1)
(t−1)
(t−1)
, γi+1 ) 6= γi . If we apply
τ (γi−1 , γi
Xqγ (0) ,γ (0) ,γ (0) . . . Xqγ (0) ,γ (0) ,γ (0) Xqγ (0) ,γ (0) ,γ (0) ◦ ,
i−2

i−1

i

0

1

2

−1

0

1

the behavior will be the same as for the case where the sequence belonged
to a valid computation. Let ui be the resulting word. When we then apply
qγ (0) ,γ (0) ,γ (0) ◦ to ui , we see a difference: qγ (0) ,γ (0) ,γ (0) ◦ ui is undefined because
i−1 i
i+1
i−1 i
i+1
we miss the dashed transition from Figure 7 for time step t.
Behavior on Other Words. This describes the behavior on words of the correct
form but we also need to consider other words. There can be different reasons
why this is the case. As a start, we only want to consider words that are
∗
prefixes of words in ((∆0∗ )∗ #) (∆0∗ )∗ $0∗ $0. For this, we use the automaton
from Figure 8 (which is an S -automaton): qc ◦ will be defined on a word if and
only if the word is a prefix of one in the set.
Not every word on which qc ◦ is defined is of the correct form, however.
For example, the digit-block of a symbol can be too short so that we cannot
count high enough (it cannot be too long because we ignore trailing 0s). The
22

0/0
γ/γ

0/0

γ/γ
$/$

qc

$/$

0/0

#/#
Figure 8: The automaton part used for checking the form of the input word. Transitions
labeled with γ/γ exist for every γ ∈ ∆.

good news is that this case is already handled: since there is no outgoing ∆transition from the state at the bottom of Figure 6, qc0 ◦ will be undefined on
a word that contains a digit-block which is too short because each X will add
one (in reverse/least significant bit first binary representation) to the digit block
and we end up with a block consisting only of 1s; the next application of X will
be undefined at the next letter after this block.9 The same is true if the word
encodes a sequence of configurations in which one configuration is shorter than
p(n). However, we also need to handle the case where one of the configurations
is too long, i. e. longer than p(n), because we do not check this part for validity.
For this, we use ql from Figure 9 (which is, again, an S -automaton).
0/0
1/1

0/0

0/0
1/1

1/1
ql

γ/γ

$/$

$/$

0/0

γ/γ
#/#

Figure 9: The automaton part used to check that, in each configuration, each symbol was
check-marked. The transitions labeled with γ/γ exist for every γ ∈ ∆.

It checks that every digit-block contains at least one 1 (i. e. that every symbol
was check-marked). As there are exactly p(n) many Xs in qc0 , applying qc0 ◦
to a word (encoding a configuration sequence) will result in check-marks on the
first p(n) symbols of every configuration. If there is a symbol without a checkmark, the corresponding configuration is too long and ql qc0 ◦ will be undefined
on that word.
Summing this up, we have that ql qc0 qc ◦ is defined on a word if and only if
9 To

←−
←−
see this, apply X ◦ twice to γ bin2 (2)γ bin2 (1) = γ01γ10 (for γ ∈ ∆).

23

that word is a prefix of a word w which satisfies the following conditions.
∗

• w is from ((∆0∗ )∗ #) (∆0∗ )∗ $0∗ $0, i. e. w encodes a configuration sequence.
• The digit-block which belongs to a symbol at position i (for any time step)
allows for counting up to p(n) − i in (reverse) binary.
• The encoded configurations are all of length exactly p(n).
• w encodes a valid computation of M0 when started in the initial configuration c0 .
Finding Final States. Thus, we have distinguished valid computations from
other inputs. Next, we need to distinguish accepting computations (i. e. those
where we reach a final state from E). For this, we use state e from the S automaton depicted in Figure 10. This will toggle the trailing 0 into a 1 if and
only if the word contains a final state and the digit block in the suffix $00 . . . 0$0
contains only 0.
idΣ\({$}∪Γ×E)

0/0

$/$

e

$/$

0/0

$/$

0/1

“no final state (yet)”

idΓ×E
$/$

idΣ\{$}

0/0

“final state found”

1/1
idΣ

Figure 10: The automaton part used to find final states in a valid computation.

The Reduction. This gives us all necessary parts to prove that the word problem
for the automaton-inverse semigroup S generated by the union of all the previous
S -automata is PSpace-hard. For this, we need to state the reduction function
for any language L ⊆ Λ∗ which can be decided by a PSpace-machine M. The
function needs to map a problem instance of L, i. e. a word w ∈ Λ∗ , to a problem
instance of the word problem for S. Let c0 (w) be the initial configuration of
M0 on input of the encoding of w and M (where the latter only depends
on L). If n denotes the length of the input encoding, then c0 (w) has length
p(n). As M0 is a PSpace-universal Turing Machine, its computation starting

24

in c0 (w) accepts if and only M accepts w. Note that any position of c0 (w) can be
computed in logarithmic space. Thus, we can compute eql qc0 (w) qc and ql qc0 (w) qc
in logarithmic space as well. We use this pair of elements as the problem instance
for the word problem (in fact, for the word problem’s complement).
Now, we show that the thus defined function is a reduction function. First,
suppose that w′ ∈ L. Then, M accepts w′ and M0 accepts the encoding w
of the pair w′ and M. Let n denote the length of this encoding. There is
a sequence of configurations c0 , c1 , . . . , cT which describes a valid computation
of M0 such that c0 = c0 (w) and cT contains a final state (i. e. a symbol from
Γ×E). As before, let c′t be the word obtained from ct by inserting 0k blocks after
each symbol with k = ⌈log2 p(n)⌉. Then v = ql qc0 (w) qc ◦ c′1 #c′2 # . . . c′T $0k $0 is
defined and, because only the digits blocks have been manipulated (excluding
the one in the $0k $0 suffix), it contains an element from Γ×E. Also, it ends with
a 0. This 0 is toggled by e◦ into a 1. Thus, e◦v 6= v and eql qc0 (w) qc 6= ql qc0 (w) qc
in the generated (inverse) semigroup.
For the other direction, suppose w′ 6∈ L. Then, M0 will not accept the
encoding w of the pair w′ and M. Now, if a word u ∈ Σ∗ is not a prefix of
a valid encoding of M0 ’s computation on input w, then ql qc0 (w) qc ◦ will be
undefined on u and so will be eql qc0 (w) qc ◦ . If u is a prefix of a valid encoding
of the computation, then u must not contain a symbol from Γ × E because M0
does not accept. Thus, e will act like the identity on ql qc0 (w) qc ◦ u. This yields
eql qc0 (w) qc = ql qc0 (w) qc in the generated (inverse) semigroup, which concludes
the proof for the automaton-inverse semigroup case.
Extension to Groups. In the group case, we need a (single) rational constraint.
This is used to ensure the well-formedness of the words on which the states act.
The rational constraint we will be using depends on the input problem instance
w ∈ Λ∗ to the reduction function. Let n be the length of the encoding of the
pair w and M (one of the PSpace machines for the problem to reduce) as input
for M0 and let k = ⌈log2 p(n)⌉. Then, the constraint is

p(n) k
p(n) ∗
∆0k
$0 $0.
#
C(w) = ∆0k
Because we only need to count up to p(n), we can construct an acceptor for this
constraint in logarithmic space.
Due to the constraint, we do not have to consider words that do not encode
a sequence of (valid) configurations (we do have to consider words encoding a
sequence of configurations that is not a valid computation of M0 , however). So
far, we have checked the validity of the transition from time step t to time step
t + 1 by including the dashed transition in Figure 7 only if τ (γ−1 , γ0 , γ1 ) = γ0′ .
Since we need a complete automaton for the group case, we also need to have
transitions if this is not the case. That is where the so-far unused 0-block in
the suffix $00 . . . 0$0 comes into play; we use it in the S -automaton depicted in
Figure 11. The state f will skip everything up to the first $ and add one to the
following digit block (which is considered to be a reverse/least significant bit
first binary representation of some number). Remember that this will trigger a
25

idΣ\{$}

f

0/0
1/1

1/0
$/$

0/1

$/$

0/0

Figure 11: Automaton used for counting invalid transitions.

different behavior of e later on. Now, if we do not have the dashed transitions in
Figure 7, we add transitions to f instead. The behavior of the automaton may
now intuitively be described as follows. If the configuration sequence does not
belong to a valid computation of M0 , then qc0 (w) ◦ is not undefined anymore
but it will add one to the last digit block for every position with an invalid
transition.
In the other places where the automaton previously was not complete, we
may add transitions into a sink state (in such a way that the resulting automaton is a G -automaton). The rational constraint ensures that none of these
transitions is actually ever used.
Now, consider a problem L that is decided by the PSpace-machine M. First,
suppose the problem instance w ∈ Λ∗ belongs to L. Then, the computation of
M0 on the encoding of w and M is accepting. Thus, there is a u ∈ Σ∗ which
satisfies the constraint C(w) and encodes this computation of M0 up to the first
configuration that reaches a final state (i. e. contains an element from Γ × E).
On this u, we have qc0 (w) ◦ u 6= eqc0 (w) ◦ u because the digit block at the end
(counting the invalid transitions) remains 0k and e ◦ toggles the trailing 0 into
a 1.
If w 6∈ L, then in any word u satisfying the constraint (i. e. encoding a
sequence of valid configurations), there will either be an invalid transition or no
final state is reached, i. e. u does not contain a symbol from Γ × E. In either
case, qc0 (w) and eqc0 (w) will act on u in the same way.
This shows that mapping w to the element pair qc0 (w) and eqc0 (w) and the
rational constraint C(w) is a reduction from L to the (complement of the) word
problem with a single rational constraint for the automaton group generated by
the automaton described above. One may note that we use neither qc nor ql for
this reduction since their roles are now covered by the rational constraint.
So far, we have only been able to show PSpace-hardness of the word problem with a rational constraint in the group case. The question remains whether
the problem is also PSpace-hard in the absence of rational constraints (in the
uniform and non-uniform cases). Steinberg asks this question as well [24, Question 5] and suspects that the answer is “yes”. While the encoding techniques
presented in the previous proof come close to an answer to this question (as
they show PSpace-hardness for automaton-inverse semigroups), they still require some means of propagating a single bit from one element of the automaton

26

structure to the next. It is not clear how this can be done if the input is not in
some well-formed, well-known form or whether this can be done at all.
However, we can show a weaker result, with which we conclude this section:
NL-hardness of the uniform case.
Proposition 7. The uniform word problem for automaton groups is NL-hard.
Proof. It is easy to see that the following problem is NL-hard.
Constant: Σ = {0, 1}
Input:
a deterministic and complete Σ-acceptor A
Question: is L(A) empty?
For a Σ-acceptor A = (Z, Σ, δ, z0 , F ), we define the automaton TA = (Z, Σ, δ ′ )
by setting
δ ′ = {z

a/a

z ′ | a ∈ Σ, z ∈ Z \ F, z

{z

0/1

z ′ | z ∈ F, z

0

a

z ′ ∈ δ} ∪

z ′ ∈ δ} ∪ {z

1/0

z ′ | z ∈ F, z

1

z ′ ∈ δ}.

Structurally, TA behaves like A. For non-final states z ∈ Z \ F , we have z ◦ 0 = 0
and z ◦ 1 = 1, while, for final states z ∈ F , z ◦ swaps 0 and 1. One should verify
that, for all Σ-acceptors A, TA is a G -automaton by construction.
We use TA to give a reduction from the problem stated above to the uniform word problem for automaton groups. An acceptor A is mapped to the
automaton TA and the input sequence z0 , which consists of only a single state
(i. e. n = 1). For the other sequence, we use 1 (or, more precisely, the empty
sequence with m = 0, which we consider to act as the identity on Σ∗ ). This
mapping can, clearly, be computed by a deterministic Turing Machine in logarithmic space.
Next, we show that L(A) = ∅ if and only if z0 ◦ is the identity on Σ∗ . Suppose
there is a word u = a1 a2 . . . aℓ ∈ L(A) (with a1 , a2 , . . . , aℓ ∈ Σ). Then, we have
z0 · u = zF for a zF ∈ F . Therefore, we have z0 ◦ u0 = v(zF ◦ 0) = v1 6= u0 for
a word v ∈ Σ∗ of length ℓ. Thus, z0 ◦ is not the identity on Σ∗ . Now, suppose
there is a word u = a1 a2 . . . aℓ (with ai ∈ Σ) such that u 6= v for v = z0 ◦ u.
Since z0 ◦ will map any prefix of u to v’s prefix of the same length, we may,
without loss of generality, assume that u and v differ only in the last letter.
Let zF = z0 · a1 a2 . . . aℓ−1 . Then, we have zF ◦ aℓ 6= aℓ . However, this can
only be the case if zF ∈ F . Thus, we have a1 a2 . . . aℓ−1 ∈ L(A) and, therefore,
L(A) 6= ∅.
If one bounds n and m in the uniform word problem for automaton groups
by some constant, then, by Proposition 2, this problem is in NSpace(log |T |).
By the Space Hierarchy Theorem [23, 19], it, therefore, cannot be PSpace-hard.
This implies that, if one wants to show PSpace-hardness of the uniform word
problem for automaton groups, then the sum n+m must increase with the size of
the instances. The same is in particular also true for showing PSpace-hardness
of the word problem for a specific automaton group.

27

Acknowledgements
The first author was supported by Austrian Science Fund (FWF) project
P29355-N35. The second author acknowledges support from INDAM-GNSAGA.
Summary of the contributions of this paper
• We extend the notion of automaton semigroups to semigroups generated
by partial automata. We show that, if S is an automaton group (in the
partial sense), then S adjoined with a zero is a complete automaton semigroup (Proposition 1).
• We introduce the notion of automaton-inverse semigroups as semigroups
generated by partial, invertible automata.
• We extend Steinberg’s observation about an NSpace(n) algorithm for the
word problem of automaton groups to cover the uniform word problem
for automaton semigroups, automaton-inverse semigroups and automaton groups, each with and without rational constraints (Proposition 2).
We also consider the algorithm for the non-uniform version of the word
problem (Proposition 3).
• We show that the upper bound on the length of a word on which two
distinct elements of an automaton semigroup act differently must be exponential (Proposition 4). The question about a better upper bound than
the trivial one was raised by Cain [6, Open problem 3.6].
• We give simple constructions which show that the uniform word problems for automaton semigroups and automaton-inverse semigroups are
PSpace-hard and, thus, PSpace-complete (Proposition 5). For automaton groups, the construction shows PSpace-hardness of the uniform word
problem with a single rational constraint (thus, also, showing PSpacecompleteness of this problem).
• We give a more complex construction which shows that there is an automaton-inverse semigroup (and, thus, also an automaton semigroup) for
which the word problem is PSpace-complete (Proposition 6). We extend
the construction to show that there is an automaton group for which the
word problem with a single rational constraint is PSpace-complete.
• We give a simple reduction to show NL-hardness of the uniform word
problem for automaton groups (Proposition 7).

28

References
[1] A. Akhavi, I. Klimann, S. Lombardy, J. Mairesse, M. Picantin, On the
finiteness problem for automaton (semi)groups, Internat. J. Algebra Comput. 22 (2012) 1 – 26.
[2] I. V. Bondarenko, Growth of Schreier graphs of automaton groups, Math.
Ann., 354 (2012) 765 – 785.
[3] I. V. Bondarenko, The word problem in Hanoi Towers groups, Algebra and
Discrete Math., 17 (2014) 248 – 255.
[4] T. Brough, A. J. Cain, Automaton semigroup constructions, Semigroup
Forum, 90 (2015) 763 – 774.
[5] T. Brough, A. J. Cain, Automaton semigroups: New construction results
and examples of non-automaton semigroups, Theoret. Comput. Sci., 674
(2017) 1 – 15.
[6] A. J. Cain, Automaton semigroups, Theoret. Comput. Sci., 410 (2009)
5022 – 5038.
[7] D. D’Angeli, E. Rodaro, Groups and semigroups defined by colorings of
synchronizing automata, Internat. J. Algebra Comput., 24 (2014) 773 –
793.
[8] D. D’Angeli, E. Rodaro, A geometric approach to (semi)-groups defined
by automata via dual transducers, Geom. Dedicata, 174 (2015) 375 – 400.
[9] D. D’Angeli, E. Rodaro, Freeness of automaton groups vs boundary dynamics, J. Algebra, 462 (2016) 115 – 136.
[10] P. Gillibert, The finiteness problem for automaton semigroups is undecidable, Internat. J. Algebra Comput., 24 (2014) 1 – 9.
[11] Th. Godin, I. Klimann, M. Picantin, On torsion-free semigroups generated
by invertible reversible Mealy automata, in: A.-H. Dediu, E. Formenti,
C. Martín-Vide, B. Truthe (Eds.), Language and Automata Theory and
Applications (LATA 2015), volume 8977 of Lecture Notes in Comput. Sci.,
Springer, Berlin, 2015, pp. 328–339.
[12] R. I. Grigorchuk, I. Pak, Groups of intermediate growth: an introduction,
Enseign. Math. (2), 54 (2008) 1 – 272.
[13] J. M. Howie, Fundamentals of Semigroup Theory, London Mathematical
Society Monographs, The Clarendon Press, Oxford University Press, New
York, 1995.
[14] N. Immerman, Nondeterministic space is closed under complementation,
SIAM J. Comput., 17 (1988) 935 – 938.

29

[15] D. Kozen, Lower bounds for natural proof systems, in: 18th Annual
Symposium on Foundations of Computer Science (Providence, R.I., 1977),
pages 254–266. IEEE Comput. Sci., Long Beach, Calif., 1977, pp. 115 –
123.
[16] V. Nekrashevych, Self-similar groups, volume 117 of Mathematical Surveys
and Monographs, American Mathematical Society, Providence, RI, 2005.
[17] V. Nekrashevych, Self-similar inverse semigroups and Smale spaces, Internat. J. Algebra Comput., 16 (2006) 849 – 874.
[18] A. S. Olijnyk, V. I. Sushchansky, J. K. Slupik. Inverse semigroups of partial
automaton permutations, Internat. J. Algebra Comput., 20 (2010) 923 –
952.
[19] Ch. M. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, Reading, MA, 1994.
[20] M. Petrich, Inverse Semigroups, Pure & Applied Mathematics. John Wiley
& Sons, Inc., New York, 1984.
[21] M. Picantin, Automatic semigroups vs automaton semigroups,
preprint arXiv:1609.09364, 2016.

arXiv

[22] W. J. Savitch, Relationships between nondeterministic and deterministic
tape complexities, J. Comput. System. Sci., 4 (1970) 177 – 192.
[23] J. I. Seiferas, M. J. Fischer, A. R. Meyer, Refinements of the nondeterministic time and space hierarchies, in: 14th Annual IEEE Symposium
on Switching and Automata Theory (Univ. Iowa, Iowa City, Iowa, 1973),
IEEE Comput. Soc., Northridge, Calif., 1973, pp. 130 – 137.
[24] B. Steinberg, On some algorithmic properties of finite state automorphisms
of rooted trees, volume 633 of Contemp. Math., Amer. Math. Soc., Providence, RI, 2015, pp. 115 – 123.
[25] R. Szelepcsényi, The method of forced enumeration for nondeterministic
automata, Acta Inform., 26 (1988) 279–284.

30

