Abstract

We extend the notion of activity for automaton semigroups and monoids introduced by Bartholdi, Godin, Klimann and Picantin to a more general setting. Their activity notion was already a generalization of Sidki’s activity hierarchy for automaton groups. We show that the language of \(\omega\)-words with infinite orbits is effectively a deterministic Büchi language for automata with bounded extended activity, which yields decidability of the finiteness problem for complete automaton semigroups and monoids of bounded activity (solving an open problem by Bartholdi, Godin, Klimann and Picantin). In fact, we obtain a stronger result also covering finitely generated subsemigroups.

Keywords: automaton semigroup; automaton monoid; bounded automaton; finiteness problem; orbital graph.
Mathematics Subject Classification 2010: 68Q70, 20M35, 20E08

Introduction The class of automaton groups is a rich source for groups with exotic properties. Probably the most famous one of these groups is Grigorchuk’s group (and we refer the reader e. g.to [1], [2] for many more examples). Grigorchuk’s group was the first example of a group with intermediate growth (see e. g.[3] for more information) and is also a Burnside group (in the sense that it is infinite while every element has finite order) as well as amenable but not elementary amenable (see e. g.[4]). Interestingly, it is not finitely presented [5] but, as an automaton group, it has a finite description using an automaton. This demonstrates that using automata to generate groups (and also semigroups) is algorithmically interesting as we may give the generating automaton as a finite input to an algorithm, which allows us to consider algorithms for groups that do not have finite presentations (in the sense of a pair of finitely many generators and finitely many relations over them). Semigroups arise naturally in this field (e. g.via the dual automaton) and have received quite a lot of attention structurally (e. g.[6]–[15]) and algorithmically (e. g.[11], [16]–[19]).

An automaton in this context is a deterministic and complete finite-state, letter-to-letter transducer (without initial or final states), i. e.a finite graph whose edges are labeled by pairs \((a, b)\) of an input letter \(a\) and an output letter \(b\). The idea is that we may start reading an input word \(u\) in some state \(p\) (i. e.some node) and obtain a corresponding output word \(v\). This way, we may associate to \(p\) a function that maps \(u\) to \(v\) and consider the closure under composition of these functions for all states as the semigroup generated by the automaton. For invertible automata, these functions are bijections and we naturally obtain a group. Groups and semigroups arising in this way are called automaton groups and automaton semigroups.

More structure was brought into this by Sidki’s activity notion [20] for automaton groups. His idea was to look at the structure of the cycles in the automaton (see [20] or e. g.[21] for more details). A word \(u\) here is said to be active for a state \(p\) if, after reading \(u\) starting in \(p\), we do not end in a/the state acting as the identity on all words. If the number of active words of any length is bounded uniformly by a constant, we say that \(p\) has bounded activity. If the number of words grows linearly with their length, we speak of linear activity. If it grows quadratically (cubically, etc.), also the activity is quadratic (cubic, etc.). It turns out, that the activity is either polynomial (with a natural number as the degree) or exponential.

The activity of a single state naturally generalizes to the activity of a group element (which is typically given as a word over the states as generators). If two group elements have, say, bounded activity, also their product has, which allows us to speak, for example, of bounded automaton groups (in which all elements have bounded activity). This yields an infinite hierarchy within the class of automaton groups, which consists of a polynomial and an exponential part. Interestingly, many famous and interesting examples of automaton groups are already contained in the second-lowest level of bounded activity (the lowest level belonging to finitary automata consists precisely of the class of finite groups in the sense that every finite automaton generates a finite group and every finite group is generated by a finitary automaton; compare to 2). This applies, in particular, to Grigorchuk’s group (and further examples, see e. g.in [21]).

Maybe surprisingly, bounded automaton groups (despite their already quite complicated nature) seem to be “finite enough” such that many of their decision problems remain decidable (or have lower complexity compared to general automaton groups). For example, the order problem is decidable in such groups [22] while it is undecidable for general automaton groups [23], [24]. Their finiteness problem is also decidable [25] while the problem is widely suspected to be undecidable in the general case but sill open [26] (it is known to be undecidable for automaton semigroups [17]). Furthermore, bounded automaton groups are contracting [27] (see also e. g.[2], [21]) and their word problem is therefore solvable in logarithmic space (by a deterministic Turing machine) while, for general automaton groups, there is one with \(\mathrm{\small PSpace}\)-complete word problem [28] (see [21] for more background information; see also [29] for the word problem on the lowest level of the hierarchy).

Likely driven by such algorithmic results (as they show that the order/torsion problem remains decidable), Bartholdi, Godin, Klimann and Picantin [11] generalized the notion of activity to automaton monoids.³ In order to keep certain desirable properties of the activity notion in the group case, their generalization rather uses the output instead of the input for defining active words, which makes the geometric characterization based on the cyclic structure of the generating automaton less transparent. However, they still count those words that do not end in the/an identity state, which obviously is only a useful concept if such an identity state exists; in this case, however, the generated semigroup is necessarily a monoid. As a potential extension (that is also interesting for semigroups), they propose to replace the identity state by what is called the maximal NoCyWEx subautomaton (whose definition is a bit technical but which necessarily generates a finite subsemigroup).

However, there does not seem to be any reason to only consider this particular subautomaton. Instead, we introduce a different notion of extended activity where we may consider any subset \(S\) of states (which is not a restriction as any finite set of semigroup elements may always be considered to appear as single states) that is closed in the sense that we may not leave \(S\) by reading any word in the generators. A(n output) word is then \(S\)-active if we do not end in a state in \(S\) after reading it. This strictly generalizes all previous activity notions: if we let \(S\) contain only the identity state, we obtain the activity notion for groups and monoids and, if we take \(S\) as the NoCyWEx part of the automaton, we obtain the above extended activity.

We then consider automata which have bounded \(S\)-activity. We show that, if we are given the promise that \(S\) generates a finite subsemigroup (as the finiteness problem for automaton semigroups is undecidable [17]), then the finiteness problem for automaton semigroups of bounded \(S\)-activity is decidable. This works, in particular, for all the other activity notions and generalizes the corresponding group result [25] to semigroups and monoids (solving an open problem stated by Bartholdi, Godin, Klimann and Picantin [11]). In fact, we obtain this algorithmic result by showing that the language of \(\omega\)-words with an infinite orbit is recognized (by an effectively constructible) deterministic Büchi acceptor (which also is a generalization from the group case in [25]). The construction of this Büchi acceptor is based on the notion of expandability introduced by the authors in [18] and the final connection to the finiteness problem is due to the fact that an automaton semigroup is infinite if and only if it admits an (infinite) word with an infinite orbit. As a by-product of our characterization of words with infinite orbits as Büchi languages, we obtain that an automaton semigroup of bounded \(S\)-activity is infinite if and only if it admits an ultimately periodic word with an infinite orbit.

In fact, we obtain these results not only for the full orbits but also for the case where we consider the sub-orbits given by a regular, suffix-closed language of the state set. This shows, in particular, that the finiteness problem for finitely generated subsemigroups of automaton semigroups with bounded \(S\)-activity is decidable (which the order problem is a special case of; compare to [11]).

We are confident that the techniques we use to obtain our results can also be refined to cover further algorithmic (and non-algorithmic) problems.

Preliminaries

0.0.0.1 Sets, Semigroups, Words and (Regular) Languages.

We write \(\mathcal{P}(A)\) for the power set of a set \(A\) and \(A \uplus B\) for the disjoint union of two sets \(A\) and \(B\). A set \(S\) with an associative operation is a semigroup and, if \(S\) additionally has a neutral element (i. e.an element \(e \in S\) with \(es = s = se\) for all \(s \in S\)), it is a monoid. We assume the reader to be familiar with the basics of semigroup theory but we will not need any advanced concepts.

An alphabet is a non-empty, finite set \(\Sigma\). By \(\Sigma^*\), we denote the set of finite words over \(\Sigma\) including the empty word \(\varepsilon\). If we want to exclude it, we write \(\Sigma^+\). For the set of finite words of length exactly \(n \geq 0\), we write \(\Sigma^n\). By \(\Sigma^\omega\), we denote the set of \(\omega\)-words (i. e.right infinite words) over \(\Sigma\). We use the terms word for both, finite words and \(\omega\)-words and a language can either be a subset of \(\Sigma^*\) or a subset of \(\Sigma^\omega\).

Regular Languages.

For a language \(L \subseteq \Sigma^*\) (of finite words), we define the (Myhill-Nerode) relation \(u \mathrel{L} v \iff (\forall x \in \Sigma^*: ux \in L \iff vx \in L)\). The classes of this relation are called the (Myhill-Nerode) classes of \(L\) and the class of \(u \in \Sigma^*\) is denoted by \(\mathscr{C}_L(u)\) or simply \(\mathscr{C}(u)\) if the language is clear from the context.⁴ A language of finite words is regular if it has finitely many classes.

Büchi Acceptors and \(\omega\)-Regular Languages.

An (edge-accepting) Büchi acceptor (BA) is a tuple \(\mathcal{B} = (Z, \Gamma, \tau, z_0, \mathcal{F})\) where \(Z\) is a finite set of states, \(\Gamma\) is an alphabet, \(\tau \subseteq Z \times \Gamma \times Z\) is a set of transitions, \(z_0 \in Z\) is the initial state and \(\mathcal{F} \subseteq \tau\) is the set of accepting transitions. In the context of transitions, we also write \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {y}; \setlength{\edgelength}{\widthof{\scriptsizea}+0.5cm} \node[base right=\edgelength of l] (r) {z}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizea} (r.mid west); \end{tikzpicture}\) for the element \((y, a, z) \in Z \times \Gamma \times Z\).

A Büchi acceptor \(\mathcal{B} = (Z, \Gamma, \tau, z_0, \mathcal{F})\) is deterministic if we have \[d_{y, a} = \left| \{ \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {y}; \setlength{\edgelength}{\widthof{\scriptsizea}+0.5cm} \node[base right=\edgelength of l] (r) {z}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizea} (r.mid west); \end{tikzpicture} \in \tau \mid z \in Z \} \right| = 1\] for all \(y \in Z\) and \(a \in \Gamma\).

A run of the Büchi acceptor \(\mathcal{B}\) is an infinite sequence

where \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {y_{i - 1}}; \setlength{\edgelength}{\widthof{\scriptsizea_i}+0.5cm} \node[base right=\edgelength of l] (r) {y_i}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizea_i} (r.mid west); \end{tikzpicture} \in \tau\) for all \(i \geq 1\). The input of this run is \(a_1 a_2 \dots \in \Gamma^\omega\). Such a run is initial if \(y_0 = z_0\) and it is accepting if \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {y_{i - 1}}; \setlength{\edgelength}{\widthof{\scriptsizea_i}+0.5cm} \node[base right=\edgelength of l] (r) {y_i}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizea_i} (r.mid west); \end{tikzpicture} \in \mathcal{F}\) for infinitely many \(i \geq 1\). The Büchi acceptor accepts an \(\omega\)-word \(\alpha \in \Gamma^\omega\) if it admits an accepting initial run whose input is \(\alpha\). The language (of \(\omega\)-words) of accepted words is the language recognized (or accepted) by the Büchi acceptor. A language is \(\omega\)-regular if it is accepted by some Büchi acceptor and, if the Büchi acceptor is deterministic, the language is deterministic \(\omega\)-regular.

Remark 1. Instead of defining the acceptance using accepting transitions we could have used the more common acceptance criterion based on accepting states (where an \(\omega\)-word \(\alpha\) is accepted if there is an initial run of the above form with input \(\alpha\) such that infinitely many of the visited states \(y_i\) are accepting). It is not difficult to see, though, that the two notions are equivalent: A state-accepting BA is tuned into an edge-accepting one by marking all transitions going into an accepting state as accepting. In the other direction, we duplicate every state and have an accepting and a non-accepting version. Now, we let accepting transitions end in the accepting one and non-accepting transitions end in the corresponding non-accepting state.

Remark 2. It is well-known that the class of deterministic \(\omega\)-regular languages is a proper subclass of all \(\omega\)-regular languages. See, for example, [30] for more information on \(\omega\)-regular languages.

Semigroup Presentations and Free Products.

A semigroup presentation is a pair \(\langle Q \mid \mathcal{R} \rangle_\mathscr{S}\) of a set of generators \(Q\) and a (possibly infinite) set of relations \(\mathcal{R} \subseteq Q^+ \times Q^+\). Typically, we will only consider finitely generated semigroups (i. e.we assume \(Q\) to be a finite set and, usually, also non-empty). If we denote by \(\mathcal{C}\) the smallest congruence \(\mathcal{C} \subseteq Q^+ \times Q^+\) with \(\mathcal{R} \subseteq \mathcal{C}\), the semigroup presented by such a presentation is \(S = Q^+ / \mathcal{C}\) formed by the congruence classes \([\cdot]_{\mathcal{C}}\) of \(\mathcal{C}\) with the (well-defined!) operation \([ u ]_{\mathcal{C}} \cdot [v]_{\mathcal{C}} = [uv]_{\mathcal{C}}\). Every semigroup generated by a finite, non-empty set \(Q\) is presented by some semigroup presentation of this form.

The free product of the semigroups \(S = \langle Q \mid \mathcal{S} \rangle_\mathscr{S}\) and \(T = \langle P \mid \mathcal{R} \rangle_\mathscr{S}\) is the semigroup \(S \star T = \langle Q \uplus P \mid \mathcal{S} \cup \mathcal{R} \rangle_\mathscr{S}\). For example, we have \(\{ p, q \}^+ = p^+ \star q^+\). Any element of \(S \star T\) can be written as a non-empty sequence of blocks \(\boldsymbol{p}_0 \boldsymbol{q}_1 \boldsymbol{p}_1 \ldots \boldsymbol{q}_k \boldsymbol{p}_k\) where \(\boldsymbol{p}_0, \boldsymbol{p}_k \in P^*\) may be empty but the other blocks \(\boldsymbol{q}_i \in Q^+\) (for \(1 \leq i \leq k\)) and \(\boldsymbol{p}_i \in P^+\) (for \(1 \leq i < k\)) may not.

Remark 1. Of course, there is also the free product of monoids (and monoid presentations). However, in this paper, we only consider free products of semigroups (in particular, we have \(\{ p, q \}^* \not\simeq p^* \star q^*\)).

0.0.0.2 \(\mathscr{S}\)-automata.

In the setting of the current paper, an automaton⁵ is a tuple \(\mathcal{T} = (Q, \Sigma, \delta)\) where \(Q\) is the finite, non-empty set of states, \(\Sigma\) is an alphabet and \(\delta \in Q \times \Sigma \times \Sigma \times Q\) is a set of transitions. In the context of transitions, we also use the graphical notations \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {p}; \setlength{\edgelength}{\widthof{\scriptsizea/b}+0.5cm} \node[base right=\edgelength of l] (r) {q}; \path[->] (l.mid east) edge node[inner sep=0pt] {\scriptsizea/b} (r.mid west); \end{tikzpicture}\) and \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {q}; \setlength{\edgelength}{\widthof{\scriptsizea/b}+0.5cm} \node[base right=\edgelength of l] (r) {p}; \path[<-] (l.mid east) edge node[inner sep=0pt] {\scriptsizea/b} (r.mid west); \end{tikzpicture}\) for the tuple \((p, a, b, q) \in Q \times \Sigma \times \Sigma \times Q\). The intuitive idea is that, if this element is contained in \(\delta\), we may read the input letter \(a\) starting in \(p\) and obtain the output letter \(b\) and end in \(q\).

A run in an automaton \(\mathcal{T} = (Q, \Sigma, \delta)\) is a sequence

with \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {p_{i - 1}}; \setlength{\edgelength}{\widthof{\scriptsizea_i/b_i}+0.5cm} \node[base right=\edgelength of l] (r) {p_i}; \path[->] (l.mid east) edge node[inner sep=0pt] {\scriptsizea_i/b_i} (r.mid west); \end{tikzpicture} \in \delta\) for all \(0 < i \leq \ell\) (where \(\ell \geq 0\)). It starts in \(p_0\), ends in \(p_\ell\), its input is \(a_1 \dots a_\ell\) and its output is \(b_1 \dots b_\ell\). We will abbreviate such a run also as \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {p_0}; \setlength{\edgelength}{\widthof{\scriptsizea_1 \dots a_\ell/b_1 \dots b_\ell}+0.5cm} \node[base right=\edgelength of l] (r) {p_\ell}; \path[->] ([yshift=-0.25mm] l.mid east) edge[path] node[above, inner sep=0pt] {\scriptsizea_1 \dots a_\ell/b_1 \dots b_\ell} ([yshift=-0.25mm] r.mid west); \end{tikzpicture}\).

