A new hierarchy for automaton semigroups
Laurent Bartholdi Thibault Godin Ines Klimann Matthieu Picantin






École Normale Supérieure, Paris, and
Georg-August-Universität zu Göttingen,

laurent.bartholdi@ens.fr,

University of Turku, Turku, 
 thibault.godin@utu.fi, supported by the Academy of Finland grant 296018
IRIF, UMR 8243 CNRS & Université Paris Diderot,
 klimann@irif.fr, picantin@irif.fr





A new hierarchy
 for automaton semigroups
    Laurent Bartholdi 1,
Thibault Godin2,
Ines Klimann3, and
Matthieu Picantin3
    This version: December 30, 2023
===============================================================================




  We define a new strict and computable hierarchy for the family of
  automaton semigroups, which reflects the various asymptotic
  behaviors of the state-activity growth. This hierarchy extends that
  given by Sidki for automaton groups, and also gives new insights into
  the latter.  Its exponential part coincides with a notion of entropy
  for some associated automata.

  We prove that the is decidable when the state-activity is
  bounded. The remains open for the next level of this hierarchy,
  that is, when the state-activity is linear. Gillibert showed that it
  is undecidable in the whole family.

  The former results are implemented and will be available in the
   package  developed by the first author.




 



§ INTRODUCTION




The family of automaton groups and semigroups has provided a wide playground
to various algorithmic problems in computational (semi)group theory <cit.>.
While many undecidable questions in the world of (semi)groups remain
undecidable for this family, the underlying Mealy automata provide a combinatorial leverage
to solve the for this family, and various other problems in some important subfamilies.
Recall that a Mealy automaton is a letter-to-letter, complete,
deterministic transducer with same input and output alphabet, so each of its states
induces a transformation from the set of words over its alphabet into itself.
Composing these Mealy transformations leads to so-called automaton
(semi)groups, and the can be solved using a classical technique of minimization.

The is one of the current challenging problems in computational
(semi)group theory. On the one hand, it was proven to be undecidable for automaton
semigroups by Gillibert <cit.>.
On the other hand, Sidki introduced a polynomial hierarchy for
invertible Mealy transformations in <cit.> and, with
Bondarenko, Bondarenko, and Zapata in <cit.>, solved the for its lowest level (bounded invertible automata).

Our main contributions in this paper are the following: an
activity-based hierarchy for possibly non-invertible Mealy
transformations (Section <ref>), extending Sidki's
construction <cit.> to non-necessarily-invertible transformations;
and a study of the algorithmic properties in the lowest level of the
hierarchy, namely transducers with bounded activity. We prove:
[see Section <ref>]
  The is decidable for bounded Mealy transformations; namely,
  there is an algorithm that, given a bounded initial Mealy automaton,
  decides whether the transformation τ that it defines has
  infinite order, and if not finds the minimal r>s such that
  τ^r=τ^s.


Our strategy of proof follows closely that of Sidki's <cit.>
and Bondarenko, Bondarenko, Sidki and Zapata <cit.>, with some
crucial differences. On the one hand, a naive count of the number of
non-trivial states of a transformation does not yield a useful
invariant, nor a hierarchy stable under multiplication; on the other
hand, the structure of cyclic semigroups
(⟨ a | a^m =a^m+n⟩ has index m and period
n) is more complex than that of
cyclic groups (⟨ a| a^m⟩ has order m).





§ NOTIONS FROM AUTOMATA AND GRAPH THEORY


This section gathers some basics about automata, especially some links
between automata, Mealy automata, automaton semigroups, and
finite-state transformations.  We refer the reader to handbooks for
graph theory <cit.>, automata theory <cit.>, and automaton
(semi)groups <cit.>.

A non-deterministic finite-state automaton (for short) is
given by a directed graph with finite vertex set Q, a set of edges
Δ labeled by an alphabet Σ, and two distinguished subsets
of vertices I⊆ Q and F⊆ Q. The vertices of the
graph are called states of the automaton and its edges are
called transitions. The elements of I and F are called
respectively initial and final states.  A transition
from the state p to the state q with label x is denoted
by pq.

A is deterministic—for short—(complete) if for each state q and each letter x, there
exists at most (at least) one transition from q with
label x.  Given a word w=w_1w_2⋯ w_n ∈Σ^*
(where the w_i are letters), a run with label w
in an automaton ( or ) is a sequence of consecutive
transitions

    q_1q_2
      q_3→⋯→ q_nq_n+1 .

Such a run is successful whenever q_1 is an initial state
and q_n+1 a final state.  A word in Σ^* is
recognized by an automaton if it is the label of at least one
successful run. The language recognized by an automaton is the
set of words it recognizes.  A is coaccessible if each
state belongs to some run ending at a final state.

Let 𝒜 be a with stateset Q. The Rabin–Scott
powerset construction <cit.> returns, in a nutshell, the
(co)accessible —denoted by 𝒜—with states
corresponding to subsets of Q, whose initial state is the subset
of all initial states of 𝒜 and whose  final states are
the subsets containing at least on final state of 𝒜; its transition labeled by x from a state S⊆ 2^Q leads to the state {q | ∃ p ∈ S, pq  in 𝒜}.
Notice that the size of the resulting might therefore be exponential in the size of the original .

The language of a is the subset of Σ^* consisting
in the words recognized by it. Given a language L⊆Σ^*, its
entropy is

    h(L) = lim_ℓ→∞  1/ℓ log#(L
            ∩Σ^ℓ) .

This quantity appears in various situations, in particular for
subshifts <cit.> and finite-state automata <cit.>. We
shall see how to compute it with matrices.

To a 𝒜, associate its transition matrix
A = {A_i,j}_i,j∈^n× n where A_i,j is the
number of transitions from i to j. Let furthermore v∈^n
be the row vector with `1' at all positions in I and w∈^n be
the column vector with `1' at all positions in F. Then
v A^ℓ w is the number of successful runs in 𝒜 of
length ℓ. Assuming furthermore that 𝒜 is
deterministic, v A^ℓ w is the cardinality of L∩Σ^ℓ.

Since the transition matrix of an automaton 𝒜 is
non-negative, it admits a positive real eigenvalue of maximal absolute
value, which is called its Perron-Frobenius eigenvalue and is
written λ(𝒜). Assuming therefore that 𝒜 is coaccessible, we get
<cit.>
  Let 𝒜 be a coaccessible recognizing the language
  L. Then we have h(L) = logλ(𝒜).




 §.§ Mealy transducers

A Mealy automaton is a over an alphabet of the form
Σ×Σ. If an edge's label is (x,y), one calls x the
input and y the output, and denotes the transition
by pq. Such a Mealy automaton  is
assumed to be complete and deterministic in its inputs: for every
state p and letter x, there exists exactly one transition
from p with input letter x. We denote by px its
corresponding output letter and by px its target state,
so we have


[->,>=latex,node distance=36mm,inner sep=0pt]
  [state] (0) p;
  [state,right of=0] (1) px;
  (0) edge node[above] x|px (1);




In this way, states act on letters and letters on states.
Such actions can be composed in the following way: let
q∈ Q^*, p∈ 
Q, u∈Σ^*, and x∈Σ, we have

    qpx = p(qx)   and   p(ux) = (pu)x .



We extend recursively the actions of states on letters and of letters on states (see below left).
Compositions can be more easily understood via an alternative representation by a cross-diagram <cit.> (below right).



For all x ∈Σ, u∈Σ^*, p∈ Q, q∈ Q^*, we have:


.4

    q(ux) =
    ququx

and

    (qp)u =
    qu·pqu .


.4



    [       q       p;   u      qu     qpu;      qu     pqu    ;   x     qux        ;     qux             ]







The mappings defined above are length-preserving and prefix-preserving. Note that in particular the image of the empty word is itself. 


From an algebraic point of view, the composition gives a semigroup structure to the set
of transformations u↦qu for q∈ Q^*. This
semigroup is called the semigroup generated by  and
denoted by .
An automaton semigroup is a semigroup which can be generated by
a Mealy automaton. Any element of such an automaton semigroup
induces a so-called finite-state transformation.

Conversely, for any transformation t of Σ^*
and any word u∈Σ^*, we denote by
tu the image of u by t, and by
tu the unique transformation s of Σ^*
satisfying t(uv)=tusv
for
any v∈Σ^*.
Whenever Q(t)={tu:u∈Σ^*} is finite,
t is said to be finite-state and admits a unique (minimal)
associated Mealy automaton _t with stateset Q(t).

We also use the following convenient notation to define a finite-state
transformation t: for each u∈ Q(t), we write an equation (traditionally called wreath recursion in the algebraic theory of automata) of the
following form

    u=(ux_1,…,ux_|Σ|)σ_u,