An automaton \(\mathcal{T} = (Q, \Sigma, \delta)\) is a complete \(\mathscr{S}\)-automaton if we have \[d_{p, a} = \left| \{ \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {p}; \setlength{\edgelength}{\widthof{\scriptsizea/b}+0.5cm} \node[base right=\edgelength of l] (r) {q}; \path[->] (l.mid east) edge node[inner sep=0pt] {\scriptsizea/b} (r.mid west); \end{tikzpicture} \in \delta \mid b \in \Sigma, q \in Q \} \right| = 1\] for all \(p \in Q\) and \(a \in \Sigma\).⁶ It is easy to see that, in such an automaton, there is a unique run starting in \(p\) with input \(u\) for every \(p \in Q\) and \(u \in \Sigma^*\). This allows us to uniquely define \(p \circ u\) as the output and \(p \cdot u\) as the end of this run (which is often called the section or restriction of \(p\) at \(u\) in the literature). This can naturally be extended into a left action of \(Q^*\) on \(\Sigma^*\) by letting \(\varepsilon \circ u = u\) and, inductively, \(\boldsymbol{q} p \circ u = \boldsymbol{q} \circ (p \circ u)\) for \(p \in Q\) and \(\boldsymbol{q} \in Q^*\). Clearly, we have \(q_\ell \dots q_1 \circ u = q_\ell \circ \dots \circ q_1 \circ u\).

Similarly, we may also extend the notation \(p \cdot u\) into a right action of \(\Sigma^*\) on \(Q^*\), which is called the dual action, by letting \(\varepsilon \cdot u = \varepsilon\) and \[\boldsymbol{q} p \cdot u = \left[ \boldsymbol{q} \cdot (p \circ u) \right] \, (p \cdot u) \text{.}\]

For any complete \(\mathscr{S}\)-automaton\(\mathcal{T} = (Q, \Sigma, \delta)\), we define the relation \({=_\mathcal{T}} \subseteq Q^* \times Q^*\) by \[\boldsymbol{p} =_\mathcal{T} \boldsymbol{q} \iff \forall w \in \Sigma^*: \boldsymbol{p} \circ w = \boldsymbol{q} \circ w \boldsymbol{.}\] It is easy to see that \({=_\mathcal{T}}\) is a congruence. Thus, \(Q^+/{{=_\mathcal{T}}}\) is a semigroup \(\mathscr{S}(\mathcal{T})\) and we say that it is the semigroup generated by \(\mathcal{T}\). Any semigroup arising in this way is called an automaton semigroup.

In addition to \({=_\mathcal{T}}\), we will use similar notation. In particular, we will write \(\boldsymbol{q} \in_\mathcal{T} P\) for \(\boldsymbol{q} \in Q^*\) and \(P \subseteq Q^*\) if there is some \(\boldsymbol{p} \in P\) with \(\boldsymbol{q} =_\mathcal{T} \boldsymbol{p}\). For \(P \subseteq Q^+\) and \(\boldsymbol{q} \in Q^+\), writing \(\boldsymbol{q} \in_\mathcal{T} P^+\) means that the image of \(\boldsymbol{q}\) in the semigroup \(\mathscr{S}(\mathcal{T})\) is contained in the subsemigroup generated by \(P\).

Example 1 (The Adding Machine). The classical example of a complete \(\mathscr{S}\)-automaton is the adding machine:

Clearly, we have \(e \circ u = u\) for all \(u \in \{ 0, 1 \}^*\). In order to understand the action of \(q\), it is best to look at an example. We have: \[\begin{align} q \circ 000 &= 100 & q^3 \circ 000 &= q \circ 010 = 110 \\ q^2 \circ 000 &= q \circ 100 = 010 & q^4 \circ 000 &= q \circ 110 = 001 \end{align}\] More generally, if we denote the binary representation of \(n \in \mathbb{N}\) of length \(\ell\) in reverse/with the least significant bit on the left as \(\operatorname{bin}_\ell n\), we have \(q \circ \operatorname{bin}_\ell n = \operatorname{bin}_\ell (n + 1)\) for all \(n \in \mathbb{N}\) (with sufficiently large \(\ell\)). This shows \({q}^i \neq_{\mathcal{T}} q^j\) for all \(i \neq j\) (with \(i, j > 0\)). By identifying \(q^0\) with \(e\), we obtain that the semigroup generated by the adding machine is (isomorphic to) the free monogenic monoid \(q^*\).

Example 2 (Finite Monoids). Consider the finite monoid \(M = \{ e, p, q \}\) with \(e^2 = e\), \(ep = p = pe\), \(eq = q = qe\), \(pq = p = pp\) and \(qp = q = qq\) in \(M\). In particular, we have \(ps = p\) and \(qs = q\) for all \(s \in M\). Consider the complete \(\mathscr{S}\)-automaton⁷ \(\mathcal{T} = (M, M, \delta)\)

where \(M\) is both the state set and the alphabet. For a word \(w \in M^* \cup M^\omega\) and a letter \(a \in M\), we have \[e \circ aw = aw, \quad p \circ aw = pw \quad \text{and} \quad q \circ aw = qw \text{.}\] This shows that we have all the relations of \(M\) also in \(\mathscr{S}(\mathcal{T})\): \(e\) is the neutral element and, for any \(s \in M\), we have \(ps \circ aw = p \circ (s \circ a)w = pw = p \circ aw\) and, thus, \(ps =_\mathcal{T} p\) (and an analogous statement for \(q\)).

This construction generalizes to any finite monoid \(M\) (and, thus, also for any finite group): It is generated by the complete \(\mathscr{S}\)-automaton\(\mathcal{T} = (M, M, \delta)\) with \[\delta = \{ \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {m}; \setlength{\edgelength}{\widthof{\scriptsizen/mn}+0.5cm} \node[base right=\edgelength of l] (r) {e}; \path[->] (l.mid east) edge node[inner sep=0pt] {\scriptsizen/mn} (r.mid west); \end{tikzpicture} \mid m, n \in M \} \text{.}\]

Example 3 (Finite Semigroups). The previous example heavily used the neutral element of the monoid. However, any finite semigroup \(S\) (even if it is not a monoid) is generated by a complete \(\mathscr{S}\)-automaton(this is due to [6]). The construction for this first adjoins a new element \(e\) to \(S\) with \(e^2 = e\) and \(es = s = se\) for all \(s \in S\) to obtain the monoid \(S^e\). It is easy to see that \(S\) acts faithfully on \(S^e\) by left translation (see e. g.[31]), which basically shows that \((S, S^e, \delta)\) with \[\begin{align} \delta &= \{ \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {s}; \setlength{\edgelength}{\widthof{\scriptsizet/st}+0.5cm} \node[base right=\edgelength of l] (r) {s}; \path[->] (l.mid east) edge node[inner sep=0pt] {\scriptsizet/st} (r.mid west); \end{tikzpicture} \mid s \in S, t \in S^e \} \end{align}\] is a complete \(\mathscr{S}\)-automaton generating \(S\) (see [6] for a full proof).

Example 4 (Grigorchuk’s Group). A very famous automaton is the complete \(\mathscr{S}\)-automaton

whose generated semigroup is Grigorchuk’s group (which coincides also with the generated monoid and group). We will not elaborate on this further but refer the reader, for example to [2], [3] for details.

Example 5 (Running Example). We will use the following complete \(\mathscr{S}\)-automaton as a running example for demonstrating our constructions:

Union and Power Automata.

The union of two automata \(\mathcal{T}_1 = (Q_1, \Sigma_1, \delta_1)\) and \(\mathcal{T}_2 = (Q_2, \Sigma_2, \delta_2)\) is the automaton \(\mathcal{T}_1 \cup \mathcal{T}_2 = (Q_1 \cup Q_2, \Sigma_1 \cup \Sigma_2, \delta_1 \cup \delta_2)\). The most common case of a union automaton is when the automata use the same alphabet but their state sets are disjoint. In this case, the union of two complete \(\mathscr{S}\)-automata is a complete \(\mathscr{S}\)-automaton.

The composition of two automata \(\mathcal{T}_2 = (Q_2, \Sigma, \delta_2)\) and \(\mathcal{T}_1 = (Q_1, \Sigma, \delta_1)\) over the same alphabet is \(\mathcal{T}_2 \circ \mathcal{T}_1 = (Q_2 Q_1, \Sigma, \delta_2 \circ \delta_1)\) where \(Q_2 Q_1 = \{ q_2 q_1 \mid q_1 \in Q_1, q_2 \in Q_2 \}\) is the Cartesian product and \[\delta_2 \circ \delta_1 = \{ \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {p_2 p_1}; \setlength{\edgelength}{\widthof{\scriptsizea/c}+0.5cm} \node[base right=\edgelength of l] (r) {q_2 q_1}; \path[->] (l.mid east) edge node[inner sep=0pt] {\scriptsizea/c} (r.mid west); \end{tikzpicture} \mid \exists b \in \Sigma: \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {p_1}; \setlength{\edgelength}{\widthof{\scriptsizea/b}+0.5cm} \node[base right=\edgelength of l] (r) {q_1}; \path[->] (l.mid east) edge node[inner sep=0pt] {\scriptsizea/b} (r.mid west); \end{tikzpicture} \in \delta_1, \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {p_2}; \setlength{\edgelength}{\widthof{\scriptsizeb/c}+0.5cm} \node[base right=\edgelength of l] (r) {q_2}; \path[->] (l.mid east) edge node[inner sep=0pt] {\scriptsizeb/c} (r.mid west); \end{tikzpicture} \in \delta_2 \} \text{.}\] The composition of two complete \(\mathscr{S}\)-automata over the same alphabet is a complete \(\mathscr{S}\)-automaton.

The \(k\)-th power of an automaton \(\mathcal{T} = (Q, \Sigma, \delta)\) (with \(k \geq 1\)) is the \(k\)-fold composition of \(\mathcal{T}\) with itself. Any power of a complete \(\mathscr{S}\)-automaton is a complete \(\mathscr{S}\)-automaton and the action of \(\boldsymbol{p} \in Q^+\) as a state sequence over \(Q\) (with respect \(\mathcal{T}\)) is the same as the action of \(\boldsymbol{p} \in Q^{|\boldsymbol{p}|}\) as a state of \(\mathcal{T}^{|\boldsymbol{p}|}\), which makes the notation \(\boldsymbol{p} \circ u\) unambiguous. The same holds for \(\boldsymbol{p} \cdot u\) by the construction of the power automaton. The semigroup generated by the union of a complete \(\mathscr{S}\)-automaton with some of its powers is the same as the semigroup generated by the original automaton. This allows us to use the power automaton construction to make sure that any fixed state sequence acts in the same way as a single state of the automaton. For our results later on, it will be important to note here that power and union automata are computable.

For the remainder of this paper, we fix an arbitrary complete \(\mathscr{S}\)-automaton\(\mathcal{T} = (Q, \Sigma, \delta)\).

0.0.0.3 Orbits.

For a language \(R \subseteq Q^*\), the \(R\)-orbit of a word \(w \in \Sigma^* \cup \Sigma^\omega\) is \[R \circ w = \{ \boldsymbol{r} \circ w \mid \boldsymbol{r} \in R \} \text{,}\] which is a subset of \(\Sigma^{|w|}\) for \(w \in \Sigma^*\) and a subset of \(\Sigma^\omega\) for \(w \in \Sigma^\omega\). The \(Q^*\)-orbit of \(w\) is also simply called the orbit of \(w\). The orbital transducer⁸ \(\mathcal{T} \circ w\) of \(w \in \Sigma^*\) is the complete \(\mathscr{S}\)-automaton with state set \(Q^* \circ w\) and alphabet \(Q\) whose transitions are given by \[\{ \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {u}; \setlength{\edgelength}{\widthof{\scriptsizep/p \cdot u}+0.5cm} \node[base right=\edgelength of l] (r) {p \circ u}; \path[->] (l.mid east) edge node[inner sep=0pt] {\scriptsizep/p \cdot u} (r.mid west); \end{tikzpicture} \mid u \in Q^* \circ w, p \in Q \} \text{.}\] We designate \(w\) as the root of \(\mathcal{T} \circ w\). Since \(\boldsymbol{p} \circ u\) is a left action, it is natural to write the runs of \(\mathcal{T} \circ w\) from right to left. Thus, we write

to indicate that \(\mathcal{T} \circ w\) contains a run from \(u_0\) to \(u_\ell\) with input \(p_1 \dots p_\ell\) and output \(q_1 \dots q_\ell\) (where \(p_1, \dots, p_\ell, q_1, \dots, q_\ell \in Q\)). Notice that, for \(p_\ell \dots p_1 = \boldsymbol{p}\) and \(q_\ell \dots q_1 = \boldsymbol{q}\), such a run means that we have \(u_\ell = \boldsymbol{p} \circ u_0 = p_\ell \dots p_1 \circ u_0\) and \(q_\ell \dots q_1 = \boldsymbol{q} = \boldsymbol{p} \cdot u_0 = p_\ell \dots p_1 \cdot u_0\), which justifies this somewhat reverse notation. As a short-hand notation, we also write \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {u_\ell}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{p}/\boldsymbol{q}}+0.5cm} \node[base right=\edgelength of l] (r) {u_0}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{p}/\boldsymbol{q}} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) for the same run. Often, we will not be interested in the input of the run and simply write \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v}; \setlength{\edgelength}{\widthof{\scriptsize/\boldsymbol{q}}+0.5cm} \node[base right=\edgelength of l] (r) {u}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize/\boldsymbol{q}} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) to indicate that there is a run \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{p}/\boldsymbol{q}}+0.5cm} \node[base right=\edgelength of l] (r) {u}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{p}/\boldsymbol{q}} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) for some \(\boldsymbol{p} \in Q^+\).

Figure 8: Orbital transducers for the automaton from the running example.

Example 6 (Running Example). Recall \(\mathcal{T}\) from 5. The orbital transducers \(\mathcal{T} \circ 0\) (which is equal to \(\mathcal{T} \circ 1\), \(\mathcal{T} \circ 2\) and the dual automaton) and the orbital transducer \(\mathcal{T} \circ 22\) are shown in 8. Observe that, reading \(22\) from state \(p\) yields output \(12\) and we end in state \(e\); this yields the edge \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {22}; \setlength{\edgelength}{\widthof{\scriptsizep/e}+0.5cm} \node[base right=\edgelength of l] (r) {12}; \path[->] (l.mid east) edge node[inner sep=0pt] {\scriptsizep/e} (r.mid west); \end{tikzpicture}\) in \(\mathcal{T} \circ 22\). If we read \(10\) in state \(p\), we obtain the output \(02\) and return to state \(p\) in the end; this yields the edge \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {10}; \setlength{\edgelength}{\widthof{\scriptsizep/p}+0.5cm} \node[base right=\edgelength of l] (r) {02}; \path[->] (l.mid east) edge node[inner sep=0pt] {\scriptsizep/p} (r.mid west); \end{tikzpicture}\) in \(\mathcal{T} \circ 22\). All other edges arise in the same manner.

Figure 9: Orbital transducers for the adding machine.

Example 7 (Orbital Transducers of the Adding Machine). Recall the adding machine \(\mathcal{T}\) from 1. Also recall the notation \(\operatorname{bin}_\ell n\) from there. The orbital transducers \(\mathcal{T} \circ 0\), \(\mathcal{T} \circ 00\) and a general depiction of \(\mathcal{T} \circ 0^\ell\) may be found in 9. The orbital transducer \(\mathcal{T} \circ 0\) coincides with what is commonly referred to as the dual automaton of \(\mathcal{T}\). Observe that, if we start reading \(1^\ell\) in \(q\), we output \(0^\ell\) while remaining in \(q\) the entire time. This yields the \(q/q\)-edge from \(1^\ell\) to \(0^\ell\). If we read any other word (i. e.one that contains at least one \(0\)), we end in the state \(e\). This is the reason why any other \(q\)-edge has output \(e\).

Figure 10: The orbital transducer \mathcal{T} \circ 00 for Grigorchuk’s group. — Figure 10: The orbital transducer \(\mathcal{T} \circ 00\) for Grigorchuk’s group.