where σ_u=[ux_1,…,ux_|Σ|] denotes
the transformation on Σ induced by u.


We consider the semigroup  of those finite-state transformations of Σ^*.

 The transformation t_0=(,t_0)[2,2] belongs to ({1,2}^*) with Q(t_0)={,t_0}.
See Examples <ref> and <ref> for further details about t_0.


 The transformation p=(q,r) with q=(r,)
and r=(r,r)[2,2] also belongs to ({1,2}^*) with Q(p)={,p,q,r}.
See Figure <ref> for _p.








§ AN ACTIVITY-BASED HIERARCHY FOR 


In this section we define a suitable notion of activity for finite-state transformations, together with two norms, from which we build a new hierarchy.
We will prove its strictness and its computability in Section <ref>.

For any element t∈, we define its activity (see Figure <ref>) as

    α_t:n⟼#{v∈Σ^n:∃u∈Σ^n, tu≠ and tu=v}.





We next define two norms on .
When α_t has polynomial growth, namely when the set D={d:lim_n→∞α_t(n)/n^d=0} is nonempty,
then we define t=min D-1. 
Otherwise, the value of lim_n→∞logα_t(n)/n is denoted by t.

We then define the following classes of finite-state transformations:

    d   ={ t∈:t≤ d }
    and  λ   ={ t∈:t≤λ } .


We shall see in Theorem <ref> that these yield a strict and computable hierarchy for .
The following basic lemma is crucial:

 For each n≥ 0, the map t↦α_t(n) is subadditive.




Assume s,t∈.

[t]0.46
For any u∈Σ^n with (st)u≠,
we have either su≠ or tsu≠.

We deduce α_st(n)≤α_s(n)+α_t(n) for each n≥ 0.

[t]0.5   


[thick,node distance=13mm]
	[thick,node distance=16mm,xshift=50mm]
	(01) at (0,1.25) u;
	(10) at (.75,2)  s;
	(12) [below of=10] su;
	(11) [node distance=20mm,right of=01] v=su;
	(20) [node distance=23mm,right of=10] t;
	(22) [node distance=16mm,below of=20] tv;
	(31) [node distance=23mm,right of=11] w=tv;
	(44) [node distance=16mm,below of=11] (st)u≠;
	
	[->,>=latex]
		(01)	edge  (11)
		(10)	edge  (12)
		(11)	edge  (31)
		(20)	edge  (22);
	[decorate,decoration=brace,amplitude=7pt,aspect=.5]   (22.south east)–(12.south west);
	







We deduce that . and . are respectively +- and max-subadditive.

 Let Σ be an alphabet.
For every integer d≥ -1, d is a subsemigroup of .
So is λ for every 0 ≤λ≤#Σ.


As an easy corollary of Proposition <ref>,
the subadditivity property allows us to compute the hierarchy class
of any given Mealy automaton by considering only its generators.

 Let Σ be an alphabet.
The elements of the semigroup  can be graded according to the following strict 
hierarchy:
for any d_1,d_2∈ with -1<d_1<d_2 and
any λ_1,λ_2∈
with 0<λ_1<λ_2<#Σ,  we have:

    -1⊊⋯⊊d_1⊊⋯⊊d_2⊊⋯⊊0


    ⊊λ_1⊊⋯⊊λ_2⊊⋯⊊#Σ.



The proof of the previous result is postponed to the end of Section <ref> on page proof:hierarchy.

Sidki defined in <cit.> the activity of a finite-state automorphism t∈(Σ^*) as 
    θ_t:n⟼{u∈Σ^n: tu≠},
 and the corresponding classes (d). Using this notion of activity θ for transformations leads inevitably to an impasse: the associated classes with fixed degree polynomial θ-activity would be not closed under composition. However it is straightforward that our new notion
of activity α coincides with Sidki's activity θ in the case of automorphisms.

The class 0 coincides with the infinite union ⋃_d ≥ -1d, whose corresponding automorphisms class is denoted by (∞) in <cit.>.





§ STRUCTURAL CHARACTERIZATION OF THE ACTIVITY NORM


From <cit.>, we know that the finite-state automorphisms which have polynomial activity are exactly those  whose underlying automaton does not contain entangled cycles (except on the trivial state). Moreover, the degree of the polynomial is given by the longest chain of cycles in the automaton. The first claim remains true for transformations, but things are a bit more involved for the second one (see Example <ref>).

To any minimal Mealy automaton  with stateset Q and alphabet Σ, we associate
its pruned output automaton  defined as the with stateset Q∖{} (all states being final) and alphabet Σ,
and whose transitions are given, for p,q∈ Q∖{}, by

    p  q  ∈   ⟺   p  q  ∈ .

According to context, we shall identify a transformation t∈, the state of _t, and the corresponding state of _t.


The activity of a transformation t ∈ is the number of paths starting from t
in the (non-complete) deterministic automaton _t constructed via the Rabin–Scott construction.



Let t ∈ with _t its associated automaton.  Let us count the words v∈Σ^n for which there is a word u∈Σ^n with tu≠ and tu=v. For n=1, α_t(1) is exactly the number of different outputs from the state t that do not lead to a trivial state of _t. Now for v∈Σ^n, if ℰ denotes the set of those
states accessible from t by reading v (this corresponds to the Rabin–Scott powerset construction) in _t,
the number of ways to extend v without getting into a trivial state in _t corresponds to the number of outputs of the state ℰ in _t, whence the result.


Whether the activity of a given t∈ is polynomial or
exponential can be decided by only looking at the cycle structure
of _t. Any cycle considered throughout this paper is
simple: no repetitions of vertices or edges are allowed. Two cycles
are coreachable if there exists a path from any of them to the
other one. A chain of cycles is a sequence of cycles such that each cycle is reachable from its predecessor.


A transformation t ∈ has exponential activity if and only if it can reach two coreachable cycles with distinct labels in _t.



(⇐) Assume that t can reach a state s ∈_t that lies on two cycles with distinct labels.
There exist a word u∈Σ^* satisfying tu=s
and two words v,w∈Σ^* satisfying sv=s=sw
and sv≠sw.
We obtain α_t(ℓ) ≥{tx|x∈u(v+w)^* ∩Σ^ℓ} for ℓ≥0. Therefore α_t grows exponentially.

(⇒) Assume that t has exponential activity and cannot reach two coreachable cycles in _t. By Lemma <ref>, there exist a subset ℰ⊂ Q and three words u,v,w∈Σ^* such that ℰ is the set of nontrivial states accessible from t reading u  and the paths labeled by v and w are cycles starting from ℰ in _t. It means that  v and w are also cycles starting from t in _t, contradiction.


Using the subadditivity of the activity (see Lemma <ref>), we get for the polynomial activities:


Let  be a Mealy automaton. The transformations of  are all of polynomial activity if and only if there are no coreachable cycles in the automaton . Moreover the degree of the (polynomial) activity corresponds to the longest chain of cycles in  minus 1.




 Consider the transformation t_0=(,t_0)[2,2] from Example <ref>, its square t_0^2, and the associated automata _t_0^2 and _t_0^2:


[->,>=latex,node distance=16mm]
	[]
	[draw,circle,minimum width=19pt,inner sep=0pt] (tt) t_0^2;
	[draw,circle,minimum width=19pt,inner sep=0pt,right of=tt] (t) t_0;
	[draw,circle,minimum width=19pt,inner sep=0pt,right of=t] (one) ;
	(tt)	edge[loop below] 		node[below]2|2	(tt)
		(tt)	edge				node[below]1|2	(t)
		(t)	edge[loop below] 		node[below]2|2	(t)
		(t)	edge				node[below]1|2	(one)
		(one)	edge[loop right]		node[right,align=center]1|1
2|2	(one);
	
	[xshift=6.5cm,node distance=20mm]
	[draw,rectangle,minimum height=19pt] (tt) { t_0^2 };
	[draw,rectangle,minimum height=19pt,right of=tt] (ttt) { t_0^2,t_0 };
	[draw,rectangle,minimum height=19pt,right of=ttt] (t) { t_0};
	(tt)	edge[] 		node[below]2	(ttt)

		(ttt)	edge[loop below] 		node[below]2	(ttt)
		(t)	edge[loop below] 		node[below]2	(t);
	



Note that, before determinization, two disjoint cycles are accessible from the state t_0^2. In the determinized version, {t_0} and {t_0^2} both access to only one cycle, and we conclude {t_0,t_0^2}⊂0. By Proposition <ref>, we actually knew the full inclusion t_0 ⊂0.