Example 8 (Orbital Transducers for Grigorchuk’s Group). Recall \(\mathcal{T}\) generating Grigorchuk’s group from 4. The orbital transducer \(\mathcal{T} \circ 00\) is drawn in 10

0.0.0.4 The Product \(\mathcal{T} \circ w \times R\).

For some language \(R \subseteq Q^*\), the product \(\mathcal{T} \circ w \times R\) is a possibly infinite \(\mathscr{S}\)-automaton over the alphabet \(Q\). Its states are of the form \((u, C)\) where \(u \in Q^* \circ w\) and \(C\) is a class of \(R\) and we have a transition \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(v, \mathscr{C}(\boldsymbol{r}p))}; \setlength{\edgelength}{\widthof{\scriptsizep/q}+0.5cm} \node[base right=\edgelength of l] (r) {(u, \mathscr{C}(\boldsymbol{r}))}; \path[<-] (l.mid east) edge node[inner sep=0pt] {\scriptsizep/q} (r.mid west); \end{tikzpicture}\) if we have a transition \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v}; \setlength{\edgelength}{\widthof{\scriptsizep/q}+0.5cm} \node[base right=\edgelength of l] (r) {u}; \path[<-] (l.mid east) edge node[inner sep=0pt] {\scriptsizep/q} (r.mid west); \end{tikzpicture}\) in \(\mathcal{T} \circ w\). We restrict \(\mathcal{T} \circ w \times R\) to the part reachable from its root \((w, \mathscr{C}(\varepsilon))\). We use the same conventions to write transitions and runs in \(\mathcal{T} \circ w \times R\) as in \(\mathcal{T} \circ w\). In particular, we omit the input label if we are not interested in it.

Note that we have a run \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(u, C)}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{p}/\boldsymbol{q}}+0.5cm} \node[base right=\edgelength of l] (r) {(w, \mathscr{C}(\varepsilon))}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{p}/\boldsymbol{q}} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) in \(\mathcal{T} \circ w \times R\) if and only if we have \(u = \boldsymbol{p} \circ w\), \(\boldsymbol{q} = \boldsymbol{p} \cdot w\) and \(C = \mathscr{C}(\boldsymbol{p})\). Furthermore, \(\mathcal{T} \circ w \times R\) is finite if \(R\) is regular.

0.0.0.5 Expandability.

A finite word \(w \in \Sigma^*\) is \(R\)-expandable for \(R \subseteq Q^*\) if there is some \(x \in \Sigma^*\) with \(|R \circ w| < |R \circ wx|\). In this case, \(x\) is said to \(R\)-expand \(w\).

Remark 2. The notion of expandability was introduced in [18] where it was shown that it is decidable whether a given word is expandable with respect to the action of a given \(\mathscr{S}\)-automaton and that there is a bound on the length of the expanding suffix.

Generalized Activity We say that a subset \(S \subseteq Q\) of states of \(\mathcal{T}\) is closed (under the dual action) if we have \[S \cdot \Sigma^* = \{ s \cdot u \mid s \in S, u \in \Sigma^* \} \subseteq S \text{.}\] For such a closed subset \(S\), we may consider the restriction \(\delta|_S\) of \(\delta\) into a relation \(\delta|_S \subseteq S \times \Sigma \times \Sigma \times S\), which yields a complete \(\mathscr{S}\)-automaton\(\mathcal{T}|_S = (S, \Sigma, \delta|_S)\). Notice that the action \(\boldsymbol{s} \circ u\) of some \(\boldsymbol{s} \in S^+\) is the same when we consider it with respect to \(\mathcal{T}\) or with respect to \(\mathcal{T}|_S\). This justifies that we define the semigroup generated by \(\mathcal{T}|_S\) as \(S^+/{=_{\mathcal{T}}}\) (which is the subsemigroup generated by \(S\) in the semigroup generated by \(\mathcal{T}\)).

We are mostly interested in the case that this generated semigroup is finite. Therefore, we fix an arbitrary closed subset \(S \subseteq Q\) such that the generated semigroup \(S^+/{=_{\mathcal{T}}}\) is finite.

Remark 3. Only considering subsets of states here is not a real restriction: If we have that \(S \subseteq Q^+\) generates a finite subsemigroup in \(\mathscr{S}(\mathcal{T})\), we may assume that \(S\) is finite (by choosing one representative for each of the finitely many elements in the subsemigroup). As briefly mentioned above, we may then pass to a union of suitable power automata of \(\mathcal{T}\), which allows us to finally assume \(S \subseteq Q\).

For a state sequence \(\boldsymbol{p} \in Q^+\), we define its set of \(S\)-active words of length \(n \in \mathbb{N}\) as \[A_{\boldsymbol{p}}(n) = \{ v \mid \exists u \in \Sigma^n: \boldsymbol{p} \circ u = v, \boldsymbol{p} \cdot u \not\in_\mathcal{T} S^+ \}\] and the set of \(S\)-active words as \(A_{\boldsymbol{p}} = \bigcup_{n \geq 0} A_{\boldsymbol{p}}(n)\). The \(S\)-activity of \(\boldsymbol{p}\) is the growth of the function \(n \mapsto \alpha_{\boldsymbol{p}}(n) = |A_{\boldsymbol{p}}(n)|\).

Please note that, instead of considering \(\boldsymbol{p}\) as a state sequence over \(Q\), we may also consider it as a single state of \(\mathcal{T}^{|\boldsymbol{p}|}\) and obtain the same sets of active words.

With regard to orbital transducers, a word \(v \in \Sigma^n\) is \(S\)-active (i. e.in \(A_{\boldsymbol{p}}(n)\)) if and only if there is some \(u \in \Sigma^n\) with a run \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{p}/\boldsymbol{q}}+0.5cm} \node[base right=\edgelength of l] (r) {u}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{p}/\boldsymbol{q}} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) in \(\mathcal{T} \circ u\) such that \(\boldsymbol{q} \not\in_{\mathcal{T}} S^+\). In other words, we collect all words with an in-going run in any orbital transducer \(\mathcal{T} \circ w\) whose output is not labeled by an element contained in the subsemigroup generated by \(S\).

Remark 3. Our notion of \(S\)-activity generalizes the activity notion for automaton monoids introduced in [11]. An automaton monoid is an automaton semigroup generated by a complete \(\mathscr{S}\)-automaton\(\mathcal{T} = (Q, \Sigma, \delta)\) containing an identity state \(e \in Q\) (i. e.we have \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {e}; \setlength{\edgelength}{\widthof{\scriptsizea/a}+0.5cm} \node[base right=\edgelength of l] (r) {e}; \path[->] (l.mid east) edge node[inner sep=0pt] {\scriptsizea/a} (r.mid west); \end{tikzpicture} \in \delta\) for all \(a \in \Sigma\)).⁹ For such an automaton, the set \(\{ e \}\) is clearly closed and its generated subsemigroup is the trivial monoid (and, thus, in particular finite). The activity defined in [11] is then precisely the \(\{ e \}\)-activity in our terminology. In fact, [11] already contains an extension of the activity notion where the set \(S\) is given by the NoCyWEx part of the generating automaton (which always generates a finite subsemigroup).

The authors of [11] use NoCyWEx as an acronym for “no cycles with exit”. We do not strictly need the NoCyWEx notion for (sub)automata for our results but we will compare our generalization to it. Therefore, it seems worthwhile to give a definition here. We invite the interested reader to refer to [11] for more details and references. An automaton (or subautomaton over the same alphabet) is called NoCyWEx if, for every state \(q \in Q\) on a cycle, all transitions starting in \(q\) lead to the same state, i. e.\(\{ q \cdot a \mid a \in \Sigma \}\) contains precisely one element for all \(q \in Q\) that lie on a cycle (which are those \(q \in Q\) with \(q \cdot w = q\) for some \(w \in \Sigma^+\)).

The activity notion for automaton monoids from [11] is, in turn, a generalization of the original activity notion for automaton groups (which are generated by invertible automata) introduced by Sidki [20]. The main difference is that, in the group case, we may use the input words to define the set of active words, i. e.we could let \[A_{\boldsymbol{p}}(n) = \{ u \in \Sigma^n \mid \boldsymbol{p} \circ u \neq_\mathcal{T} e \}\] (where \(e\) is the identity state). The straight-forward generalization of this definition to automaton monoids is not well-behaved (and we refer the reader to [11] for more details on this).

Example 9 (Running Example). Recall the automaton \(\mathcal{T}\) from 5. We let \(S = \{ e \}\) and observe that \(S^+ / {=_\mathcal{T}}\) is the trivial monoid (and, thus, in particular, finite). The word \(02\) is \(S\)-active (of length \(2\)) for the state \(p\): We have \(p \circ 10 = 02\) and, after reading \(10\) from \(p\), we end in state \(p\) again. Since we have \(p \not\in_\mathcal{T} e^+\) (as \(p \neq_\mathcal{T} e\)), this shows that \(02\) is indeed \(\{ e \}\)-active.

We may also observe that \(02\) is \(\{ e \}\)-active for \(p\) from the orbital transducer \(\mathcal{T} \circ 22\) (see 8): \(02\) has an incoming \(p/p\)-edge (from \(10\) and also from \(11\)).

On the other hand, \(11\) is not \(\{ e \}\)-active for \(p\): While there are input words (e. g.\(21\) or \(00\)) yielding \(11\) as the output when starting in \(p\) (e. g.\(p \circ 21 = 11\) and \(p \circ 00 = 11\)), we always end in state \(e\) after reading any of them from \(p\) (e. g.\(p \cdot 21, p \cdot 00 \in_\mathcal{T} e^+\)).

In fact, \(11\) is not \(\{ e \}\)-active for any state of the automaton, which we may see by observing that the orbital transducer \(\mathcal{T} \circ 22\) (from 8, which contains all words of length \(2\)) does not have any incoming transitions at \(11\) with output different to \(e\). Similarly, we may also observe that \(00\), \(01\), \(10\), \(12\) and \(22\) are also not \(\{ e \}\)-active for any state of the automaton.

Our generalization of the activity notion maintains many desirable properties of the original notion(s). First, it remains subadditive (compare to [11]).

Fact 4. For \(\boldsymbol{p}, \boldsymbol{q} \in Q^+\), we have \(\alpha_{\boldsymbol{q} \boldsymbol{p}}(n) \leq \alpha_{\boldsymbol{q}}(n) + \alpha_{\boldsymbol{p}}(n)\) for all \(n \geq 0\).

Proof. We show \(A_{\boldsymbol{qp}}(n) \subseteq A_{\boldsymbol{q}}(n) \cup \boldsymbol{q} \circ A_{\boldsymbol{p}}(n)\) where \(\boldsymbol{q} \circ A_{\boldsymbol{p}}(n) = \{ \boldsymbol{q} \circ v \mid v \in A_{\boldsymbol{p}}(n) \}\) and, thus, \(| \boldsymbol{q} \circ A_{\boldsymbol{p}}(n) | \leq | A_{\boldsymbol{p}}(n) | = \alpha_{\boldsymbol{p}}(n)\).

Suppose we have \(w \in A_{\boldsymbol{qp}}(n)\). By definition, there is some \(u \in \Sigma^n\) with \(\boldsymbol{qp} \circ u = w\) and \(\boldsymbol{qp} \not\in_{\mathcal{T}} S^+\). We cannot have \(\boldsymbol{p} \cdot u \in_{\mathcal{T}} S^+\) and \(\boldsymbol{q} \cdot v \in_{\mathcal{T}} S^+\) for \(v = \boldsymbol{p} \circ u\) since this would imply \(\boldsymbol{qp} \cdot u = (\boldsymbol{q} \cdot v) (\boldsymbol{p} \cdot u) \in_{\mathcal{T}} S^+\). Thus, we have \(\boldsymbol{p} \cdot u \not\in_{\mathcal{T}} S^+\) or \(\boldsymbol{q} \cdot v \not\in_{\mathcal{T}} S^+\). In the first case, we have \(v = \boldsymbol{p} \circ u \in A_{\boldsymbol{p}}(n)\) and, thus, \(w = \boldsymbol{q} \circ v \in \boldsymbol{q} \circ A_{\boldsymbol{p}}(n)\). In the second case, we have \(w \in A_{\boldsymbol{q}}(n)\) directly by definition. ◻

Next, the set of \(S\)-active words is regular.

Fact 5. The set of \(S\)-active words \(A_{\boldsymbol{p}}\) is regular for all state sequences \(\boldsymbol{p} \in Q^+\).

Proof. We will describe how to obtain (in fact, compute) a non-deterministic finite acceptor (NFA) recognizing \(A_{\boldsymbol{p}}\). We refer the reader to [11], [21] or a standard textbook on formal language theory (such as [32]) for proper definitions of NFAs and how they relate to our definition of regular languages.

Recall that we may consider \(\boldsymbol{p}\) as a single state of the power automaton \(\mathcal{T}^{|\boldsymbol{p}|}\) (and still obtain the same set of active words). By replacing \(\mathcal{T}\) with \(\mathcal{T}^{|\boldsymbol{p}|}\), we may, thus, without loss of generality assume \(\boldsymbol{p} = p \in Q\). We mark all states \(q\) in \(\mathcal{T}\) with \(q \not\in_{\mathcal{T}} S^+\) as accepting and \(p\) as initial. Afterwards, we drop the inputs from all transitions and obtain an NFA. By construction, we obtain that the words accepted by this are precisely the \(S\)-active ones. ◻

The growth of a language \(L \subseteq \Sigma^*\) is the growth of the function \(n \mapsto \gamma_L(n) = |L \cap \Sigma^n|\). Thus, by definition, \(\alpha_{\boldsymbol{p}}\) is the growth function of the language of \(S\)-active words. It is well-known that a regular language either grows polynomially of exponentially (see e. g.[21]). Here, exponential growth means that there is some \(r > 1\) such that \(\gamma_L(n) \geq r^n\) for infinitely many \(n\) (while, of course, \(\gamma_L(n) \leq |\Sigma|^n\) for all \(n\)) and polynomial growth of degree exactly \(d \geq 0\) means that there is some \(d\) and polynomials \(p(n)\) and \(q(n)\) of degree \(d\) with \(\gamma_L(n) \geq p(n)\) for infinitely many \(n\) and \(\gamma_L(n) \leq q(n)\) for all \(n\). The special case of polynomial growth of degree \(-\infty\) occurs if \(\gamma_L\) eventually becomes the constant zero function (which happens if and only if \(L\) is a finite language). We say that a language has polynomial growth of degree at most \(d\) if it has polynomial growth of degree exactly \(d'\) for some \(d' \leq d\).

Now, a language has polynomial growth if it has polynomial growth of degree \(d\) for some \(d \in \{ -\infty \} \cup \mathbb{N}\). Since the \(S\)-activity of the state sequence \(\boldsymbol{p}\) is the growth of its language of \(S\)-active words, this immediately induces definitions of polynomial or exponential \(S\)-activity and we obtain:

Fact 6. The \(S\)-activity of a state sequence is either polynomial or exponential.

One important special case of polynomial \(S\)-activity occurs when there is a constant bounding \(\alpha_{\boldsymbol{p}}(n)\) for all \(n\). In this case, the \(S\)-activity of \(\boldsymbol{p}\) is called bounded and this is what we will mostly be concerned with in this paper. If \(\alpha_{\boldsymbol{p}}(n)\) eventually becomes the constant zero function (i. e.if the language of \(S\)-active words is finite), we say that \(\boldsymbol{p}\) is \(S\)-finitary.

Extension to Automata.

The subadditivity stated in 4 ensure that, if we take two state sequences \(\boldsymbol{q}\) and \(\boldsymbol{p}\) of polynomial activity (or bounded activity), then their concatenation \(\boldsymbol{q} \boldsymbol{p}\) remains to have polynomial (bounded) activity. This justifies defining the activity of the entire \(\mathscr{S}\)-automaton\(\mathcal{T} = (Q, \Sigma, \delta)\) as the activity of the states. More precisely, we define the set of \(S\)-active words of length \(n\) for the whole automaton as \[A(n) = \bigcup_{q \in Q} A_q(n)\] and the \(S\)-activity of \(\mathcal{T}\) as the growth of the function \(n \mapsto \alpha(n) = |A(n)|\). Clearly, we have \(\alpha_p(n) \leq \alpha(n) \leq \sum_{q \in Q} \alpha_q(n)\) for all \(n \in \mathbb{N}\) and \(p \in Q\). Thus, and by 4, we also have that the \(S\)-activity of any state sequence \(\boldsymbol{p} \in Q^+\) is polynomial with degree at most \(d\) if the \(S\)-activity of \(\mathcal{T}\) is.

As with state sequences, we say that \(\mathcal{T}\) is of bounded \(S\)-activity if there is some constant bounding the \(S\)-activity of \(\mathcal{T}\) and we say that \(\mathcal{T}\) is \(S\)-finitary if all states of \(\mathcal{T}\) are.

Example 10 (Running Example). Again, let us consider the automaton from 5. We can fully describe all the \(\{ e \}\)-active words for all states of the automaton. Using standard notation from formal language theory, we have: \[\begin{align} A_p(n) &= \begin{cases} \{ \left( 02 \right)^{\frac{n}{2}} \} & n \text{ even}\\ \left( 02 \right)^{\frac{n}{2} - 1} \{ 0, 1 \} & n \text{ odd} \end{cases}\\ A_q(n) &= \begin{cases} \{ (20)^\frac{n}{2}, (20)^{\frac{n}{2} - 1}21 \} & n \text{ even}\\ \{ (20)^\frac{n - 1}{2}2 \} & n \text{ odd} \end{cases}\\ A_r(n) &= \emptyset \intertext{Accordingly, we have for the entire automaton} A(n) &= \begin{cases} \{ (02)^\frac{n}{2}, (20)^\frac{n}{2}, (20)^{\frac{n}{2} - 1}21 \} & n \text{ even}\\ (02)^\frac{n - 1}{2}\{ 0, 1 \} \cup \{ (20)^\frac{n - 1}{2} 2 \} & n \text{ odd} \end{cases} \end{align}\] and \(|A(n)| \leq 3\) for all \(n \geq 0\). This shows that the automaton is of bounded \(\{ e \}\)-activity.

Example 11. The adding machine from 1 is well known to have bounded \(\{ e \}\)-activity; the only \(\{ e \}\)-active words are those in \(0^*\). No state in the automaton from 2 has any \(\{ e \}\)-active words; it, therefore, is \(\{ e \}\)-finitary.

The construction in 3 to generate a finite semigroup \(S\) does not contain an identity state if \(S\) is not a monoid and, thus, has trivially exponential activity in the sense of [11] in that case. The generating automaton is NoCyWEx in the sense of [11] and, thus, also finitary in this sense.

However, there are also non-NoCyWEx automata generating finite semigroups. For example, the complete \(\mathscr{S}\)-automaton

with alphabet \(\{ a, \bot \}\) generates the monoid \(U_1 = \{ e, z \}\) with \(e^2 = e\) and \(z^2 = ez = ze = z\). As \(z\) is not the neutral element, this automaton has exponential activity in the sense of [11] and it has bounded activity (but is not finitary!) in the NoCyWEx-sense of [11].

We may even go further. As an example, consider the complete \(\mathscr{S}\)-automaton\(\mathcal{T} = (\{ q, e, z \}, \{ 0, 1, a, \bot \}, \delta)\)

which combines the above example (with additional \(0/0\)- and \(1/1\)-self-loops at all states that do not change the generated semigroup) with the adding machine from 1. Using an induction on \(|u|\) for \(u \in \{ 0, 1, a, \bot \}^*\) and an exhaustive calculation, one may easily see that all states commute in the generated semigroup and that we have \(qe =_{\mathcal{T}} q\), which turns \(e\) into a neutral element. Next, we have \[\begin{align} q^i \circ 0^\ell = q^i e \circ 0^\ell = q^i z \circ 0^\ell = \operatorname{bin}_\ell i \end{align}\] (for \(\ell\) sufficiently large), which shows \(q^i s \neq_{\mathcal{T}} q^j t\) for all \(i \neq j\) and \(s, t \in \{ e, z \}\). Finally, we clearly have \(q^i e \neq_{\mathcal{T}} q^i z\) for all \(i \geq 0\) and, thus, that the semigroup generated by \(\mathcal{T}\) is (isomorphic to) \(q^* \times U_1\).

The interesting part about this last example \(\mathcal{T}\) is that the automaton has exponential activity both with respect to the identity function (and even its neutral element \(e\)) as well as to its NoCyWEx part (which only contains of \(z\)). Nevertheless, it has bounded \(\{ e, z \}\)-activity (where the subsemigroup generated by \(e\) and \(z\) is isomorphic to \(U_1\)).

Figure 13: A complete \mathscr{S}-automaton with exponential activity. — Figure 13: A complete \(\mathscr{S}\)-automaton with exponential activity.

Example 12 (Exponential Activity). By slightly modifying the automaton from 5, we may obtain the automaton depicted in 13. Here, the \(\{ e \}\)-active words for the states are: \[\begin{align} A_p(n) &= \begin{cases} \left( 0 \{ 0, 2 \} \right)^\frac{n}{2} & n \text{ even}\\ \left( 0 \{ 0, 2 \} \right)^\frac{n - 1}{2} \{ 0, 1 \} & n \text{ odd} \end{cases}\\ A_q(n) &= \begin{cases} \left( \{ 0, 2 \} 0 \right)^\frac{n}{2} \cup \left( \{ 0, 2 \} 0 \right)^{\frac{n}{2} - 1} \{ 0, 2 \} 1 & n \text{ even}\\ \left( \{ 0, 2 \} 0 \right)^{\frac{n - 1}{2}} \{ 0, 2 \} & n \text{ odd} \end{cases}\\ A_r(n) &= \emptyset \end{align}\] In particular, the automaton has exponential \(\{ e \}\)-activity.

Remark 7. The isomorphism problem for automaton groups and, thus, for automaton semigroups is undecidable (this follows from [33] but, in the semigroup case, also from the direct construction in [19]). However, the (uniform) word problem is decidable (in fact, it is \(\mathrm{\small PSpace}\)-complete [28], [34], see also [21]). Thus, for any fixed finite semigroup \(T\), we may test whether there is a (closed) subset \(P\) of states whose generated subsemigroup is isomorphic to \(T\): We enumerate all elements of the subsemigroup (for example, using breath-first search in the Cayley graph) until we have found all elements or more than \(|T|\)-many elements. In the second case, the subsemigroup cannot be isormorphic to \(T\) and, in the first case, we may test the isomorphism between finite semigroups. This allows us to consider our notion of \(S\)-activity in a more abstract sense where, instead of fixing a subset of states, we fix some finite semigroup \(T\) and then try to find a closed subset \(S\) of states generating \(T\). If there is such an \(S\), we may use it to base the activity on; if there is no such \(S\), we set \(S = \emptyset\) and obtain exponential activity.

Expansion Relation Recall that we fixed some complete \(\mathscr{S}\)-automaton\(\mathcal{T} = (Q, \Sigma, \delta)\) and some closed subset \(S \subseteq Q\) such that \(S^+/{=_{\mathcal{T}}}\) is finite. Without loss of generality, we may assume that for every \(\boldsymbol{t} \in S^+\), there is exactly one \(s \in S\) with \(\boldsymbol{t} =_{\mathcal{T}} s\): since there are only finitely many equivalence classes under \(=_{\mathcal{T}}\), we may replace \(\mathcal{T}\) by a finite union of suitable powers of \(\mathcal{T}\) and then minimize the automaton to avoid multiple states with the same action.¹⁰

We write \(P = Q \setminus S\) for the states outside the closed subset and consider the free product \((S^+/{=_{\mathcal{T}}}) \star P^+ = Q^+/{\approx}\) of semigroups. In other words, two state sequences \(\boldsymbol{p}, \boldsymbol{q} \in Q^+\) are equivalent under \(\approx\) if they are the same up to reductions within the \(S^+\) blocks. To simplify our notation, we extend \(\approx\) into a relation on \(Q^*\) by letting \(\varepsilon \approx \varepsilon\) (and \(\varepsilon \not\approx \boldsymbol{p}\) for all \(\boldsymbol{p} \in Q^+\)). In this free product, we may define the normal form of some word \(\boldsymbol{p}_0 \boldsymbol{t}_1 \boldsymbol{p}_1 \ldots \boldsymbol{t}_n \boldsymbol{p}_n\) with \(\boldsymbol{p}_0, \boldsymbol{p}_n \in P^*\), \(\boldsymbol{p}_1, \dots, \boldsymbol{p}_{n - 1} \in P^+\) and \(\boldsymbol{t}_1, \dots, \boldsymbol{t}_n \in S^+\) as \(\boldsymbol{p}_0 s_1 \boldsymbol{p}_1 \dots s_n \boldsymbol{p}_n\) where \(s_i\) is the unique element \(s_i \in S\) with \(s_i =_{\mathcal{T}} \boldsymbol{t}_i\) for \(1 \leq i \leq n\).

Example 13. If our automaton \(\mathcal{T}\) contains an identity state \(e\) and we choose \(S = \{ e \}\), then taking the normal form of some \(\boldsymbol{p} \in Q^+\) is to reduce all blocks of the form \(e^n\) to a single \(e\). Accordingly, \(\boldsymbol{p} \approx \boldsymbol{q}\) holds if and only if we end up with the same word when doing this for \(\boldsymbol{p}\) and for \(\boldsymbol{q}\).

It is not difficult to see that \(Q^+/{=_{\mathcal{T}}}\), the semigroup generated by \(\mathcal{T}\), is a quotient of \(Q^+/{\approx}\):

Fact 8. We have \(\boldsymbol{p} \approx \boldsymbol{q} \implies \boldsymbol{p} =_{\mathcal{T}} \boldsymbol{q}\) for all \(\boldsymbol{p}, \boldsymbol{q} \in Q^+\).

Similarly, the action \(\boldsymbol{q} \cdot u\) is compatible with the classes of \(\approx\) since it is compatible with the classes of \(=_{\mathcal{T}}\) (i. e.the semigroup generate by \(\mathcal{T}\)):

Fact 9. We have \(\boldsymbol{p} \approx \boldsymbol{q} \implies \boldsymbol{p} \cdot u \approx \boldsymbol{q} \cdot u\) for all \(\boldsymbol{p}, \boldsymbol{q} \in Q^+\) and \(u \in \Sigma^*\).

To further simplify our notation from here on, we fix some language \(R \subseteq Q^*\) and simply say that a finite word is expandable if it is \(R\)-expandable. Similarly, we say that \(x \in \Sigma^+\) expands some \(w \in \Sigma^*\) if it \(R\)-expands it.

We now use the above free product to define a relation that will allow us to detect whether a word \(w \in \Sigma^*\) is expandable or not. The idea is basically that two state sequences \(\boldsymbol{p}\) and \(\boldsymbol{q}\) are equivalent if there are runs \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v}; \setlength{\edgelength}{\widthof{\scriptsize/\boldsymbol{p}}+0.5cm} \node[base right=\edgelength of l] (r) {w}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize/\boldsymbol{p}} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) and \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v}; \setlength{\edgelength}{\widthof{\scriptsize/\boldsymbol{q}}+0.5cm} \node[base right=\edgelength of l] (r) {w}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize/\boldsymbol{q}} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) to the same word in the orbital transducer of \(w\). However, we will do this only “up to equality in the \(S^+\) blocks” and this is where the free product comes into play. Additionally, we also have to keep track of the classes of the inputs (with respect to \(R\)).

Definition 1. For \(w \in \Sigma^*\), we define the expansion relation \(\mathcal{E}_{w} \subseteq Q^+ \times Q^+\) by \[\begin{align} \boldsymbol{p}_1 \mathrel{\mathcal{E}_{w}} \boldsymbol{p}_2 \iff \exists \boldsymbol{p}_1', \boldsymbol{p}_2' \in Q^+ \text{ with }& \boldsymbol{p}_1 \approx \boldsymbol{p}_1', \boldsymbol{p}_2 \approx \boldsymbol{p}_2' \text{ and}\\ &\text{runs } \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{r}'_1/\boldsymbol{p}_1'}+0.5cm} \node[base right=\edgelength of l] (r) {w}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{r}'_1/\boldsymbol{p}_1'} ([yshift=-0.25mm] l.mid east); \end{tikzpicture} \text{ and } \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{r}'_2/\boldsymbol{p}_2'}+0.5cm} \node[base right=\edgelength of l] (r) {w}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{r}'_2/\boldsymbol{p}_2'} ([yshift=-0.25mm] l.mid east); \end{tikzpicture} \text{ in } \mathcal{T} \circ w\\ &\text{for some } v \in Q^* \circ w \text{ and } \boldsymbol{r}'_1, \boldsymbol{r}'_2 \in R \text{.} \end{align}\]

Note that \(\mathcal{E}_w\) implicitly depends on \(R\).

Example 14 (Expansion Relation of the Adding Machine). Let \(R = Q^*\) and consider the adding machine from 1 (for \(S = \{ e \}\)). We have, for example, \(qe \mathrel{\mathcal{E}_{00}} qeqe\) since we have the runs

and

in \(\mathcal{T} \circ 00\) (see 9). In fact, this generalizes and we have \(qe \mathrel{\mathcal{E}_{0^\ell}} qeqe\) for all \(\ell > 0\). It turns out that we have \(\boldsymbol{p}_1 \mathrel{\mathcal{E}_{0^\ell}} \boldsymbol{p}_2\) whenever \(\boldsymbol{p}_1, \boldsymbol{p}_2 \in \left( e^* q e^+ \right)^*\) (see, later, in 16).

Example 15 (Expansion Relation for the Running Example). Let us also set \(R = Q^*\) for our running example from 5 (with \(S = \{ e \}\)). From 8, we obtain the runs

and

in \(\mathcal{T} \circ 22\). This shows \(re \mathrel{\mathcal{E}_{22}} pe \approx pee\). Similarly, one can also, for example, observe \(ere \mathrel{\mathcal{E}_{22}} e\).

We will show that \(\mathcal{E}_w\) can be used to test whether \(w\) is expandable:

Proposition 10. A word \(x \in \Sigma^*\) expands a word \(w \in \Sigma^*\) if and only if there are some \(\boldsymbol{p}_1, \boldsymbol{p}_2 \in Q^+\) with \(\boldsymbol{p}_1 \mathrel{\mathcal{E}_w} \boldsymbol{p}_2\) and \(\boldsymbol{p}_1 \circ x \neq \boldsymbol{p}_2 \circ x\).

Proof. Consider the surjective map \(\pi: R \circ wx \to R \circ w\) given by \(\boldsymbol{r} \circ wx \mapsto \boldsymbol{r} \circ w\). It is injective if and only if \(|R \circ wx| = |R \circ w|\) (i. e.\(x\) does not expand \(w\)).

For the first direction, suppose that it is not injective. Then, there are \(\boldsymbol{r}_1, \boldsymbol{r}_2 \in R\) with \(\boldsymbol{r}_1 \circ wx \neq \boldsymbol{r}_2 \circ wx\) but \(\boldsymbol{r}_1 \circ w = v = \boldsymbol{r}_2 \circ w\). The latter implies that there are runs \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{r}_1/\boldsymbol{p}_1}+0.5cm} \node[base right=\edgelength of l] (r) {w}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{r}_1/\boldsymbol{p}_1} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) and \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{r}_2/\boldsymbol{p}_2}+0.5cm} \node[base right=\edgelength of l] (r) {w}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{r}_2/\boldsymbol{p}_2} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) in \(\mathcal{T} \circ w\) with \(\boldsymbol{p}_1 = \boldsymbol{r}_1 \cdot w\) and \(\boldsymbol{p}_2 = \boldsymbol{r}_2 \cdot w\), which means that we have \(\boldsymbol{p}_1 \mathrel{\mathcal{E}_w} \boldsymbol{p}_2\). The former implies \(v (\boldsymbol{p}_1 \circ x) = (\boldsymbol{r}_1 \circ w) (\boldsymbol{r}_1 \cdot w \circ x) = \boldsymbol{r}_1 \circ wx \neq \boldsymbol{r}_2 \circ wx = (\boldsymbol{r}_2 \circ w) (\boldsymbol{r}_2 \cdot w \circ x) = v (\boldsymbol{p}_2 \circ x)\). Thus, we have \(\boldsymbol{p}_1 \circ x \neq \boldsymbol{p}_2 \circ x\).