Defining further t_k=(t_k-1,t_k)[2-(k  2), 2-(k  2)]∈({1,2}^*), we obtain the family with t_k∈k∖k-1 for k>0,
that witnesses the strictness of the polynomial part of the hierarchy from Theorem <ref>.


Using Proposition <ref>, we obtain an explicit formula for the norm ·:


  Let t be a finite-state transformation with associated Mealy
  automaton _t.  The norm t is the logarithm of
  the Perron eigenvalue of the transition matrix of
  _t:
  
    t = logλ(_t)  .



 By Lemma <ref>, the activity of t counts the number of paths in _t.
Since all its states are final, this automaton is coaccessible and the cardinality of the language accepted when putting t as the initial state is exactly the activity of t.
Therefore by Proposition <ref>, we have

    t = lim_ℓ→∞logα_t(ℓ) ℓ = lim_ℓ→∞1/ℓ log∑_t'=1^n (A^ℓ)_t,t'  = h(L) = logλ(_t),

with A=(A_i,j)_i,j the adjacency matrix of _t.


Proof of Theorem <ref>. The strictness for the polynomial part is obtained from Example <ref>. Now, as the norm . is the logarithm of the maximal eigenvalue of a matrix with integer coefficients, the classes λ increase only when e^λ is an algebraic integer that is the largest zero of its minimal polynomial, , a root of a Perron number. Furthermore, each of these numbers is the norm of some finite-state transformation, see <cit.> for a proof. It is also known that Perron numbers are dense in [1,∞), which gives us the strictness for the exponential part: λ_1<λ_2 implies λ_1⊊λ_2. 

Finally, the growth rate  can be computed with any precision 0<δ <1 in time Θ(-log ( δ n) ), where n is the number of states of the automaton <cit.>.


 Consider the transformations =(,)[1,1] and =(,) with common associated automata 
(on the left) and  (on the right):


[->,>=latex,node distance=17mm]
	
	[draw,circle,minimum width=19pt] (s) ;
	[draw,circle,minimum width=19pt,right of=s] (t) ;
	[draw,circle,minimum width=19pt,right of=t] (one) ;
	(s)	edge[loop left] 		node[left]2|1	(s)
		(s)	edge[bend left=10] 	node[above]1|1	(t)
		(t)	edge[bend left=10] 	node[below]2|2	(s)
		(t)	edge				node[below]1|1	(one)
		(one)	edge[loop right]		node[right,align=center]1|1
2|2	(one);
	
	[xshift=57.5mm]
	[draw,rectangle,minimum height=16pt] (t) {};
	[draw,rectangle,minimum height=16pt,right of=t] (s) {};
	[draw,rectangle,minimum height=16pt,right of=s] (st) {,};
	(st)	edge[loop right,xscale=.6] 	node[right]1	(s)
		(t)	edge[] 			node[above]2	(s)
		(s)	edge[bend left=10] 	node[above]1	(st)
		(st)	edge[bend left=10] 	node[below]2	(s);
	



We find that α_(n) and α_(n+1)
correspond to the n-th Fibonacci number.
We deduce ==logφ where φ is the golden ratio,
hence ,∈logφ. 






§ THE ORBIT SIGNALIZER GRAPH AND THE ORDER PROBLEM


This section is devoted to the : can one decide whether a given
element generates a finite semigroup?  The latter is known to be
undecidable for general automaton semigroups <cit.> and
decidable for (0) <cit.>. We give a general
construction that associates a graph to a transformation of
Σ^*, and show that, if finite, this graph lets us compute the
index and period of the transformation.  We show that this graph is
finite for elements from (0), and solve the in this
manner.

Let Σ be an alphabet. We define the orbit signalizer graph Φ for (Σ^*) as the following (infinite) graph. The vertices are the pairs of elements in (Σ^*).
For each letter x∈Σ, there is an arrow from the source (s,t) with label (x )
where  and  are the minimal integers (with >0) satisfying
    st^+x=st^x,

and with target (rx,t^rx) for r=st^.
The parameters  and  correspond respectively to the index
and to the period of the orbit of x under the action of st^ω, see Figure <ref>. 

In what follows, the intuition is roughly to generalize Figure <ref>, by considering a path π instead of the letter x: such a construction leads also to a pan graph, whose handle has length between i^-_t and i^+_t, and whose cycle has length p_t. The main challenge here is to be able to keep the construction finite, when possible.