For the other direction, suppose that \(\pi\) is injective and that we have \(\boldsymbol{p}_1, \boldsymbol{p}_2 \in Q^+\) with \(\boldsymbol{p}_1 \mathrel{\mathcal{E}_w} \boldsymbol{p}_2\). By definition, there are \(\boldsymbol{p}_1', \boldsymbol{p}_2'\) with \(\boldsymbol{p}_1 \approx \boldsymbol{p}_1'\), \(\boldsymbol{p}_2 \approx \boldsymbol{p}_2'\) and runs \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{r}_1'/\boldsymbol{p}_1'}+0.5cm} \node[base right=\edgelength of l] (r) {w}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{r}_1'/\boldsymbol{p}_1'} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) and \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{r}_2'/\boldsymbol{p}_2'}+0.5cm} \node[base right=\edgelength of l] (r) {w}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{r}_2'/\boldsymbol{p}_2'} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) in \(\mathcal{T} \circ w\). Thus, we have \(\boldsymbol{r}_1' \circ w = v = \boldsymbol{r}_2' \circ w\) and, since \(\pi\) is injective, also \(\boldsymbol{r}_1' \circ wx = \boldsymbol{r}_2' \circ wx\). We obtain \(v (\boldsymbol{p}_1' \circ x) = (\boldsymbol{r}_1' \circ w) (\boldsymbol{r}_1' \cdot w \circ x) = \boldsymbol{r}_1' \circ wx = \boldsymbol{r}_2' \circ wx = (\boldsymbol{r}_2' \circ w) (\boldsymbol{r}_2' \cdot w \circ x) = v (\boldsymbol{p}_2' \circ x)\), which implies \(\boldsymbol{p}_1 \circ x = \boldsymbol{p}_1' \circ x = \boldsymbol{p}_2' \circ x = \boldsymbol{p}_2 \circ x\) since we have \(\boldsymbol{p}_1 =_{\mathcal{T}} \boldsymbol{p}_1'\) and \(\boldsymbol{p}_2 =_{\mathcal{T}} \boldsymbol{p}_2'\) by 8. ◻

An immediate consequence of the last result is that expandability only depends on the expansion relation:

Proposition 11. For all \(u, v, x \in \Sigma^*\), we have \[\mathcal{E}_u = \mathcal{E}_v \implies \left( |R \circ u| < |R \circ ux| \iff |R \circ v| < |R \circ vx| \right) \text{.}\]

Proof. Let \(\mathcal{E}_u = \mathcal{E}_v\) and \(|R \circ u| < |R \circ ux|\). By 10, there are \(\boldsymbol{p}_1, \boldsymbol{p}_2 \in Q^+\) with \(\boldsymbol{p}_1 \mathrel{\mathcal{E}_u} \boldsymbol{p}_2\) and \(\boldsymbol{p}_1 \circ x \neq \boldsymbol{p}_2 \circ x\). The former is the same as \(\boldsymbol{p}_1 \mathrel{\mathcal{E}_v} \boldsymbol{p}_2\) and, from the other direction of 10, we obtain \(|R \circ v| < |R \circ vx|\). ◻

We have just seen that it suffices to know the expansion relation for a word \(w\) to answer the question whether a given \(x\) expands \(w\). Next, we will see that the expansion relation is compatible with appending a word.

Proposition 12. For all \(u, v, x \in \Sigma^*\), we have \(\mathcal{E}_u = \mathcal{E}_v \implies \mathcal{E}_{ux} = \mathcal{E}_{vx}\).

Proof. We will only show the statement for \(x = a \in \Sigma\) since the general case follows from this using an induction. Assume that we have \(\mathcal{E}_u = \mathcal{E}_v\) for some \(u, v \in \Sigma^*\). If we have \(\boldsymbol{q}_1 \mathrel{\mathcal{E}_{ua}} \boldsymbol{q}_2\) for some \(\boldsymbol{q}_1, \boldsymbol{q}_2 \in Q^+\), then there are \(\boldsymbol{q}_1', \boldsymbol{q}_2' \in Q^+\) and \(\boldsymbol{r}'_1, \boldsymbol{r}'_2 \in R\) with \(\boldsymbol{q}_1 \approx \boldsymbol{q}_1'\), \(\boldsymbol{q}_2 \approx \boldsymbol{q}_2'\) and runs \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {u'a'}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{r}'_1/\boldsymbol{q}_1'}+0.5cm} \node[base right=\edgelength of l] (r) {ua}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{r}'_1/\boldsymbol{q}_1'} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) and \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {u'a'}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{r}'_2/\boldsymbol{q}_2'}+0.5cm} \node[base right=\edgelength of l] (r) {ua}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{r}'_2/\boldsymbol{q}_2'} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) in \(\mathcal{T} \circ ua\) for some \(u' \in \Sigma^*\) and \(a' \in \Sigma\). By the construction of \(\mathcal{T} \circ ua\) this is only possible if there are \(\boldsymbol{p}_1', \boldsymbol{p}_2' \in Q^+\) with \(\boldsymbol{p}_1' \cdot a = \boldsymbol{q}_1'\), \(\boldsymbol{p}_2' \cdot a = \boldsymbol{q}_2'\), \(\boldsymbol{p}_1' \circ a = a' = \boldsymbol{p}_2' \circ a\) and runs \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {u'}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{r}'_1/\boldsymbol{p}_1'}+0.5cm} \node[base right=\edgelength of l] (r) {u}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{r}'_1/\boldsymbol{p}_1'} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) and \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {u'}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{r}'_2/\boldsymbol{p}_2'}+0.5cm} \node[base right=\edgelength of l] (r) {u}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{r}'_2/\boldsymbol{p}_2'} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) in \(\mathcal{T} \circ u\), which implies that we have \(\boldsymbol{p}'_1 \mathrel{\mathcal{E}_u} \boldsymbol{p}'_2\) and, thus, \(\boldsymbol{p}'_1 \mathrel{\mathcal{E}_v} \boldsymbol{p}'_2\).

This, in turn, implies that there are \(\boldsymbol{p}_1'', \boldsymbol{p}_2'' \in Q^+\) and \(\boldsymbol{r}''_1, \boldsymbol{r}''_2 \in R\) with \(\boldsymbol{p}_1'' \approx \boldsymbol{p}_1'\), \(\boldsymbol{p}_2'' \approx \boldsymbol{p}_2'\) and runs \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v'}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{r}''_1/\boldsymbol{p}''_1}+0.5cm} \node[base right=\edgelength of l] (r) {v}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{r}''_1/\boldsymbol{p}''_1} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) and \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v'}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{r}''_2/\boldsymbol{p}_2''}+0.5cm} \node[base right=\edgelength of l] (r) {v}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{r}''_2/\boldsymbol{p}_2''} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) in \(\mathcal{T} \circ v\) for some \(v' \in \Sigma^*\). From this follows \(\boldsymbol{p}_1' =_{\mathcal{T}} \boldsymbol{p}_1''\) and \(\boldsymbol{p}_2' =_{\mathcal{T}} \boldsymbol{p}_2''\) by 8, which, in particular, means \(a' = \boldsymbol{p}_1' \circ a = \boldsymbol{p}_1'' \circ a\) and \(a' = \boldsymbol{p}_2' \circ a = \boldsymbol{p}_2'' \circ a\). Thus, we have runs \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v'a'}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{r}_1''/\boldsymbol{q}_1''}+0.5cm} \node[base right=\edgelength of l] (r) {va}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{r}_1''/\boldsymbol{q}_1''} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) and \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v'a'}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{r}_2''/\boldsymbol{q}_2''}+0.5cm} \node[base right=\edgelength of l] (r) {va}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{r}_2''/\boldsymbol{q}_2''} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) in \(\mathcal{T} \circ va\) for \(\boldsymbol{q}_1'' = \boldsymbol{p}_1'' \cdot a\) and \(\boldsymbol{q}_2'' = \boldsymbol{p}_2'' \cdot a\). Finally, 9 yields \(\boldsymbol{q}_1'' = \boldsymbol{p}_1'' \cdot a \approx \boldsymbol{p}_1' \cdot a = \boldsymbol{q}_1' \approx \boldsymbol{q}_1\) and \(\boldsymbol{q}_2'' = \boldsymbol{p}_2'' \cdot a \approx \boldsymbol{p}_2' \cdot a = \boldsymbol{q}_2' \approx \boldsymbol{q}_2\), which shows \(\boldsymbol{q}_1 \mathrel{\mathcal{E}_{va}} \boldsymbol{q}_2\). The other direction is symmetric. ◻

Bounded Activity In this section, we will use the previous results to show that the \(\omega\)-words with infinite \(R\)-orbits form a deterministic \(\omega\)-regular language if the automaton \(\mathcal{T}\) is of bounded \(S\)-activity and \(R\) is regular. Therefore, we assume the latter from now on and that there is some constant \(K\) bounding all \(\alpha(n)\) with \(n \in \mathbb{N}\).

A Finite Acceptor for the Expansion Relation The basic idea of our approach is that we will store the expansion relation using a finite acceptor whose size is uniformly bounded. While we could use nondeterministic finite-state transducers for this, we will instead introduce a different acceptor model that more closely mimics a minimization of the orbital transducer or, in fact, the product \(\mathcal{T} \circ w \times R\).

Definition 2. A nondeterministic finite relation acceptor (NFRA) \(\mathcal{A}\) is a tuple \((Z, \Gamma, \tau, z_0, \mathcal{F})\) where \(Z\) is a set of states, \(\Gamma\) is an alphabet, \(\tau \subseteq Z \times \Gamma \times Z\) is the set of transitions, \(z_0 \in Z\) is the initial state and \(\mathcal{F} \subseteq Z \times Z\) is the acceptance relation. For a transition \((y, a, z)\), we also use the graphical notations \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {y}; \setlength{\edgelength}{\widthof{\scriptsizea}+0.5cm} \node[base right=\edgelength of l] (r) {z}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizea} (r.mid west); \end{tikzpicture}\) and \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {z}; \setlength{\edgelength}{\widthof{\scriptsizea}+0.5cm} \node[base right=\edgelength of l] (r) {y}; \path[<-] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizea} (r.mid west); \end{tikzpicture}\).

A run of the NFRA \(\mathcal{A} = (Z, \Gamma, \tau, z_0, \mathcal{F})\) on a word \(a_1 \dots a_n\) with \(a_1, \dots, a_n \in \Gamma\) is a sequence

with \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {y_{i - 1}}; \setlength{\edgelength}{\widthof{\scriptsizea_i}+0.5cm} \node[base right=\edgelength of l] (r) {y_i}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizea_i} (r.mid west); \end{tikzpicture} \in \tau\) for all \(1 \leq i \leq n\). It starts in \(y_0\) and ends in \(y_n\). It is initial if \(y_0 = z_0\). In short-hand notation, we also denote this run by \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {y_n}; \setlength{\edgelength}{\widthof{\scriptsizea_n \dots a_1}+0.5cm} \node[base right=\edgelength of l] (r) {y_0}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsizea_n \dots a_1} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\).

An NFRA \(\mathcal{A} = (Z, \Gamma, \tau, z_0, \mathcal{F})\) accepts a pair \((u, v) \in \Gamma^* \times \Gamma^*\) if it admits an initial run ending in \(z\) on \(u\) and an initial run ending in \(y\) on \(v\) with \(z \mathrel{\mathcal{F}} y\). The recognized relation for \(\mathcal{A}\) is \(\mathscr{R}(\mathcal{A}) = \{ (u, v) \in \Gamma^* \times \Gamma^* \mid \mathcal{A} \text{ accepts } (u, v) \}\).

Remark 13. For readers familiar with rational subsets of monoids (see e. g.[36]), we want to point out that \(\mathscr{R}(\mathcal{A})\) is indeed a rational relation (in the sense that it is a rational subset of the monoid \(\Gamma^* \times \Gamma^*\)). This may be seen from observing that any NFRA \(\mathcal{A} = (Z, \Gamma, \tau, z_0, \mathcal{F})\) may be turned into a (more traditional) non-deterministic, finite-state (spelling) \(\Gamma^* \times \Gamma^*\)-acceptor (again, see e. g.[36] for more information on \(M\)-automata or, as we call them here, \(M\)-acceptors). The idea is to take \(Z \times Z\) as the state set, \((z_0, z_0)\) as the initial state, \(\mathcal{F}\) as the set of final states and add the transitions \[\begin{align} &\{ \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(x, y)}; \setlength{\edgelength}{\widthof{\scriptsize(a, \varepsilon)}+0.5cm} \node[base right=\edgelength of l] (r) {(x', y)}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsize(a, \varepsilon)} (r.mid west); \end{tikzpicture} \mid \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {x}; \setlength{\edgelength}{\widthof{\scriptsizea}+0.5cm} \node[base right=\edgelength of l] (r) {x'}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizea} (r.mid west); \end{tikzpicture} \in \tau, y \in Z \}\\ {}\cup{}& \{ \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(x, y)}; \setlength{\edgelength}{\widthof{\scriptsize(\varepsilon, a)}+0.5cm} \node[base right=\edgelength of l] (r) {(x, y')}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsize(\varepsilon, a)} (r.mid west); \end{tikzpicture} \mid \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {y}; \setlength{\edgelength}{\widthof{\scriptsizea}+0.5cm} \node[base right=\edgelength of l] (r) {y'}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizea} (r.mid west); \end{tikzpicture} \in \tau, x \in Z \} \text{.} \end{align}\] It is now a routine matter to check that the NFRA \(\mathcal{A}\) accepts a pair \((u, v)\) if and only if there is an initial run ending in a final state in the thus constructed acceptor where the concatenation of the first components of the transitions on that run is exactly \(u\) and the concatenation of the second components is exactly \(v\).

We will describe an NFRA that recognizes the expansion relation. However, before we do this in full technical detail, we first describe the general idea.

Idea of the construction.

To explain the construction, it is helpful to first consider the special case where \(R = Q^*\) and \(S=\{ e \}\) for an identity state \(e\). For this choice, there is only one class of \(R\) and we de not need to keep track of this information. In order to simply things further, we also re-define \(\boldsymbol{p} \approx \boldsymbol{q}\) (for \(\boldsymbol{p}, \boldsymbol{q} \in Q^*\)) for this special case for now: we let \(\boldsymbol{p} \approx \boldsymbol{q}\) if \(\boldsymbol{p}\) and \(\boldsymbol{q}\) are the same word up to removing all occurrences of the identity state \(e\).¹¹

Suppose we want to encode the expansion relation \(\mathcal{E}_w\) for some \(w \in \Sigma^*\). We will keep track of whether there is a path \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v}; \setlength{\edgelength}{\widthof{\scriptsize/\boldsymbol{q}}+0.5cm} \node[base right=\edgelength of l] (r) {w}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize/\boldsymbol{q}} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) in the orbital graph \(\mathcal{T} \circ w\) for some \(v \in \Sigma^*\) and \(\boldsymbol{q} \in Q^*\). The main idea is that we may factorize \(\boldsymbol{q} = \boldsymbol{r}_{\ell} q_\ell \cdots \boldsymbol{r}_1 q_1 \boldsymbol{r}_0\) for \(\boldsymbol{r}_0, \dots, \boldsymbol{r}_\ell \in \{ e \}^*\) and \(q_1, \dots, q_\ell \in Q\). Consider a run

in \(\mathcal{T} \circ w\). By definition, the word \(w_i\) is active for the state \(q_i\) (for \(1 \leq i \leq \ell\)) and the number of such active words is bounded by a constant \(K\). The main idea is now that, since the \(\boldsymbol{r}_i \in \{ e \}^*\) will not contribute to expanding the orbit, we may compress this run into

Formally, we use the active words \(u\) of length \(|w|\) and \(w\) as the states of the NFRA and define \[\mathscr{W}(u) = \{ v \mid \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v}; \setlength{\edgelength}{\widthof{\scriptsize/\boldsymbol{r}}+0.5cm} \node[base right=\edgelength of l] (r) {u}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize/\boldsymbol{r}} ([yshift=-0.25mm] l.mid east); \end{tikzpicture} \text{ for some } \boldsymbol{r} \in \{ e \}^* \} \text{.}\] We then have a transition \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {u'}; \setlength{\edgelength}{\widthof{\scriptsizeq}+0.5cm} \node[base right=\edgelength of l] (r) {u}; \path[<-] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizeq} (r.mid west); \end{tikzpicture}\) (for \(q \in Q\)) if there is some \(v \in \mathscr{W}(u)\) with \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {u'}; \setlength{\edgelength}{\widthof{\scriptsize/q}+0.5cm} \node[base right=\edgelength of l] (r) {v}; \path[<-] (l.mid east) edge node[inner sep=0pt] {\scriptsize/q} (r.mid west); \end{tikzpicture}\). By construction, we now have a run \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{q}}+0.5cm} \node[base right=\edgelength of l] (r) {w}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{q}} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) in this NFRA if and only if there is a run from \(w\) to \(v\) in \(\mathcal{T} \circ w\) whose output is \(\approx\)-equivalent to \(\boldsymbol{q}\). We can extend this run to any \(w' \in \mathscr{W}(v)\) without changing the class of the output (with respect to \(\approx\)). Thus, we have \(\boldsymbol{p} \mathrel\mathcal{E}_w \boldsymbol{q}\) if and only if there are runs \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{p}}+0.5cm} \node[base right=\edgelength of l] (r) {w}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{p}} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) and \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v'}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{q}}+0.5cm} \node[base right=\edgelength of l] (r) {w}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{q}} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) and some \(w' \in \mathscr{W}(v) \cap \mathscr{W}(v')\). We, therefore, use \(v \mathrel\mathcal{F} v'\) if and only if \(\mathscr{W}(v) \cap \mathscr{W}(v') \neq \emptyset\) as the acceptance relation of the NFRA.

This way, we have defined an NFRA with at most \(K\) states for the expansion relation \(\mathcal{E}_w\). For more general \(R\), we also have to keep track of the input but only up to its class (with respect to \(R\)) and, for more general \(S\), we cannot simply remove all \(e\) states but need to keep track of the image in \(S\). This makes the actual construction more technical.

Back to the General Case.

We now return to the general case and proceed by describing the NFRA \(\mathcal{A}_w\) that recognizes \(\mathcal{E}_w\) for some word \(w \in \Sigma^*\), which we fix for the rest of this subsection to simplify our notation. Additionally, we write \(A = A(|w|)\) for the set of \(S\)-active words of length \(|w|\). Recall that we have \(|A| \leq K\) and write \(P\) for \(P = Q \setminus S\).

Definition 3. Let \[\begin{align} Z ={}&\{ (u, \varepsilon, C, C) \mid u \in A \cup \{ w \}, C \text{ class of } R \} \cup{}\\ & \{ (u, s, C, D) \mid u \in A \cup \{ w \}, s \in S, C \text{ and } D \text{ classes of } R \} \text{.} \end{align}\] For every \(\boldsymbol{t} \in S^+\), \(u \in A \cup \{ w \}\) and every pair \(C, D\) of classes of \(R\), there is exactly one element \((u, s, C, D)\) in \(Z\) with \(\boldsymbol{t} =_{\mathcal{T}} s\). For convenience, we write \((u, \boldsymbol{t}, C, D)\) for this unique element.

Define¹² \[\begin{align} \mathscr{W}: Z &\to \mathcal{P}(Q^* \circ w) \\ (u, \varepsilon, C, C) &\mapsto \{ u \}\\ (u, s, C, D) &\mapsto \{ u' \mid \exists \boldsymbol{t} \in S^+: s =_{\mathcal{T}} \boldsymbol{t}, \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(u', D)}; \setlength{\edgelength}{\widthof{\scriptsize/\boldsymbol{t}}+0.5cm} \node[base right=\edgelength of l] (r) {(u, C)}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize/\boldsymbol{t}} ([yshift=-0.25mm] l.mid east); \end{tikzpicture} \text{ in } \mathcal{T} \circ w \times R \} \text{ for } s \in S \text{.} \end{align}\] and let \(\mathcal{A}_w\) denote the NFRA with states \(Z\), alphabet \(Q\), transitions \[\begin{align} & \{ \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(u, \varepsilon, C, C)}; \setlength{\edgelength}{\widthof{\scriptsizes}+0.5cm} \node[base right=\edgelength of l] (r) {(u, s, C, D)}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizes} (r.mid west); \end{tikzpicture} \mid \begin{aligned}[t] &u \in A \cup \{ w \}, C, D \text{ classes of } R, s \in S \} \end{aligned}\\ {}\cup{}& \{ \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(u, s, C, D)}; \setlength{\edgelength}{\widthof{\scriptsizet}+0.5cm} \node[base right=\edgelength of l] (r) {(u, st, C, D)}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizet} (r.mid west); \end{tikzpicture} \mid \begin{align}[t] &u \in A \cup \{ w \}, C, D \text{ classes of } R, s, t \in S \} \end{align}\\ {}\cup{}& \{ \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(u, \varepsilon, C, C)}; \setlength{\edgelength}{\widthof{\scriptsizep}+0.5cm} \node[base right=\edgelength of l] (r) {(v, \varepsilon, E, E)}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizep} (r.mid west); \end{tikzpicture} \mid \begin{align}[t] &u \in A \cup \{ w \}, C \text{ class of } R,\\ & \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(v, E)}; \setlength{\edgelength}{\widthof{\scriptsize/p}+0.5cm} \node[base right=\edgelength of l] (r) {(u, C)}; \path[<-] (l.mid east) edge node[inner sep=0pt] {\scriptsize/p} (r.mid west); \end{tikzpicture} \text{ in } \mathcal{T} \circ w \times R\\ &\text{for } p \in P \text{ and some class E of R} \} \end{align}\\ {}\cup{}& \{ \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(u, s, C, D)}; \setlength{\edgelength}{\widthof{\scriptsizep}+0.5cm} \node[base right=\edgelength of l] (r) {(v, \varepsilon, E, E)}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizep} (r.mid west); \end{tikzpicture} \mid \begin{aligned}[t] &u, v \in A \cup \{ w \}, C, D \text{ classes of } R, s \in S,\\ &\exists u' \in \mathscr{W}(u, s, C, D) \text{ with }\\ & \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(v, E)}; \setlength{\edgelength}{\widthof{\scriptsize/p}+0.5cm} \node[base right=\edgelength of l] (r) {(u', D)}; \path[<-] (l.mid east) edge node[inner sep=0pt] {\scriptsize/p} (r.mid west); \end{tikzpicture} \text{ in } \mathcal{T} \circ w \times R\\ &\text{for } p \in P \text{ and some class E of R} \} \text{,} \end{aligned} \end{align}\] initial state \((w, \varepsilon, \mathscr{C}(\varepsilon), \mathscr{C}(\varepsilon))\) and the accepting relation \(\mathcal{F} \subseteq Z \times Z\) given by \[(u, s, C, D) \mathrel{\mathcal{F}} (v, t, E, F) \iff D, F \subseteq R, \mathscr{W}(u, s, C, D) \cap \mathscr{W}(v, t, E, F) \neq \emptyset \text{.}\]

Remark 14. We may define this acceptor for any language \(R \subseteq Q^+\) but it only remains finite if \(R\) has finitely many classes (i. e.if \(R\) is regular). The size of the state set \(Z\) of \(\mathcal{A}_w\) is then \((|A \cup \{ w \}|)(1 \cdot N + |S| \cdot N^2) \leq (K + 1)N(|S|N + 1)\) where \(N\) is the number of classes of \(R\). Thus, the size of \(\mathcal{A}_w\) is not only finite but uniformly bounded. Furthermore, note that \(\mathcal{A}_w\) can clearly be computed from \(w\), \(\mathcal{T}\), \(R\) and \(S\).

Example 16 (NFRA for the Expansion Relation of the Adding Machine). The NFRA \(\mathcal{A}_w\) we obtain for \(w = 0^\ell\) (where \(\ell > 0\)) for the adding machine from 1 (with \(R = Q^*\) and \(S = \{ e \}\)) is very simple. We have \(A = \{ 0^\ell \}\) and, since we chose \(R = Q^*\), only a single class \(C\) of \(R\). It, therefore, makes sense to simply write \((u)\) for the state \((u, \varepsilon, C, C)\) and \((u, e)\) for the state \((u, e, C, C)\); in fact, we only have such states for \(u = w = 0^\ell\). We may depict \(\mathcal{A}_w\) in the usual way of depicting automata as:

We have \(\mathscr{W}(0^\ell) = \{ 0^\ell \}\) and \(\mathscr{W}(0^\ell, e) = \{ 0, 1 \}^\ell\) (since we may reach any word \(v \in \{ 0, 1 \}^\ell\) by a path \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v}; \setlength{\edgelength}{\widthof{\scriptsize/e^i}+0.5cm} \node[base right=\edgelength of l] (r) {0^\ell}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize/e^i} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) for some \(i\); compare to 9). Since \(\mathcal{W}(0^\ell) \cap \mathcal{W}(0^\ell, e) = \{ 0^\ell \} \neq \emptyset\), we have that all pairs of states \(\{ 0^\ell, (0^\ell, e) \}^2\) are in \(\mathcal{F}\). We will show in 15 that \(\mathcal{A}_w\) recognizes \(\mathcal{E}_w\) and, thus, obtain that \(\boldsymbol{p}_1 \mathrel{\mathcal{E}_w} \boldsymbol{p}_2\) whenever \(\boldsymbol{p}_1\) and \(\boldsymbol{p}_2\) can both be read from \(0^\ell\) in the above NFRA. This is the case if and only if \(\boldsymbol{p}_1, \boldsymbol{p}_2 \in \left( e^* q e^+ \right)^*\) (as claimed in 14).

Example 17 (NFRA for the Running Example). Recall our running example from 5 and (continue to) let \(S = \{ e \}\), \(R = Q^*\) and \(w = 22\). Since we again only have a single class \(C\) of \(R\), we continue to simply write \(u\) for the state \((u, \varepsilon, C, C)\) and \((u, e)\) for \((u, e, C, C)\). The active words are already marked in the orbital transducer \(\mathcal{T} \circ 22\) from 8. We have \(\{ w \} \cup A = \{ 02, 20, 21, 22 \}\) and, thus, \[Z = \{ 02, (02, e), 20, (20, e), 21, (21, e), 22, (22, e) \} \text{.}\] By definition, we have \(\mathscr{W}(u) = \{ u \}\) for \(u \in \{ 02, 20, 21, 22 \}\). For the states of the form \((u, e)\), \(\mathscr{W}(u, e)\) contains those words \(v\) that are reachable from \(u\) by a run \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v}; \setlength{\edgelength}{\widthof{\scriptsize/e^i}+0.5cm} \node[base right=\edgelength of l] (r) {u}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize/e^i} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) for some \(i > 0\) (but observe that we always have an \(e/e\)-self-loop at every state in \(\mathcal{T} \circ 22\)). This yields: \[\begin{align} \mathscr{W}(02, e) &= \{ 02, 11, 12, 21 \}, & \mathscr{W}(20, e) &= \{ 10, 11, 20, 21 \}, \\ \mathscr{W}(21, e) &= \{ 11, 21 \} \qquad \text{and} & \mathscr{W}(22, e) &= \{ 11, 12, 21, 22 \} \end{align}\] Observe that \(11\) is contained in all sets \(\mathscr{W}(u, e)\). Thus, we have \((u, e) \mathrel{\mathcal{F}} (v, e)\) for all \(u, v \in \{ w \} \cup A\). We also always have \(\mathscr{W}(u) \cap \mathscr{W}(u, e) = \{ u \} \neq \emptyset\) (because of the \(e/e\)-self-loops) and, thus, \(u \mathrel{\mathcal{F}} (u, e)\) for all \(u \in \{ w \} \cup A\). We also have \(21 \in \mathscr{W}(u, e)\) for all such \(u\) and, thus, \(21, (21, e) \mathrel{\mathcal{F}} (u, e)\).

For the transitions, we obtain \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {u}; \setlength{\edgelength}{\widthof{\scriptsizee}+0.5cm} \node[base right=\edgelength of l] (r) {(u, e)}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizee} (r.mid west); \end{tikzpicture}\) and \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(u, e)}; \setlength{\edgelength}{\widthof{\scriptsizee}+0.5cm} \node[base right=\edgelength of l] (r) {(u, e)}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizee} (r.mid west); \end{tikzpicture}\) for all \(u \in \{ w \} \cup A\) from the first and second line of the definition. Observe that no state \(u \in \{ w \} \cup A\) has an out-going transition with an output different to \(e\) in \(\mathcal{T} \circ 22\) (although such transitions may exist in general!) and that, thus, we do not create any transition using the third line of the definition. The last line does create transitions, however. For example, consider the transition \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {12}; \setlength{\edgelength}{\widthof{\scriptsizep/r}+0.5cm} \node[base right=\edgelength of l] (r) {02}; \path[->] (l.mid east) edge node[inner sep=0pt] {\scriptsizep/r} (r.mid west); \end{tikzpicture}\) in \(\mathcal{T} \circ 22\). We have \(12 \in \mathscr{W}(02, e), \mathscr{W}(22, e)\) and, therefore, obtain the transitions \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(02, e)}; \setlength{\edgelength}{\widthof{\scriptsizer}+0.5cm} \node[base right=\edgelength of l] (r) {02}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizer} (r.mid west); \end{tikzpicture}\) and \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(22, e)}; \setlength{\edgelength}{\widthof{\scriptsizer}+0.5cm} \node[base right=\edgelength of l] (r) {02}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizer} (r.mid west); \end{tikzpicture}\) in \(\mathcal{A}_w\).

In the same way, all the (reachable) transitions with output different to \(e\) create transitions in \(\mathcal{A}_w\) and, in the end, we obtain:

Note that, while this automaton is deterministic, this is not the case in general!

The states of the NFRA represent parts of the orbital transducer \(\mathcal{T} \circ w\) or – more precisely – the product \(\mathcal{T} \circ w \times R\). This correspondence is given by \(\mathscr{W}\): states of the form \((u, \varepsilon, C, C)\) represent the (constantly many) words from \(A \cup \{ w \}\) with an in-going transition whose output is not from \(S\) and the other states of the form \((u, s, C, D)\) represent the words reachable with output equal to \(s\) in \(\mathscr{S}(\mathcal{T})\) from those words in \(A \cup \{ w \}\). We have basically attached a copy of the (finite) Cayley graph of \(S^+ / {=_{\mathcal{T}}}\) to every \(u \in A \cup \{ w \}\). Additionally, we continue to have those transitions whose output is not from \(S\).

While we are mostly interested in the output of the transitions in \(\mathcal{T} \circ w\), we use the last two components of a state to track the class of \(R\) for the input. The first one is used to store the class of the input up to when we entered the last word from \(A \cup \{ w \}\) and, in the second one, we nondeterministically guess the class of the input when we leave the local copy of the Cayley graph. Of course, it is possible that the nondeterministic choice is impossible to realize; in this case, we have that \(\mathscr{W}\) of a state is the empty set.

Proposition 15. The recognized relation of \(\mathcal{A}_w\) is \(\mathcal{E}_w\).

Proof. First, we show the following (which we will refer to as Claim I): if we have a run \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{r}/\boldsymbol{q}}+0.5cm} \node[base right=\edgelength of l] (r) {w}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{r}/\boldsymbol{q}} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) for some \(\boldsymbol{r}, \boldsymbol{q} \in Q^*\) and \(v \in \Sigma^*\) in \(\mathcal{T} \circ w\), then, for all \(\boldsymbol{q}' \in Q^*\) with \(\boldsymbol{q}' \approx \boldsymbol{q}\), we have a run \[\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(u, s, C, \mathscr{C}(\boldsymbol{r}))}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{q}'}+0.5cm} \node[base right=\edgelength of l] (r) { (w, \varepsilon, \mathscr{C}(\varepsilon), \mathscr{C}(\varepsilon)) }; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{q}'} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\] in \(\mathcal{A}_w\) for some \(u \in A \cup \{ w \}\), \(s \in S \uplus \{ \varepsilon \}\) and class \(C\) of \(R\) with \(v \in \mathscr{W}(u, s, C, \mathscr{C}(\boldsymbol{r}))\). From the claim follows that \(\boldsymbol{p} \mathrel{\mathcal{E}}_w \boldsymbol{q}\) implies that \(\mathcal{A}_w\) accepts \((\boldsymbol{p}, \boldsymbol{q})\) for all \(\boldsymbol{p}, \boldsymbol{q} \in Q^+\).

In order to show Claim I, we first observe that we have a run \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {v}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{r}/\boldsymbol{q}}+0.5cm} \node[base right=\edgelength of l] (r) {w}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{r}/\boldsymbol{q}} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) in \(\mathcal{T} \circ w\) if and only if we have a run \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(v, \mathscr{C}(\boldsymbol{r}))}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{r}/\boldsymbol{q}}+0.5cm} \node[base right=\edgelength of l] (r) {(w, \mathscr{C}(\varepsilon))}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{r}/\boldsymbol{q}} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) in \(\mathcal{T} \circ w \times R\). We use this fact and an induction on the letters from \(P\) and the \(S^+\) blocks of \(\boldsymbol{q}\) to show the claim. For the empty state sequence, there is nothing to show as we have \(\mathscr{W}(w, \varepsilon, \mathscr{C}(\varepsilon), \mathscr{C}(\varepsilon)) = \{ w \}\).

Next, we consider the state sequences \(\boldsymbol{s} \boldsymbol{q}\) with \(\boldsymbol{s} \in S^+\) and \(\boldsymbol{q} \in \{ \varepsilon \} \cup PQ^*\) and suppose that there is a run

in \(\mathcal{T} \circ w \times R\) for some \(u, u' \in \Sigma^*\). For every \(\boldsymbol{q}' \in Q^*\) with \(\boldsymbol{q}' \approx \boldsymbol{q}\), we have a run \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(u, \varepsilon, C, C)}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{q}'}+0.5cm} \node[base right=\edgelength of l] (r) {(w, \varepsilon, \mathscr{C}(\varepsilon), \mathscr{C}(\varepsilon))}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{q}'} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) in \(\mathcal{A}_w\) by induction (or because \(\boldsymbol{q}\) is empty). Note here that only states of the form \((u, \varepsilon, C, C)\) have ingoing transitions labeled with elements from \(P\) (and that the initial state is of this form as well). To conclude this case we show that we have a run \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(u, \boldsymbol{s}, C, D)}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{t}}+0.5cm} \node[base right=\edgelength of l] (r) {(u, \varepsilon, C, C)}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{t}} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) for all \(\boldsymbol{t} \in S^+\) with \(\boldsymbol{t} \approx \boldsymbol{s}\). This is sufficient because we have \(u' \in \mathscr{W}(u, \boldsymbol{s}, C, D)\) due to the run \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(u', D)}; \setlength{\edgelength}{\widthof{\scriptsize/\boldsymbol{s}}+0.5cm} \node[base right=\edgelength of l] (r) {(u, C)}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize/\boldsymbol{s}} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) in \(\mathcal{T} \circ w \times R\). We write \(\boldsymbol{t} = t_\ell \dots t_2 t_1\) for \(t_1, \dots, t_\ell \in S\) and observe that we have a run

in \(\mathcal{A}_w\) by construction.

For the remaining inductive case, consider a state sequence \(p \boldsymbol{q}\) with \(p \in P\) and \(\boldsymbol{q} \in Q^*\) such that there is a run

in \(\mathcal{T} \circ w \times R\). Let \(\boldsymbol{q}' \in Q^*\) be arbitrary with \(\boldsymbol{q}' \approx \boldsymbol{q}\). By induction (or because \(\boldsymbol{q}\) is empty), we have a run \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(u, s, E, C)}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{q}'}+0.5cm} \node[base right=\edgelength of l] (r) {(w, \varepsilon, \mathscr{C}(\varepsilon), \mathscr{C}(\varepsilon))}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{q}'} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) in \(\mathcal{A}_w\) for some \(u \in A \cup \{ w \}\), \(s \in S \uplus \{ \varepsilon \}\) and class \(E\) of \(R\) with \(u' \in \mathscr{W}(u, s, E, C)\). We also have a transition \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(v, \varepsilon, D, D)}; \setlength{\edgelength}{\widthof{\scriptsizep}+0.5cm} \node[base right=\edgelength of l] (r) {(u, s, E, C)}; \path[<-] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizep} (r.mid west); \end{tikzpicture}\) in \(\mathcal{A}_w\) by construction because we have the transition \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(v, D)}; \setlength{\edgelength}{\widthof{\scriptsize/p}+0.5cm} \node[base right=\edgelength of l] (r) {(u', C)}; \path[<-] (l.mid east) edge node[inner sep=0pt] {\scriptsize/p} (r.mid west); \end{tikzpicture}\) in \(\mathcal{T} \circ w \times R\). This concludes our proof of Claim I and the first direction as we have \(\mathscr{W}(v, \varepsilon, D, D) = \{ v \}\).

For the other direction, we show the similar Claim II: if we have a run \[\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(u, s, C, D)}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{q}}+0.5cm} \node[base right=\edgelength of l] (r) {(w, \varepsilon, \mathscr{C}(\varepsilon), \mathscr{C}(\varepsilon))}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{q}} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\] in \(\mathcal{A}_w\) for some \(\boldsymbol{q} \in Q^*\), \(u \in A \cup \{ w \}\), \(s \in S \uplus \{ \varepsilon \}\) and classes \(C, D\) of \(R\), then, for every \(u' \in \mathscr{W}(u, s, C, D)\), there is some \(\boldsymbol{q}' \in Q^*\) with \(\boldsymbol{q}' \approx \boldsymbol{q}\), some \(\boldsymbol{r}' \in D\) and a run \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {u'}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{r}'/\boldsymbol{q}'}+0.5cm} \node[base right=\edgelength of l] (r) {w}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{r}'/\boldsymbol{q}'} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) in \(\mathcal{T} \circ w\). The claim implies that \(\boldsymbol{p} \mathrel{\mathcal{E}_w} \boldsymbol{q}\) holds if \(\mathcal{A}_w\) accepts some pair \((\boldsymbol{p}, \boldsymbol{q}) \in Q^+ \times Q^+\).

Recall that we have a run \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {u'}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{r}'/\boldsymbol{q}'}+0.5cm} \node[base right=\edgelength of l] (r) {w}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{r}'/\boldsymbol{q}'} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) in \(\mathcal{T} \circ w\) if and only if we have the run \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(u', \mathscr{C}(\boldsymbol{r}'))}; \setlength{\edgelength}{\widthof{\scriptsize\boldsymbol{r}'/\boldsymbol{q}'}+0.5cm} \node[base right=\edgelength of l] (r) {(w, \mathscr{C}(\varepsilon))}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize\boldsymbol{r}'/\boldsymbol{q}'} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) in \(\mathcal{T} \circ w \times R\). We use this and another induction on the letters from \(P\) and the \(S^+\) blocks of \(\boldsymbol{q}\) to show Claim II. For the empty state sequence, there is nothing to show as we have \(\mathscr{W}(w, \varepsilon, \mathscr{C}(\varepsilon), \mathscr{C}(\varepsilon)) = \{ w \}\).

Therefore, we first consider a state sequence \(\boldsymbol{s} \boldsymbol{q}\) with \(\boldsymbol{s} \in S^+\) and \(\boldsymbol{q} \in \{ \varepsilon \} \cup PQ^*\) such that we have a run

in \(\mathcal{A}_w\) for some \(u \in A \cup \{ w \}\) and classes \(C, D\) of \(R\). Note that the states on the left have to be of this form due to the construction of \(\mathcal{A}_w\): only states of the form \((u, \varepsilon, C, C)\) have ingoing transitions labeled with an element from \(P\) (and the initial state is of this form) and, from them, we can only reach states of the form \((u, \boldsymbol{s}, C, D)\) by a run labeled with \(\boldsymbol{s}\). Since we have \(\mathscr{W}(u, \varepsilon, C, C) = \{ u \}\), there is some \(\boldsymbol{q}' \in Q^*\) with \(\boldsymbol{q}' \approx \boldsymbol{q}\) and a run \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(u, C)}; \setlength{\edgelength}{\widthof{\scriptsize/\boldsymbol{q}'}+0.5cm} \node[base right=\edgelength of l] (r) {(w, \mathscr{C}(\varepsilon))}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize/\boldsymbol{q}'} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) in \(\mathcal{T} \circ w \times R\) by induction. We are done with this inductive case if we show that, for every \(u' \in \mathscr{W}(u, \boldsymbol{s}, C, D)\), there is a run \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(u', D)}; \setlength{\edgelength}{\widthof{\scriptsize/\boldsymbol{t}}+0.5cm} \node[base right=\edgelength of l] (r) {(u, C)}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize/\boldsymbol{t}} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) in \(\mathcal{T} \circ w \times R\) for some \(\boldsymbol{t} \in S^+\) with \(\boldsymbol{t} \approx \boldsymbol{s}\). Such a run exists, however, by the definition of \(\mathscr{W}(u, \boldsymbol{s}, C, D)\).

It remains to consider the state sequences \(p\boldsymbol{q}\) with \(p \in P\) and \(\boldsymbol{q} \in Q^*\) such that there is a run

in \(\mathcal{A}_w\) for some \(u, v \in A \cup \{ w \}\), \(s \in S \uplus \{ \varepsilon \}\) and classes \(C, D, E\) of \(R\). Again, the state on the left has to be of this form because only such states have ingoing transitions with an element from \(P\) as the label. Also by the construction of \(\mathcal{A}_w\), we obtain that there is some \(u' \in \mathscr{W}(u, s, C, D)\) with a run \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(v, E)}; \setlength{\edgelength}{\widthof{\scriptsize/p}+0.5cm} \node[base right=\edgelength of l] (r) {(u', D)}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize/p} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) in \(\mathcal{T} \circ w \times R\) from the transition \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(v, \varepsilon, E, E)}; \setlength{\edgelength}{\widthof{\scriptsizep}+0.5cm} \node[base right=\edgelength of l] (r) {(u, s, C, D)}; \path[<-] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizep} (r.mid west); \end{tikzpicture}\) in \(\mathcal{A}_w\). By induction, we also obtain that there is some \(\boldsymbol{q}' \in Q^*\) with \(\boldsymbol{q}' \approx \boldsymbol{q}\) and a run \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {(u', D)}; \setlength{\edgelength}{\widthof{\scriptsize/\boldsymbol{q}'}+0.5cm} \node[base right=\edgelength of l] (r) {(w, \mathscr{C}(\varepsilon))}; \path[->] ([yshift=-0.25mm] r.mid west) edge[path] node[above, inner sep=0pt] {\scriptsize/\boldsymbol{q}'} ([yshift=-0.25mm] l.mid east); \end{tikzpicture}\) in \(\mathcal{T} \circ w \times R\), which concludes our proof because we have \(\mathscr{W}(v, \varepsilon, E, E) = \{ v \}\). ◻

\(\omega\)-Regular We have seen (in 11) that the growth behavior of the orbits only depends on the expansion relation and that those can be encoded in NFRAs of uniformly bounded size ([ssec:NFRAs]). Together, this allows us to encode the orbit growth behavior in a finite acceptor. More precisely, we may characterize the infinite words with infinite orbits as a deterministic Büchi language.

Theorem 16. For a regular language \(R \subseteq Q^*\), the language \[\{ \alpha \in \Sigma^\omega \mid |R \circ \alpha| = \infty \}\] is recognized by a deterministic Büchi acceptor. Furthermore, this acceptor can be computed from \(\mathcal{T}\), \(R\) and \(S\).

Proof. Using 3 and 15, we can compute an NFRA \(\mathcal{A}_w\) recognizing \(\mathcal{E}_w\) with at most \((K + 1)N(|S|N + 1)\) states where \(N\) is the number of classes of \(R\) from \(\mathcal{T} \circ w\). In particular, the set \(Y = \{ \mathcal{A}_w \mid w \in \Sigma^* \}\) is finite and we use it as the state set of the sought deterministic Büchi acceptor. To compute \(Y\) and the transitions of the BA, we use an iterative process:

We start with \(\mathcal{A}_\varepsilon\) as the initial state. As long as a state \(\mathcal{A}_w\) has no outgoing transitions, we compute \(\mathcal{A}_{wa}\) from \(\mathcal{T} \circ wa\) for all \(a \in \Sigma\). For each \(a \in \Sigma\), there are two possible situations: The NFRA \(\mathcal{A}_{wa}\) can be isomorphic to an existing state \(\mathcal{A}_{w'}\) or not (where isomorphism is to be understood as that of abstract edge-labeled graphs with a marked initial state and a binary (acceptance) relation over the nodes). If it is not isomorphic to some \(\mathcal{A}_{w'}\) (among the states constructed so far), we add \(\mathcal{A}_{wa}\) as a new state together with the transition \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {\mathcal{A}_w}; \setlength{\edgelength}{\widthof{\scriptsizea}+0.5cm} \node[base right=\edgelength of l] (r) {\mathcal{A}_{wa}}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizea} (r.mid west); \end{tikzpicture}\). If it is isomorphic to a pre-existing state \(\mathcal{A}_{w'}\), we add the transition \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {\mathcal{A}_w}; \setlength{\edgelength}{\widthof{\scriptsizea}+0.5cm} \node[base right=\edgelength of l] (r) {\mathcal{A}_{w'}}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizea} (r.mid west); \end{tikzpicture}\). In both cases, we mark the new transition as accepting if we have \(|R \circ w| < |R \circ wa|\).

This process of adding new states and transitions has to terminate because there are only finitely many possible NFRAs \(\mathcal{A}_w\) and the resulting BA is deterministic.

We do not necessarily end up in \(\mathcal{A}_w\) after reading \(w \in \Sigma^*\) from the initial state \(\mathcal{A}_\varepsilon\). However, we may show (using an induction on the length of \(w\)) that the NFRA \(\mathcal{A}_{w'}\) that we reach by reading \(w\) from \(\mathcal{A}_\varepsilon\) recognizes the expansion relation \(\mathcal{E}_w\):

This is clear for \(w = \varepsilon\). For the inductive step, let \(w = ua\) with \(a \in \Sigma\). Let \(\mathcal{A}_{u'}\) be the state we reach after reading \(u\) from \(\mathcal{A}_\varepsilon\). By its definition, \(\mathcal{A}_{u'}\) recognizes the relation \(\mathcal{E}_{u'}\) but, by induction, it must also recognize \(\mathcal{E}_u\). Thus, we must have \(\mathcal{E}_{u'} = \mathcal{E}_{u}\) and, by 12, also \(\mathcal{E}_{u'a} = \mathcal{E}_{ua}\), which is recognized by \(\mathcal{A}_{u'a}\). When adding the out-going transitions for the state \(\mathcal{A}_{u'}\), we distinguished whether \(\mathcal{A}_{u'a}\) was isomorphic to a pre-existing state or not. If it was not, we added \(\mathcal{A}_{u'a}\) as a new state together with the transition \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {\mathcal{A}_{u'}}; \setlength{\edgelength}{\widthof{\scriptsizea}+0.5cm} \node[base right=\edgelength of l] (r) {\mathcal{A}_{u'a}}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizea} (r.mid west); \end{tikzpicture}\). Thus, in this case, the state we reach after reading \(ua\) from \(\mathcal{A}_\varepsilon\) is \(\mathcal{A}_{u'a}\), which indeed recognizes \(\mathcal{E}_{ua}\) (as stated above). If \(\mathcal{A}_{u'a}\) was isomorphic to some pre-existing state \(\mathcal{A}_{w'}\), we added the transition \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {\mathcal{A}_{u'}}; \setlength{\edgelength}{\widthof{\scriptsizea}+0.5cm} \node[base right=\edgelength of l] (r) {\mathcal{A}_{w'}}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizea} (r.mid west); \end{tikzpicture}\) instead. Since \(\mathcal{A}_{w'}\) is isomorphic to \(\mathcal{A}_{u'a}\), it recognizes the same relation and we indeed have \(\mathcal{E}_{ua} = \mathcal{E}_{u'a} = \mathcal{E}_{w'}\).

Recall that the transition \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {\mathcal{A}_{u'}}; \setlength{\edgelength}{\widthof{\scriptsizea}+0.5cm} \node[base right=\edgelength of l] (r) {\mathcal{A}_{u'a}}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizea} (r.mid west); \end{tikzpicture}\) or \(\begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {\mathcal{A}_{u'}}; \setlength{\edgelength}{\widthof{\scriptsizea}+0.5cm} \node[base right=\edgelength of l] (r) {\mathcal{A}_{w'}}; \path[->] (l.mid east) edge node[inner xsep=0pt, inner ysep=0.2em] {\scriptsizea} (r.mid west); \end{tikzpicture}\), respectively, was accepting if \(|R \circ u'| < |R \circ u'a|\). Since we have \(\mathcal{E}_{u'} = \mathcal{E}_u\) (as just shown), this is the case if and only if \(|R \circ u| < |R \circ ua|\) by 11. Thus, whenever we pass an accepting transition in the Büchi acceptor, the orbit of the word we are reading has indeed increased. This means that its recognized \(\omega\)-language consists exactly of the \(\omega\)-words with an infinite \(R\)-orbit. ◻

Remark 17. Using a straight-forward guess and check approach, one can see that the equivalence problem for NFRAs

Constant:
Input:	NFRAs \(\mathcal{A}_1 = (Z_1, \Gamma, \tau_1, z_{0, 1}, \mathcal{F}_1)\) and \(\mathcal{A}_2 = (Z_2, \Gamma, \tau_2, z_{0, 2}, \mathcal{F}_2)\)
Question:	is \(\mathscr{R}(\mathcal{A}_1) = \mathscr{R}(\mathcal{A}_2)\)?

is certainly in \(\mathrm{\small PSpace}\) (see e. g.[37] or [21] for more information on complexity theory). Therefore, we can replace the check whether an isomorphic NFRA already exists as a state by a check whether an equivalent NFRA already exists in the construction of the Büchi accepter above. This yields a potentially smaller acceptor.

For a finite word \(v \in \Sigma^+\), we write \(v^\omega = v v \dots\) for the \(\omega\)-word arising from \(v\) by concatenating it with itself infinitely often. An \(\omega\)-word is ultimately periodic if it is of the form \(uv^\omega\) for \(u \in \Sigma^*\) and \(v \in \Sigma^+\). Any non-empty \(\omega\)-regular language contains an ultimately periodic word (see e. g.[30]). We immediately obtain from 16 the following specialization of [13] for automaton semigroups of bounded \(S\)-activity. The more general result [13] states that a general automaton semigroup is infinite if and only if it admits a(n infinite) word with an infinite orbit.

Corollary 1. The semigroup \(\mathscr{S}(\mathcal{T})\) generated by the automaton \(\mathcal{T} = (Q, \Sigma, \delta)\) of bounded \(S\)-activity is infinite if and only if there are \(u \in \Sigma^*\) and \(v \in \Sigma^+\) with \(Q^* \circ uv^\omega\) (i. e.if it admits an ultimately periodic word with an infinite orbit).

The Finiteness Problem for Bounded Automaton Semigroups Using 16, we obtain the main result of this paper:

Theorem 18. The problem

Constant:
Input:	a complete \(\mathscr{S}\)-automaton\(\mathcal{T} = (Q, \Sigma, \delta)\), a regular, suffix-closed language \(R \subseteq Q^*\) and a closed subset \(S \subseteq Q\) such that \(S\) generates a finite subsemigroup¹³ and \(\mathcal{T}\) is of bounded \(S\)-activity
Question:	is the image of \(R\) in \(\mathscr{S}(\mathcal{T})\) finite?

is decidable.

Proof. Since \(R\) is suffix-closed, the subset of \(\mathscr{S}(\mathcal{T})\) induced by projecting \(R\) into the semigroup is infinite if and only if there is an \(\omega\)-word with an infinite \(R\)-orbit [13].¹⁴ Thus, the stated decision problem is equivalent to testing whether such an \(\omega\)-word exists. Since the language of such words is effectively deterministic \(\omega\)-regular by 16, this problem is decidable (as the emptiness problem for (deterministic) Büchi acceptors is decidable, see e. g.[30]). ◻

An immediate consequence of this result is that the finiteness problem for complete automaton semigroups of bounded \(S\)-activity is decidable.

Corollary 2. The finiteness problem for \(\mathscr{S}\)-automata of bounded activity

Constant:
Input:	a complete \(\mathscr{S}\)-automaton\(\mathcal{T} = (Q, \Sigma, \delta)\) and a closed subset \(S \subseteq Q\) such that \(S\) generates a finite subsemigroup and \(\mathcal{T}\) is of bounded \(S\)-activity
Question:	is \(\mathscr{S}(\mathcal{T})\) finite?

is decidable.

Additionally, we also get that the finiteness problem for finitely generated subsemigroups of complete automaton semigroups of bounded \(S\)-activity is decidable. This in particular includes the (uniform) order problem for complete automaton semigroups of bounded \(S\)-activity (compare to [11]).

Corollary 3. The subsemigroup finiteness problem for \(\mathscr{S}\)-automata of bounded activity

Constant:
Input:	a complete \(\mathscr{S}\)-automaton\(\mathcal{T} = (Q, \Sigma, \delta)\), a finite set \(\boldsymbol{R} \subseteq Q^*\) and a closed subset \(S \subseteq Q\) such that \(S\) generates a finite subsemigroup and \(\mathcal{T}\) is of bounded \(S\)-activity
Question:	is the subsemigroup of \(\mathscr{S}(\mathcal{T})\) generated by \(\boldsymbol{R}\) finite?

is decidable.

We also obtain some algorithmic consequences for the semigroup generated by the dual automaton. The dual of the complete \(\mathscr{S}\)-automaton\(\mathcal{T} = (Q, \Sigma, \delta)\) is the complete \(\mathscr{S}\)-automaton\(\partial\mathcal{T} = (\Sigma, Q, \partial\delta)\) with \[\partial\delta = \{ \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {a}; \setlength{\edgelength}{\widthof{\scriptsizep/q}+0.5cm} \node[base right=\edgelength of l] (r) {b}; \path[->] (l.mid east) edge node[inner sep=0pt] {\scriptsizep/q} (r.mid west); \end{tikzpicture} \mid \begin{tikzpicture}[auto, shorten >=1pt, >=latex, baseline=(l.base), inner sep=0pt, outer xsep=0.3333em] \node (l) {p}; \setlength{\edgelength}{\widthof{\scriptsizea/b}+0.5cm} \node[base right=\edgelength of l] (r) {q}; \path[->] (l.mid east) edge node[inner sep=0pt] {\scriptsizea/b} (r.mid west); \end{tikzpicture} \in \delta \} \text{.}\] Concerning the dual, we have the following results regarding the existence of elements with (or without) torsion.

Corollary 4. The problems

Constant:
Input:	a complete \(\mathscr{S}\)-automaton\(\mathcal{T} = (Q, \Sigma, \delta)\) and a closed subset \(S \subseteq Q\) such that \(S\) generates a finite subsemigroup and \(\mathcal{T}\) is of bounded \(S\)-activity
Question:	does \(\mathscr{S}(\partial \mathcal{T})\) contain an element without torsion?

and

Constant:
Input:	a complete \(\mathscr{S}\)-automaton\(\mathcal{T} = (Q, \Sigma, \delta)\) and a closed subset \(S \subseteq Q\) such that \(S\) generates a finite subsemigroup and \(\mathcal{T}\) is of bounded \(S\)-activity
Question:	is \(\mathscr{S}(\partial \mathcal{T})\) torsion-free?

are decidable.

Proof. [13] yields that \(\mathscr{S}(\partial \mathcal{T})\) contains an element of torsion if and only if there is a periodic word \(u^\omega\) (with \(u \in \Sigma^+\)) whose orbit \(Q^* \circ u^\omega\) is finite. Similarly, it also yields that \(\mathscr{S}(\partial \mathcal{T})\) contains an element without torsion if and only if \(Q^* \circ u^\omega\) is infinite for some \(u \in \Sigma^+\). Therefore, the two stated problems boil down to testing whether an \(\omega\)-regular language (or its complement, which is also \(\omega\)-regular [30]) contains a periodic word. This, however, is decidable (using standard automaton theory techniques). ◻

References↩︎

[1]

Laurent Bartholdi and Pedro Silva. Groups defined by automata. In Jean-Éric Pin, editor, Handbook of Automata Theory, volume II, chapter 24, pages 871–911. European Mathematical Society, 09 2021.

[2]

Volodymyr V. Nekrashevych. Self-similar groups, volume 117 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2005.

[3]

Rostislav I. Grigorchuk and Igor Pak. Groups of intermediate growth: an introduction. L’Enseignement Mathématique, 54:251–272, 2008.

[4]

Kate Juschenko. Amenability of discrete groups by examples. American Mathematical Society, 2022.

[5]

Rostislav I. Grigorchuk. Groups St Andrews 1997 in Bath: Volume 1, volume 260 of London Mathematical Society Lecture Note Series, chapter On the system of defining relations and the Schur multiplier of periodic groups generated by finite automata, pages 290–317. Cambridge University Press, 1999.

[6]

Alan J. Cain. Automaton semigroups. Theoretical Computer Science, 410(47):5022 – 5038, 2009.

[7]

Tara Brough and Alan J. Cain. Automaton semigroup constructions. Semigroup Forum, 90(3):763–774, 2015.

[8]

Ines Klimann. Automaton semigroups: The two-state case. Theory of Computing Systems, 58:664–680, 2016.

[9]

Tara Brough and Alan J. Cain. Automaton semigroups: New constructions results and examples of non-automaton semigroups. Theoretical Computer Science, 674:1–15, 2017.

[10]

Matthieu Picantin. . In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 124:1–124:15, Dagstuhl, Germany, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

[11]

Laurent Bartholdi, Thibault Godin, Ines Klimann, Camille Noûs, and Matthieu Picantin. A new hierarchy for automaton semigroups. International Journal of Foundations of Computer Science, 31(08):1069–1089, 2020.

[12]

Daniele D’Angeli, Emanuele Rodaro, and Jan Philipp Wächter. On the structure theory of partial automaton semigroups. Semigroup Forum, pages 51 – 76, 2020.

[13]

Daniele D’Angeli, Dominik Francoeur, Emanuele Rodaro, and Jan Philipp Wächter. Infinite automaton semigroups and groups have infinite orbits. Journal of Algebra, 553:119 – 137, 2020.

[14]

Daniele D’Angeli, Emanuele Rodaro, and Jan Philipp Wächter. Automaton semigroups and groups: On the undecidability of problems related to freeness and finiteness. Israel Journal of Mathematics, 237:15–52, 2020.

[15]

Tara Macalister Brough, Jan Philipp Wächter, and Janette Welker. Preserving self-similarity in free products of semigroups. International Journal of Algebra and Computation, 35(08):1091–1121, 2025.

[16]

Ines Klimann, Jean Mairesse, and Matthieu Picantin. Implementing computations in automaton (semi)groups. In Nelma Moreira and Rogério Reis, editors, Implementation and Application of Automata, pages 240–252, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.

[17]

Pierre Gillibert. The finiteness problem for automaton semigroups is undecidable. International Journal of Algebra and Computation, 24(01):1–9, 2014.

[18]

Daniele D’Angeli, Emanuele Rodaro, and Jan Philipp Wächter. Orbit expandability of automaton semigroups and groups. Theoretical Computer Science, 809:418 – 429, 2020.

[19]

Daniele D’Angeli, Emanuele Rodaro, and Jan Philipp Wächter. The freeness problem for automaton semigroups. In Rastislav Královič and Antonı́n Kučera, editors, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), volume 306 of Leibniz International Proceedings in Informatics (LIPIcs), pages 44:1–44:18, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

[20]

Said N. Sidki. Automorphisms of one-rooted trees: growth, circuit structure, and acyclicity. Journal of Mathematical Sciences, 100(1):1925–1943, 2000.

[21]

Jan Philipp Wächter and Armin Weiß. Languages and Automata: GAGTA book 3, chapter “The Word Problem for Automaton Groups,” pages 265–396. DeGruyter, 2024.

[22]

Ievgen V. Bondarenko, Natalia V. Bondarenko, Said N. Sidki, and Flavia R. Zapata. On the conjugacy problem for finite-state automorphisms of regular rooted trees. Groups, Geometry, and Dynamics, 7:232–355, 2013.

[23]

Pierre Gillibert. An automaton group with undecidable order and Engel problems. Journal of Algebra, 497:363 – 392, 2018.

[24]

Laurent Bartholdi and Ivan Mitrofanov. The word and order problems for self-similar and automata groups. Groups, Geometry, and Dynamics, 14:705–728, 2020.

[25]

Ievgen Bondarenko and Jan Philipp Wächter. On orbits and the finiteness of bounded automaton groups. International Journal of Algebra and Computation, 31(06):1177–1190, 2021.

[26]

Rostislav I. Grigorchuk, Volodymyr V. Nekrashevych, and Vitaly I. Sushchanskı̆i. Automata, dynamical systems, and groups. Proceedings of the Steklov Institute of Mathematics, 231:128–203, 2000.

[27]

Ievgen V. Bondarenko and Volodymyr V. Nekrashevych. Post-critically finite self-similar groups. Algebra and Discrete Mathematics, 2(4):21–32, 2003.

[28]

Jan Philipp Wächter and Armin Weiß. An automaton group with -complete word problem. Theory of Computing Systems, 67(1):178–218, 2023.

[29]

Maximilian Kotowsky and Jan Philipp Wächter. The word problem for finitary automaton groups. In Henning Bordihn, Nicholas Tran, and György Vaszil, editors, Descriptional Complexity of Formal Systems, pages 94–108, Cham, 2023. Springer Nature Switzerland.

[30]

Dominique Perrin and Jean-Éric Pin. Infinite words, volume 141 of Pure and Applied Mathematics. Elsevier, Amsterdam, 2004.

[31]

John M. Howie. Fundamentals of Semigroup Theory. London Mathematical Society Monographs. Clarendon Press, 1995.

[32]

John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.

[33]

Zoran Šunić and Enric Ventura. The conjugacy problem in automaton groups is not solvable. Journal of Algebra, 364:148–154, 2012.

[34]

Daniele D’Angeli, Emanuele Rodaro, and Jan Philipp Wächter. On the complexity of the word problem for automaton semigroups and automaton groups. Advances in Applied Mathematics, 90:160–187, 2017.

[35]

Peter Linz. An introduction to formal languages and automata, 6th Edition. Jones and Bartlett Publishers, 2016.

[36]

Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger, and Ulrich Hertrampf. Discrete Algebraic Methods. De Gruyter, 2016.

[37]

Christos M. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.

The first two authors are members of the INdAM-GNSAGA group.↩︎
The third author was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 492814705 – while visiting the Department of Mathematics at Politecnico di Milano. Some part of this article was written while he was affiliated with Universität des Saarlandes and partly funded by ERC grant 101097307. The listed affiliation is his current one where his research is supported by EPSRC project EP/Y008626/1 ‘Special Inverse Monoids: Geometry, Structure & Algorithms’.↩︎
Although they do not clearly distinguish between automaton monoids and semigroups.↩︎
The classes of \(L\) can be identified with the states of the minimal deterministic acceptor of \(L\). The initial state is \(\mathscr{C}(\varepsilon)\) and the final states are the classes \(C\) with \(C \subseteq L\). For every class \(\mathscr{C}(u)\) and every \(a \in \Sigma\), we have an \(a\)-labeled transition from \(\mathscr{C}(u)\) to \(\mathscr{C}(ua)\).↩︎
In more general automaton-theoretic terms, this would rather be called a finite-sate, letter-to-letter transducer.↩︎
i. e.if it is deterministic and complete↩︎
We use this notation to mean that all transitions starting in \(p\) have output \(p\) and all transitions starting in \(q\) have output \(q\).↩︎
The orbital transducer is basically the part reachable from \(w\) in the \(|w|\)-th power of the dual of \(\mathcal{T}\) (up to mirroring the words).↩︎
Please note that [11] uses the slightly misleading term “automaton semigroup” for what we call an automaton monoid here.↩︎
For our algorithmic results, it is important to note that these powers (and the minimization) can be computed from \(\mathcal{T}\) and the subset \(S\) if the semigroup \(S^+/{=_\mathcal{T}}\) is finite. For more information on how to minimize an automaton, see e. g.[16] or [35].↩︎
The difference to the previous definition is that there a block of \(e\) states was shortened into a single \(e\) but not completely dropped.↩︎
Recall that we use \(\mathcal{P}(X)\) to denote the powerset of \(X\).↩︎
Recall that requiring \(S \subseteq Q\) is not a restriction by 3.↩︎
This is precisely the statement of the referenced theorem.↩︎

The Finiteness Problem for Automaton Semigroups of Extended Bounded Activity

Abstract

0.0.0.1 Sets, Semigroups, Words and (Regular) Languages.

Regular Languages.

Büchi Acceptors and \(\omega\)-Regular Languages.

Semigroup Presentations and Free Products.

0.0.0.2 \(\mathscr{S}\)-automata.

Union and Power Automata.

0.0.0.3 Orbits.

0.0.0.4 The Product \(\mathcal{T} \circ w \times R\).

0.0.0.5 Expandability.

Extension to Automata.

Idea of the construction.

Back to the General Case.

References↩︎

Subjects

Updated on Academus