$\varepsilon$-separated subset of $L(\bar{\pi}^{*})_{\leq T}$ and its size is
at least $2^{\left\lfloor\frac{T}{3\varepsilon|\pi|}\right\rfloor}$.

Case of Type II structural obesity.

For a Type II cycle, the construction is similar. For technical reasons, for a
given $\varepsilon$, we will build an $\varepsilon^{\prime}$-separated set
with $\varepsilon^{\prime}$ the next value (slightly) larger than
$\varepsilon$ such that $\frac{1}{3\varepsilon^{\prime}|\pi|}$ is integer. The
difference with previous construction is that as long as only $\pi$ is
executed, instead of going back to $u$, we go farther and farther from $u$ and
closer and closer to $v$: a run of duration $t$ from $(1-\lambda)u+\lambda v$
goes to $(1-\lambda-t)u+(\lambda+t)v$, provided $\lambda+t\leq 1$. So the
analogs of runs $\rho_{0}$ and $\rho_{1}$ can only be executed
$\frac{1}{3\varepsilon^{\prime}|\pi|}$ times at most before it is necessary to
“recharge” the clocks through the execution of a resetting cycle.

More precisely, the vertex $u$ can be the starting point of a run of duration
0 through $\pi$, going back to $u$, as well of runs of duration $\geq 1$,
going to $v$; while, through $\pi$, vertex $v$ can only be the starting point
of realizations of duration $0$, all going back to $v$. By convex
combinations, from any $x(\lambda)=(1-\lambda)u+\lambda v$ it is thus possible
to start a run of any duration $\mu\leq 1-\lambda$ and reach the point
$x(\lambda+\mu)$.

In particular, with $\varepsilon^{\prime}$ such that
$0<\varepsilon^{\prime}<\frac{1}{3|\pi|}$, for any point $x(\lambda)$ of the
segment $[u,\tilde{v}]$ (where $\tilde{v}=x(1-3\varepsilon^{\prime}|\pi|)$),
there exists at least a run $\sigma(x(\lambda))$ of $\bar{\pi}$ of duration
$\varepsilon^{\prime}$ and a run $\rho_{0}(x(\lambda))$ of duration
$3\varepsilon^{\prime}|\pi|$. Let us define $\rho_{1}(x)=\sigma(x)^{3|\pi|}$
(so that $\rho_{0}(x)$ and $\rho_{1}(x)$ have the same duration) and remark
that both $\rho_{0}(x(\lambda))$ and $\rho_{1}(x(\lambda))$ reach
$x(\lambda+3\varepsilon^{\prime}|\pi|)$. Before we construct the new function
$f_{x}:\\{0,1\\}^{*}\to\mathop{Runs}_{\bar{\pi}^{*}}$, let us choose a
resetting cycle $\pi_{r}$ such that its p-orbit has an edge from $v$ to $u$, a
run $\rho_{r}$ that goes from $v$ to $u$ through $\pi_{r}$ and $\tau_{r}$ the
duration of this run.

Now we construct $f_{x}$: $f_{x}(\epsilon)=\epsilon$; with $b\in\\{0,1\\}$, if
$x\in[u,\tilde{v}]$, $f_{x}(b)=\rho_{b}(x)$ and
$f_{x}(bw)=\rho_{b}(x)f_{\mathop{dst}\nolimits(\rho_{b}(x)}(w)$; otherwise
$f_{v}(w)=\rho_{r}(v)f_{u}(w)$ (note that values of $x$ in $(\tilde{v},v)$
cannot be reached with this strategy; hence $f$ is left undefined for this
interval).

Here again, the language of the labels of the image is
$\varepsilon^{\prime}$-separated for the same reason as in the previous case.
So $S_{\varepsilon}(T)\triangleq\\{\mathop{word}(f_{u}(w))\mid
w\in\\{0,1\\}^{*}\\}_{\leq T}$ is an $\varepsilon^{\prime}$-separated (thus
$\varepsilon$-separated) subset of
$L((\bar{\pi}^{\frac{1}{3\varepsilon^{\prime}|\bar{\pi}|}}\bar{\pi_{r}})^{*})_{\leq
T}$ equal to the product of its slices corresponding to intervals
$[ip,i(p+1)]$, $i\in{\rm Nature}$, with
$p=\left\lfloor\frac{1}{3\varepsilon^{\prime}|\pi|}\right\rfloor
3\varepsilon^{\prime}|\pi|+\tau_{r}=1+\tau_{r}$. Each slice contains exactly
$2^{\frac{1}{3\varepsilon^{\prime}|\pi|}}$ elements, hence
$\log\\#S_{\varepsilon}(T)\geq{\frac{1}{3\varepsilon^{\prime}|\pi|}\left\lfloor\frac{T}{p}\right\rfloor}\geq{\frac{1}{3\varepsilon^{\prime}|\pi|}\left\lfloor\frac{T}{1+\tau_{r}}\right\rfloor}\geq{(\frac{1}{3\varepsilon|\pi|}-1)\left\lfloor\frac{T}{1+\tau_{r}}\right\rfloor}$.
Hence $\mathcal{BH}_{\varepsilon}(L(\bar{\pi}^{*})_{\leq
T})=\Theta(\frac{1}{\varepsilon})$ (the upper bound is given by comparison
with the universal language, having a bandwidth
$\Theta(\frac{1}{\varepsilon})$).

See 3

######  Proof B.29 (Proof sketch).

The RsTA contains at most $n$ locations. Each orbit can be represented as a
couple of locations and an $(m+1)\times(m+1)$-matrix with elements in
$\Lambda_{d}$ (a semiring of 4 elements). Thus $\\#\mathbf{M}_{d}\leq
n^{2}\cdot 4^{(m+1)^{2}}=\poly(n)\myexp(m).$ An automaton is structurally
obese whenever it contains a path $\pi$ with orbit $\gamma_{d}(\pi)$ having an
obesity pattern. According to Lem. 3.5, only cycles up to length
$\\#\mathbf{M}_{d}$ need to be checked. We use now the reachability method
[21, Sect. 7.3] to detect the obesity pattern in a space-efficient way, see
LABEL:algo:obese. An auxiliary function isAPathOrbit(e,h), true iff there is a
path $\pi\in\gamma_{d}^{-1}(e)$ of length $\leq 2^{h}$ in the RsTA, is
computed by a divide-and-conquer algorithm.

Listing 2: Deciding structural obesity

⬇

Boolean function isAPathOrbit(e, h)

if h = 0 return (e=$\mathbf{1}$ || $\exists\delta:\gamma_{d}(\delta)=$e)

for all orbits e1, e2

if e1$\cdot$e2 = e && isAPathOrbit(e1, h-1) && isAPathOrbit(e2, h-1)

return true

return false

Boolean function isStrucObese()

for all orbits e

if (obeseType1(e) && isAPathOrbit(e, $\log\\#\mathbf{M}_{d}$)) return true

for all states q, int i,j $\leq d_{q}$

for all orbits e1,e2 from q to q

if (obeseType2(e1,i,j) && resettingPath(e2,j,i)&&

isAPathOrbit(e1, $\log\\#\mathbf{M}_{d}$) && isAPathOrbit(e2,
$\log\\#\mathbf{M}_{d}$))

return true

return false

The algorithm requires a call stack of depth $\log\\#\mathbf{M}_{d}$, the size
of each stack frame is $O(\log n)+\poly(m)$, thus the computation takes space
$\left(O(\log
n)+\poly(m)\right)\cdot\log\\#\mathbf{M}_{d}=\log^{2}(n)\poly(m)$.

See 4.6

######  Proof B.30.

This is a direct corollary of Prop. B.27. We obtain an $\varepsilon$-separated
set $S^{\prime}$ from $S$, the $\varepsilon$-separated set of
$L_{\bar{\pi}^{*},T}(u,\cdot)$ constructed in the previous proof, by
prepending a common prefix $w$ to all its elements, such that $w$ is the
labeling of a run $\rho$ going from an initial vertex of an initial location
to the vertex $u$, through some path $p$.

This shows that $L_{\bar{p}\bar{\pi}^{*}}$ is obese, but since for each
$\varepsilon$-separated subset of $L_{\bar{p}\bar{\pi}^{*},T}$,
$L_{{p}{\pi}^{*},T}$ admits a $\varepsilon^{\prime}$-separated subset of the
same size (according to Lem. A.15), this actually also proves that
$L_{{p}{\pi}^{*}}$ is obese and hence its superset $L(\mathcal{A})$.

##  Appendix C Proofs on meagerness

###  C.1 Monoid properties

See 3.3

######  Proof C.1.

Here again, we only need to prove, for any two edge sequences
$\pi_{1},\pi_{2}$, that
$\gamma_{f}(\pi_{1}\circ\pi_{2})=\gamma_{f}(\pi_{1})\gamma_{f}(\pi_{2})$. It
is still trivially true if any of the two sequences is $\epsilon$, or if
$\pi_{1}\circ\pi_{2}$ is not a path. So assume again both $\pi_{1}$ and
$\pi_{2}$ are paths of length $\geq 1$ such that $\pi_{1}\circ\pi_{2}$ also is
a path and let us call $R$ the destination region of $\pi_{1}$.

Let us choose any source vertex $u$ and any destination vertex $v$ for
$\pi_{1}\circ\pi_{2}$. Then
$\left(\gamma_{f}(\pi_{1})\gamma_{f}(\pi_{2})\right)[u,v]$ has to take one of
the three values of $\Lambda_{d}$:

  * •

If it is $\mathsf{0}$: the proof is the same as the case $\mathsf{0}$ in Prop.
4.3 (actually $\gamma_{f}(\pi)[u,v]=\mathsf{0}$ iff
$\gamma_{d}(\pi)[u,v]=\mathsf{0}$ iff $\gamma(\pi)=0$).

  * •

If it is $\mathbf{narrow}$, there is a single vertex $w$ of $R$ such that
$\gamma_{f}(\pi_{1})[u,w]=\gamma_{f}(\pi_{2})[w,v]\neq\mathsf{0}$, and this
value has to be $\mathbf{narrow}$. But according to Lem. A.12, a full region
must be reachable from $u$ through $\pi_{1}$, and $v$ must be reachable from a
full region through $\pi_{2}$; the intersection of these two regions must also
be a region, but this region contains only the vertex $w$, hence it is equal
to $\\{w\\}$. So the only run from $u$ to $v$ through $\pi_{1}\circ\pi_{2}$ is
the concatenation of the only run from $u$ to $w$ and the only run from $w$ to
$v$. Hence
$\gamma_{f}(\pi_{1}\circ\pi_{2})[u,v]=\mathbf{narrow}=\left(\gamma_{f}(\pi_{1})\gamma_{f}(\pi_{2})\right)[u,v]$.

  * •

If it is $\mathbf{wide}$, because of semiring rules Table 1, there are 2
possibilites. Either $\mathbf{wide}$ is obtained by virtue of f-orbit
multiplication, meaning there is $w$ such that
$\gamma_{f}(\pi_{1})[u,w]=\mathbf{wide}$ and
$\gamma_{f}(\pi_{2})[w,v]\neq\mathsf{0}$; since, by definition,
$L_{\overline{\pi_{1}}}(u,w)$ contains several words, and thus so is the case
of $L_{\overline{\pi_{1}\circ\pi_{2}}}(u,v)$. Or we obtained $\mathbf{wide}$
by virtue of f-orbit addition, meaning that there are $w_{1}$ and $w_{2}$,
$w_{1}\neq w_{2}$, such that $\gamma_{f}(\pi_{1})[u,w_{1}]=\mathbf{narrow}$,
$\gamma_{f}(\pi_{2})[w_{1},v]=\mathbf{narrow}$,
$\gamma_{f}(\pi_{1})[u,w_{2}]=\mathbf{narrow}$ and
$\gamma_{f}(\pi_{2})[w_{2},v]=\mathbf{narrow}$; this implies you can go from
$u$ to $v$ by at least two different orbit paths, with different timings,
hence $L_{\bar{\pi}(u,v)}$ contains at least two distinct words. Hence
$\gamma_{f}(\pi_{1}\circ\pi_{2})[u,v]=\mathbf{wide}=\left(\gamma_{f}(\pi_{1})\gamma_{f}(\pi_{2})\right)[u,v]$.

###  C.2 Upper bound

Throughout this section, we reason about a structurally meager region-split
automaton, we will abbreviate it as smA. As we said, the case when the
language $L_{\bar{\pi}}(x,x)$ is a singleton (typical for structurally meager
automata) will play the key role. First, we prove that whenever $\pi$ is an
“idempotent cycle”, the language mentioned above is indeed a singleton.

######  Lemma C.2.

In an smA, for any path $\pi$ with idempotent orbit and a clock vector $x$ in
the closure of starting region of $\pi$, the language $L_{\bar{\pi}}(x,x)$ is
either empty or a singleton.

######  Proof C.3.

First note that it is already known [22], for p-orbits, that
$L_{\bar{\pi}}(x,x)$ is non-empty iff $x$ is in the convex hull of some set of
vertices with self-loops. So, it remains to prove that, in the non-empty case,
the language is a singleton, which we do by using the fact that, in the
f-orbit, all these self-loops are $\mathbf{narrow}$ when $\pi$ is structurally
meager.

Before going on, we show it is possible to assume w.l.o.g. that, for all
factorization $\pi=\pi_{1}\circ\pi_{2}$, the “shifted” cycle
$\pi^{\prime}=\pi_{2}\circ\pi_{1}$ always has an idempotent f-orbit. If not,
reason with $\pi^{p}$, where $p$ is sufficiently large, observe it is still
structurally meager and then, prove its polytope is a singleton. It implies
that $L_{\bar{\pi}}(x,x)$ also is a singleton: indeed, if it were some non-
singleton polytope, then $L_{\bar{\pi}^{p}}(x,x)$ would also include several
words.

So we assume that $\pi$ and all its “shifted” versions have idempotent
p-orbits.

Suppose, towards a contradiction, that $L_{\bar{\pi}}(x,x)$ is neither empty
nor a singleton. Then, this language has at least two words with different
timings and, thus, with a first disagreeing timing, so there exist two paths
$\pi_{1}$ and $\pi_{2}$ and an edge $\delta\in\Delta$ such that
$\pi=\pi_{1}\circ\delta\circ\pi_{2}$ a word $w_{1}$ through $\pi_{1}$, two
delays $t$ and $t^{\prime}$ with $0<t<t^{\prime}$ and two words $w_{2}$ and
$w_{2}^{\prime}$ through $\pi_{2}$ such that both
$w_{1}\circ(\mathop{lbl}\nolimits_{\delta},t)\circ w_{2}$ and
$w_{1}\circ(\mathop{lbl}\nolimits_{\delta},t^{\prime})\circ w^{\prime}_{2}$
belong to $L_{\bar{\pi}}(x,x)$. Let us call $y$ and $y^{\prime}$ the two clock
vectors reached after reading respectively
$w_{1}\circ(\mathop{lbl}\nolimits_{\delta},t)$ and
$w_{1}\circ(\mathop{lbl}\nolimits_{\delta},t)$ through $\pi_{1}\circ\delta$
from $x$.

If $y\neq y^{\prime}$, then observe both vectors are reachable from each other
through $\pi^{\prime}=\pi_{2}\circ\pi_{1}\circ\delta$. The smallest affine set
that contains the two vectors has dimension 1, hence, according to Cor. A.25,
the starting region of $\pi^{\prime}$ has at least one non-singleton SCC $S$.
Since $\gamma_{f}(\pi^{\prime})$ is idempotent, all self-loops
$\gamma_{f}(\pi^{\prime})[u,u]$ for $u\in S$ are $\mathbf{wide}$, which is
impossible in a structurally meager automaton.

If $y=y^{\prime}$, this means the edge $\delta$ can reach the same vector with
different delays from the same originating vector, and hence that
$\mathfrak{g}_{\delta}$ is not punctual and $\mathfrak{r}_{\delta}$ contains
at least all clocks such that their value is not constrained inside a
singleton in $\mathfrak{g}_{\delta}$. In this case
$S(\mathop{dst}\nolimits_{\delta})$ also is a singleton, of the form $\\{v\\}$
with $v=(0,\dots,0)$. So $v$ is the only vertex of
$\gamma_{d}(\pi_{2}\circ\pi_{1}\circ\delta)$. It necessarily has a self-loop,
and since $L_{\overline{\pi_{2}\circ\pi_{1}\circ\delta}}(v,v)$ contains
several words, this loop is $\mathbf{wide}$, which is the non-meagerness
pattern.

We establish now a continuity result for the vicinity of a single-word path:

######  Lemma C.4.

Given a path $\pi$ in an RsTA and clock vectors $x^{0},y^{0}$, such that
$L_{\bar{\pi}}(x^{0},y^{0})=\\{w^{0}\\}$ (a singleton), for any clock vectors
$x^{1},y^{1}$ such that both $||x^{0}-x^{1}||_{\infty}<\varepsilon$,
$||y^{0}-y^{1}||_{\infty}<\varepsilon$, and for any $w^{1}\in
L_{\bar{\pi}}(x^{1},y^{1})$ we have $d(w^{0},w^{1})<3\varepsilon$.

######  Proof C.5.

We fix notations for start and end regions of the path:
$S(\mathop{src}\nolimits_{\pi})=R_{s}$,
$S(\mathop{dst}\nolimits_{\pi})=R_{d}$, clearly $x^{0},x^{1}\in\bar{R_{s}}$
and $y^{0},y^{1}\in\bar{R_{d}}$ (otherwise the languages
$L_{\bar{\pi}}(\cdot)$ would be empty.)

For any $x\in\bar{R_{s}},y\in\bar{R_{d}}$ all words in $L_{\bar{\pi}}(x,y)$
have the form $(a_{1},t_{1}),\dots(a_{n},t_{n})$, where the untiming is always
the same $a_{1}\dots a_{n}=\mathop{lbl}\nolimits_{w}$, and the set of timings
is defined by a parametric DBM $A(x,y)$, as described in Prop. A.2, and its
projection to $t_{j}$ is an interval $[L_{j}(x,y);U_{j}(x,y)]$ as described in
Prop. A.4. As we know $L_{\bar{\pi}}(x^{0},y^{0})$ is a singleton $w^{0}$,
thus for every $j$, the interval for $t^{0}_{j}$ is also a singleton:
$L_{j}(x^{0},y^{0})=U_{j}(x^{0},y^{0})=t^{0}_{j}$. DBMs $A(x^{1},y^{1})$ and
$A(x^{0},y^{0})$ satisfy the hypotheses of Cor. A.5: they are equal in the
middle and $\varepsilon$-close on border, thus by this Corollary,

$t^{0}_{j}-3\varepsilon<L_{j}(x^{1},y^{1})\leq t^{1}_{j}\leq
U_{j}(x^{1},y^{1})<t^{0}_{j}+3\varepsilon,$

hence $|t^{0}_{j}-t^{1}_{j}|<3\varepsilon$ (for any $j$). We conclude that
$d(w^{0},w^{1})<3\varepsilon$.

In order to characterize the duration of singletons we will naturally use the
monoid $\mathbf{M}_{d}$ again and define a new structural property. An
idempotent $e$ in $\mathbf{M}_{d}$ will be called _quick_ whenever all its
self-loops are $\mathbf{instant}$.

######  Lemma C.6.

In an smA, if for a cycle $\pi$ with idempotent $e=\gamma_{d}(\pi)$ and a
clock vector $x$ the language $L_{\bar{\pi}}(x,x)$ is a singleton $\\{w\\}$,
then

  * •

if $e$ is quick then $\tau(w)=0$;

  * •

otherwise $\tau(w)\geq 1$.

######  Proof C.7.

Let $\pi$ be a cycle such that $\gamma_{f}(\pi)$ is idempotent and $x$ a clock
vector such that $L_{\bar{\pi}}(x,x)$ is not empty. Necessarily, $x$ is in a
facet of the starting region of $\pi$, delimited by vertices all having self-
loops in the $(p,f,d)$-orbits (the convex sums of triples $(x,t,x)$ that
satisfy the linear system of constraints of $\pi$ also satisfy it; hence if
$x$ is a convex combination of vertices $v$ such that at least one is such
that $(v,t,v)$ satisfies the system for several $t$, then $x$ also accepts
several $t$ such that $(x,t,x)$ satisfies the system). Let us call $V$ the set
of vertices of this facet.

If $\gamma_{d}(\pi)$ is quick (only has $\mathbf{instant}$ self-loops), then
any element $w$ of $L_{\bar{\pi}}(x,x)$ is such that $\tau(w)=0$. If
$\gamma_{d}(\pi)$ only has $\mathbf{slow}$ self-loops, then $\tau(w)\geq 1$.
If $\gamma_{d}(\pi)$ has a $\mathbf{fast}$ self-loop, then $P(x,x)$ is not a
singleton. If $\exists u,v\in V$ s.t. $\gamma_{d}(\pi)[u,u]=\mathbf{instant}$
and $\gamma_{d}(\pi)[v,v]=\mathbf{slow}$, then Lem. B.8 applies, and we deduce
that $\gamma_{p}(\pi)$ is complete and that therefore all the self-loops of
$\gamma_{f}(\pi)$ are $\mathbf{wide}$ and that therefore $L_{\bar{\pi}}(x,x)$
is not a singleton.

We will now need a small technical lemma.

######  Lemma C.8.

Let $e$ be a realizable idempotent of $\mathbf{M}_{f}$. If $u$ and $v$ are
transient vertices such that $e[u,v]=\mathbf{narrow}$, then there is a non-
transient vertex $w$ such that $e[u,w]=\mathbf{narrow}$ and
$e[w,v]=\mathbf{narrow}$.

######  Proof C.9.

Assume there is no such vertex $w$. Then all paths from $u$ to $v$ only pass
through transient vertices. Paths through transient vertices cannot go back or
stay in place, thus by taking $n$ the length of the longest such path,
$e^{n+1}$ does not contain a path from $u$ to $v$, which contradicts $e$ being
idempotent.

The following lemma states that in any singleton run along a structurally
meager idempotent cycle, all iterations except the first and the last one loop
on a same clock configuration.

######  Lemma C.10.

In an smA, let $e\neq 0$ be an idempotent, let $\pi=\pi_{1}\dots\pi_{k}$ such
that all $\gamma(\pi_{i})=e$ and $L_{\bar{\pi}}(x,y)=\\{w\\}$. Then there
exists a factorization $w=w_{1}\dots w_{k}$ and a clock vector $z$ such that:
$L_{\bar{\pi}_{1}}(x,z)=\\{w_{1}\\}$, for $i=2..k-1$ it holds that
$L_{\bar{\pi}_{i}}(z,z)=\\{w_{i}\\}$, and finally
$L_{\bar{\pi}_{k}}(z,y)=\\{w_{k}\\}$.

######  Proof C.11.

Assume such a path $\pi$ and call $\rho=\rho_{1}\dots\rho_{k}$ its unique run
such that $\mathop{Runs}_{\bar{\pi}}(x,y)=\\{\rho\\}$ and
$\rho_{i}\in\mathop{Runs}_{\bar{\pi_{i}}}$.

Necessarily there is $x_{0}=x,x_{1},x_{2},\dots x_{k}=y$ such that
$\mathop{Runs}_{\bar{\pi}}(x_{i},x_{i+1})=\\{\rho_{i+1}\\}$.

Moreover, the timing vector of $\rho_{i}$ necessarily is a convex combination
of timings of runs from a vertex $u$ to another $v$ in the support of $e$.
Note that if there were several such runs from $u$ to $v$, there would be
several runs from $x_{i}$ to $x_{i+1}$ through $\pi_{i+1}$, hence several from
$x$ to $y$ through $\pi$, which would contradict the hypothesis. Hence the
convex combination has positive coefficients only for runs from $u$ to $v$
such that $e[u,v]=\mathbf{narrow}$.

Additionally, we show that, for $i<k$, $\rho_{i}$ cannot be a convex
combination including runs from vertex $u$ to vertex $v$ when $v$ is
transient.

Indeed, $\mathbf{narrow}$ edges can only go from $u$ to $v$ such that either
$u=v$ or at least one of the two vertices is transient (otherwise it would
violate the idempotency of $e$).

Assume $\rho_{i}$ can be written as a linear combination of vertex-to-vertex
runs such that one goes from $u$ to $v$ with $v$ transient. Hence $x_{i}$ has
a positive barycentric coordinate in $v$. So $\rho_{i+1}$ is a convex
combination of vertex-to-vertex runs which must include a run from $v$ to
another vertex $w$. Remark that $\rho_{i}\rho_{i+1}$ is also a realization of
$\pi$ and so it can be written as a linear combination of vertex-to-vertex
runs too, this one such that one run goes from $u$ to $w$ (connecting the run
from $u$ to $v$ and the one from $v$ to $w$). By Lem. C.8, there are non-
transient vertices in the path from $u$ to $v$ and from $v$ to $w$. But in
this case, $e[u,w]=\mathbf{wide}$, so it means other runs than
$\rho_{i}\rho_{i+1}$ can go from $x_{i-1}$ to $x_{i+1}$ which contradicts the
hypothesis.

This means that the barycentric coordinate of $x_{i}$, $0<i<k$, for any
transient vertex is $0$. So for $1<i<k$, $\rho_{i}$ is a convex combination of
vertex-to-vertex runs starting from each non-transient vertex $u$ and going to
themselves (going to another non-transient is impossible because the edge is
$\mathbf{wide}$, going to a transient is forbidden, as we just proved), and
the coefficient of these runs is necessarily equal to the weight of $u$ in the
barycentric coordinates of $x_{i-1}$, hence $x_{i}=x_{i-1}$.

Given a timed word $w=(a_{1},t_{1})\dots(a_{n},t_{n})$ we denote
$|\\!|\\!|w|\\!|\\!|=\\#\\{i\mid t_{i-1}<t_{i}\\}$, i.e. the number of non-
instant events in $w$. We will now estimate the number of non-instant delays
in singletons w.r.t. their duration.

######  Lemma C.12.

For any path $\pi$ and clock vectors $x,y$ in an smA, if the language
$L_{\bar{\pi}}(x,y)=\\{w\\}$ (a singleton), then $|\\!|\\!|w|\\!|\\!|\leq
a\tau(w)+a$, with the constant $a$ depending on the automaton.

######  Proof C.13.

We will use Simon’s theorem for monoid $\mathbf{M}_{d}$ and prove by
induction, that whenever $\pi\in X_{h}$ (with $X_{h}$ as in (4)) satisfies the
Lemma’s hypothesis for some $x,y,w$, then $|\\!|\\!|w|\\!|\\!|\leq
2^{h}\tau(w)+2^{h}$. Since $h\leq 3\\#\mathbf{M}_{d}$, this would imply the
required result with $a=2^{3\\#\mathbf{M}_{d}}$.

  * •

The base case $\pi\in X_{0}$ is evident, $|\\!|\\!|w|\\!|\\!|\leq 1$.

  * •

The first inductive case is $\pi=\pi_{1}\pi_{2}$ with $\pi_{1},\pi_{2}\in
X_{h}$ satisfying the inductive hypothesis. On the unique run along $\pi$ from
$x$ to $y$, let $z$ be the vector of clock values at the end of the prefix
$\pi_{1}$. It is easy to see that languages $L_{\bar{\pi}_{1}}(x,z)$ and
$L_{\bar{\pi}_{2}}(z,y)$ should be some singletons $w_{1}$ and $w_{2}$. Thus
by inductive hypothesis $|\\!|\\!|w_{1}|\\!|\\!|\leq 2^{h}\tau(w_{1})+2^{h}$,
similarly for $w_{2}$. As required

$|\\!|\\!|w|\\!|\\!|=|\\!|\\!|w_{1}|\\!|\\!|+|\\!|\\!|w_{2}|\\!|\\!|\leq(2^{h}\tau(w_{1})+2^{h})+(2^{h}\tau(w_{2})+2^{h})=2^{h}\tau(w)+2^{h+1}.$

  * •

The second inductive case is $\pi=\pi_{1}\dots\pi_{k}$ with all $\pi_{i}\in
X_{h}$ and $\gamma(\pi_{i})=e$ for some non-quick idempotent $e$. By Lem. C.10
we find a clock vector $z$, and timed words $w_{1},\dots w_{k}$ such that
$w=w_{1}\dots w_{k}$ and $L_{\bar{\pi}_{1}}(x,z)=\\{w_{1}\\}$,
$L_{\bar{\pi}_{k}}(z,y)=\\{w_{k}\\}$, and $L_{\bar{\pi}_{i}}(z,z)=\\{w_{i}\\}$
for each $i=2..k-1$. $|\\!|\\!|w_{i}|\\!|\\!|\leq 2^{h}\tau(w_{i})+2^{h}$. By
Lem. C.6, $\tau(w_{i})\geq 1$ for all $i=2..k-1$, hence $k-2\leq\tau(w)$. By
inductive hypothesis, $|\\!|\\!|w_{i}|\\!|\\!|\leq 2^{h}\tau(w_{i})+2^{h}$ for
any $i$. Summarizing, we get the required estimate:

$|\\!|\\!|w|\\!|\\!|=\sum_{i=1}^{k}|\\!|\\!|w_{i}|\\!|\\!|\leq\sum_{i=1}^{k}(2^{h}\tau(w_{i})+2^{h})\leq
2^{h}\tau(w)+2^{h}(\tau(w)+2)=2^{h+1}\tau(w)+2^{h+1}.$

  * •

The last inductive case is $\pi=\pi_{1}\dots\pi_{k}$ with all $\pi_{i}\in
X_{h}$ and $\gamma(\pi)=\gamma(\pi_{i})=e$ for a quick idempotent $e$. Let us
factorize $w=w_{1}\dots w_{k}$ according to Lem. C.10.

By Lem. C.6, $\tau(w_{i})=0$ for $i=2..k-1$, thus
$|\\!|\\!|w|\\!|\\!|=|\\!|\\!|w_{1}|\\!|\\!|+|\\!|\\!|w_{k}|\\!|\\!|$.
Applying the inductive hypothesis to $w_{1}$ and $w_{k}$, we obtain again

$|\\!|\\!|w|\\!|\\!|=|\\!|\\!|w_{1}|\\!|\\!|+|\\!|\\!|w_{2}|\\!|\\!|\leq(2^{h}\tau(w_{1})+2^{h})+(2^{h}\tau(w_{2})+2^{h})=2^{h}\tau(w)+2^{h+1}.$

######  Definition C.14.

Given a run $\rho$ (on $w$) we define its _signature_
$\sigma(\rho)=I_{0}\delta_{0}I_{1}\delta_{1}\dots\delta_{k}I_{k}$ with
$k=|\\!|\\!|w|\\!|\\!|$, $\forall j\in\\{0..k\\}\,I_{j}\subset\Sigma$,
$\delta_{j}\in\Delta$ as follows:

  * •

for every (maximal) sequence of instant (0 time) transitions in $\rho$ we keep
only the set of labels $I\subset\Sigma$;

  * •

for every non-instant transition we keep only the edge $\delta\in\Delta$.

There are at most $2^{(k+1)\\#\Sigma}\cdot\\#\Delta^{k}$ different signatures
of size $k$. Consequently, for some constant $c$ the number of signatures of
size $\leq k$ can be bounded by $2^{ck}$.

######  Lemma C.15.

In an smA, for an idempotent $e\in\mathbf{M}_{d}$, the following holds. If we
have two runs $\rho_{1},\rho_{2}$, with $\gamma(\mathop{path}(\rho_{i}))=e$,
$\mathop{src}\nolimits_{\rho_{i}}=\mathop{dst}\nolimits_{\rho_{i}}=x$, and
with the same signature $\sigma(\rho_{1})=\sigma(\rho_{2})$, then
$d(\mathop{word}(\rho_{1}),\mathop{word}(\rho_{2}))=0$.

######  Proof C.16.

The factors of the runs $\rho_{i}$ corresponding to the $I_{j}$ have exactly
the same effects on clocks: they reset all clocks that are not 0 in the ending
region of $\delta_{j-1}$ and become 0 in the starting region of $\delta_{j}$
and leave all other clocks unchanged (an instant run cannot change a clock it
does not reset).

So, after the prefix of $\rho_{1}$ up to $\delta_{j-1}$, it is possible to run
the sequence of instant transitions corresponding to $I_{j}$ in $\rho_{2}$,
instead of the instant transitions corresponding to $I_{j}$ in $\rho_{1}$, and
still reach the same state (and thus continue with the rest of the suffix of
$\rho_{1}$ and still go back to $x$). By induction it is thus possible to
build a run $\rho_{1}^{\prime}$ from $x$ to $x$ such that
$d(\mathop{word}(\rho_{1}),\mathop{word}(\rho_{1}^{\prime}))=0$ and
$\mathop{path}(\rho_{1}^{\prime})=\mathop{path}(\rho_{2})$. But since
$L_{\mathop{path}(\rho_{2})}(x,x)$ is a singleton (structural thinness), it is
necessary that $\rho_{1}^{\prime}=\rho_{2}$. Hence
$d(\mathop{word}(\rho_{1}),\mathop{word}(\rho_{2}))=0$.

We are ready to upper bound information in singletons.

######  Lemma C.17.

For any smA, there exists a constant $b$ such that, given any idempotent non-
zero $e\in\mathbf{M}_{d}$ and clock vector $x$, the language
$L_{eT}(x)\triangleq\bigcup_{\pi\in\gamma^{-1}(e)}L_{\pi T}(x,x)$ admits a
$0$-net $\mathcal{N}_{1}(e,x,T)$ of cardinality no more than $2^{bT+b}$.

By definition, a $0$-net of a set $S$ has an element at distance $0$ from each
element of $S$.

######  Proof C.18.

By virtue of Lem. C.2, $L_{\pi T}(x,x)$ is empty or singleton, thus for any
timed word $w\in L_{eT}(x)$, Lem. C.12 can be applied and
$|\\!|\\!|w|\\!|\\!|\leq{aT+a}$. Thus for any run $\rho$ on $w$, the size of
the signature $\sigma(\rho)$ is also bounded by ${aT+a}$.

Now, by Lem. C.15, to build the $0-$net $\mathcal{N}_{1}(e,x,T)$, it suffices
to take the trace of one representative run for each possible signature, there
are $2^{c(aT+a)}$ possibilities.

######  Construction C.19 (Partition of regions).

Given an smA, an $\varepsilon$, and an idempotent non-zero
$e\in\mathbf{M}_{d}$, take a path $\pi\in\gamma^{-1}(e)$ and its initial
region $R=S(\mathop{src}\nolimits_{\pi})$. According to Constrs. A.22 and
A.23, we select a family $\Lambda$ of $\dim R$ independent Lyapunov functions
on $R$. We partition the closed region $\bar{R}$ into cells of clock vectors
having the same $\varepsilon$-integer part for each Lyapunov function (i.e.
the same integer vector $\left\lfloor\Lambda(x)/\varepsilon\right\rfloor$). We
notice now that for an idempotent $e$ the partition does not depend on the
choice of the path $\pi$.

Note that each cell can be characterized by a tuple of integers
$\varkappa=(\varkappa_{1},\ldots,\varkappa_{d})\in{\rm Nature}^{d}$ with
$d=dim(R)$ such that for each $x\in c$ and $1\leq i\leq d$,
$\varkappa_{i}=\left\lfloor{\ell_{i}(x)}/{\varepsilon}\right\rfloor-\left\lfloor{\ell_{i-1}(x)}/{\varepsilon}\right\rfloor$
where by convention we put $\ell_{0}(x)=0$.

Given a vertex $v$, we denote by $\ell_{v}$ the smallest function of $\Lambda$
such that $\ell_{t}(v_{t})=1$, and $I_{v}$ its support. Abusively, we denote
$\ell_{v-1}$ the element of vector $\Lambda$ preceding $\ell_{v}$ (in the
topological order of Constr. A.22), we have that (for an smA)
$\lambda_{v}=\ell_{v}-\ell_{v-1}$. Finally, we denote the corresponding
component of $\varkappa$ by $\varkappa_{v}$.

######  Lemma C.20.

With the hypotheses and notations from the construction above, if $t$ is a
transient vertex, and if $x$ and $y$ are clock vectors such that
$P_{\bar{\pi}}(x,y)\neq\emptyset$ then
$\ell_{t}(y)\leq\ell_{t}(x)-\lambda_{t}(x)$.

######  Proof C.21.

By virtue of Lem. A.18, there exists a stochastic matrix $P$ such that
$\lambda(y)=\lambda(x)P$, with $P_{uv}$ being positive only if there is an
edge $(u,v)$ in $\gamma(\pi)$, where $\lambda(x)$ is the vector of barycentric
coordinates of the clock vector $x$ relative to the vertices of
$S(\mathop{src}\nolimits_{\pi})$.

$1-\ell_{t}(y)=\sum_{u\not\in I_{t}}\lambda_{u}(y)=\sum_{u\not\in
I_{t}}\sum_{v}\lambda_{v}(x)P_{vu}=\sum_{v}\lambda_{v}(x)\left(\sum_{u\not\in
I_{t}}P_{vu}\right)\\\ =\sum_{v\in
I_{t}\setminus\\{t\\}}\lambda_{v}(x)\left(\sum_{u\not\in
I_{t}}P_{vu}\right)+\lambda_{t}(x)\left(\sum_{u\not\in
I_{t}}P_{tu}\right)+\sum_{v\not\in I_{t}}\lambda_{v}(x)\left(\sum_{u\not\in
I_{t}}P_{vu}\right)\\\ =\sum_{v\in
I_{t}\setminus\\{t\\}}\lambda_{v}(x)\left(\sum_{u\not\in
I_{t}}P_{vu}\right)+\lambda_{t}(x)+\sum_{v\not\in
I_{t}}\lambda_{v}(x)\geq\lambda_{t}(x)+\sum_{v\not\in I_{t}}\lambda_{v}(x)\\\
=\lambda_{t}(x)+1-\sum_{v\in I_{t}}\lambda_{v}(x).$

We conclude.

######  Lemma C.22.

For any cell $c_{e\varepsilon\varkappa}$ the following alternative holds:

  * •

if for some transient vertex $t$ we have $\varkappa_{t}\geq 1$, then for any
$x,y\in c_{e\varepsilon\varkappa}$ it holds that $L_{\pi}(x,y)=\emptyset$. We
call such cell $c_{e\varepsilon\varkappa}$ _transient_.

  * •

Otherwise (if for all transient vertices $v_{t}$ we have $\varkappa_{t}=0$),
then there exists an $x\in c_{e\varepsilon\varkappa}$ having
$L_{\bar{\pi}}(x,x)\neq\emptyset$ (and thus a singleton). We denote it
$x_{e\varepsilon\varkappa}$ and call such cells _recurrent_.

######  Proof C.23.

In the former case, following the previous lemma, we have that
$\ell_{t}(y)\leq\ell_{t}(x)-\lambda_{t}(x)=\ell_{t-1}(x)$. Then

$\left\lfloor\frac{\ell_{t}(y)}{\varepsilon}\right\rfloor\leq\left\lfloor\frac{\ell_{t-1}(x)}{\varepsilon}\right\rfloor<\left\lfloor\frac{\ell_{t-1}(x)}{\varepsilon}\right\rfloor+1\leq\left\lfloor\frac{\ell_{t-1}(x)}{\varepsilon}\right\rfloor+\varkappa_{t}.$

But in order for $y$ to be in $c_{e\varepsilon\varkappa}$ , we must have,
among other properties, that
$\left\lfloor\frac{\ell_{t-1}(y)}{\varepsilon}\right\rfloor=\left\lfloor\frac{\ell_{t-1}(x)}{\varepsilon}\right\rfloor$
and
$\left\lfloor\frac{\ell_{t}(y)}{\varepsilon}\right\rfloor=\left\lfloor\frac{\ell_{t-1}(y)}{\varepsilon}\right\rfloor+\varkappa_{t}$,
which, as per the above inequality, does not hold.

In the latter case, we can choose values of $\Lambda(\cdot)$ corresponding to
the cell $c_{e\varepsilon\varkappa}$ with $\ell_{t}(\cdot)=\ell_{t-1}(\cdot)$
(and thus $\lambda_{t}(\cdot)=0$) for all transient vertices $t$. By Lem. A.27
there exists a point $x$ in the cell corresponding to these values of
$\Lambda$. Such an $x$ is a combination of vertices with self-loops, which
gives $L_{\bar{\pi}}(x,x)\neq\emptyset$, as explained in the proof of Lem.
C.2.

######  Lemma C.24.

For fixed $e$ and $\varepsilon$, cells $c_{e\varepsilon\varkappa}$ have the
following properties:

  * •

the number of cells is at most
$f_{1}(\varepsilon)\triangleq\left\lceil\frac{1}{\varepsilon}\right\rceil^{\dim
R}$;

  * •

the diameter of each cell is at most $K\varepsilon$, with $K$ from Lem. A.27;

  * •

there is a partial order over cells: $c^{1}\succeq c^{2}$, whenever some
$x^{1}\in c^{1}$, $x^{2}\in c^{2}$ satisfy $\Lambda(x^{1})\geq\Lambda(x^{2})$.
The language $L_{\bar{\pi}}(c^{1},c^{2})$ can be non-empty only if
$c^{1}\succeq c^{2}$.

######  Proof C.25.

The first statement is trivial, the second is a consequence of Lem. A.27, and
the third follows from Def. A.19.

######  Definition C.26.

A non-empty run $\rho$ is called $\varepsilon$-_still_ if

  * •

$e=\gamma_{f}(\mathop{path}(\rho))$ is an idempotent;

  * •

and $\rho$ goes from a recurrent cell $c_{e\varepsilon\varkappa}$ to the same
cell.

We denote the set $\mathop{word}(\rho)$ over all $\varepsilon$-still runs by
$\mathop{Still}_{\varepsilon}$, and its restriction to words of duration $\leq
T$ by $\mathop{Still}_{\varepsilon T}$.

######  Construction C.27 (Net for $Still$).

The net $\mathcal{N}_{2}(\varepsilon,T)$ is built as follows. For each
recurrent cell $c_{e\varepsilon\varkappa}$ let $x_{e\varepsilon\varkappa}$ be
as in Lem. C.24. Take

$\mathcal{N}_{2}\triangleq\bigcup_{\begin{subarray}{c}e=ee\\\
c_{e\varepsilon\varkappa}\text{recurrent}\end{subarray}}\mathcal{N}_{1}(e,x_{e\varepsilon\varkappa},T+1).$

######  Lemma C.28.

Suppose $3K\varepsilon<1$. The set $\mathcal{N}_{2}(\varepsilon,T)$ is a
$3K\varepsilon$-net for the language $\mathop{Still}_{\varepsilon T}$ of size
$f_{2}(\varepsilon)2^{bT}$ (for some function $f_{2}$).

######  Proof C.29.

Let $w\in\mathop{Still}_{\varepsilon T}$, by definition
$w=\mathop{word}(\rho)$ with $\rho$ from some $x\in c_{e\varepsilon\varkappa}$
to some $y\in c_{e\varepsilon\varkappa}$ (in the same recurrent cell). Let
$\pi=\mathop{path}(\rho)$. By Lem. C.22,
$L(\pi,x_{e\varepsilon\varkappa},x_{e\varepsilon\varkappa})$ is some singleton
$\\{w^{\prime}\\}$. By Lem. C.24,
$||x-x_{e\varepsilon\varkappa}||_{\infty}\leq K\varepsilon$ and
$||y-x_{e\varepsilon\varkappa}||_{\infty}\leq K\varepsilon$, thence by Lem.
C.4 $d(w,w^{\prime})\leq 3K\varepsilon$. This implies that
$\tau(w^{\prime})\leq T+3K\varepsilon<T+1$, and by Lem. C.17 there exists
$w^{\prime\prime}\in\mathcal{N}_{1}(e,x_{e\varepsilon\varkappa},T+1)$, such
that $d(w^{\prime},w^{\prime\prime})=0$. Hence $d(w,w^{\prime\prime})\leq
2K\varepsilon$ and by construction $w^{\prime\prime}\in\mathcal{N}_{2}$. Thus
$\mathcal{N}_{2}$ is indeed a $3K\varepsilon$-net for the language
$\mathop{Still}_{\varepsilon T}$. The size estimation is obtained by
multiplying the size of $\mathcal{N}_{1}$ by the number of cells.

We proceed now with factorizing words in $\mathop{Still}_{\varepsilon}$
fragments and transitions between them.

######  Lemma C.30.

For an smA $\mathcal{A}$ there exists a function $f_{3}(\varepsilon)$, such
that for any $\varepsilon$ every word $w\in L(\mathcal{A})$ admits a
factorization $w=w_{1}\dots w_{N}$ with $N\leq f_{3}(\varepsilon)$, with each
$w_{i}$ either having one letter or belonging to
$\mathop{Still}_{\varepsilon}$.

######  Proof C.31.

We will use Simon’s theorem (for monoid $\mathbf{M}_{d}$) and prove by
induction that for every path $\pi\in X_{h}$, every $w\in L_{\pi}$ admits a
factorization with $N\leq(2f_{1}(\varepsilon))^{h}$. Since the height $h$ is
bounded by $K$, this yields the required bound $N<f_{3}(\varepsilon)$ with
$f_{3}(\varepsilon)=(2f_{1}(\varepsilon))^{K}$

  * •

In the base case $\pi\in X_{0}$, the word $w$ has one letter and its
factorization is trivial ($N=1$).

  * •

In the first inductive case $\pi=\pi_{1}\pi_{2}$, with $\pi_{1},\pi_{2}\in
X_{h}$. Consequently $w=w_{1}w_{2}$ with $w_{i}\in L_{\pi_{i}}$, the words
$w_{1},w_{2}$ admitting factorizations with $(2f_{1}(\varepsilon))^{h}$
factors. Concatenating those we obtain a factorization for $w$ with
$2(2f_{1}(\varepsilon))^{h}<(2f_{1}(\varepsilon))^{h+1}$ factors.

  * •

In the other inductive case, there exists an idempotent $e$ and
$\pi=\pi_{1}\dots\pi_{J}$, with $\gamma_{d}(\pi_{i})=e$ and $\pi_{i}\in
X_{h}$. Passing to runs, we get $\rho=\rho_{1}\dots\rho_{J}$, with
$w=\mathop{word}(\rho)$, and $\mathop{path}(\rho_{i})=\pi_{i}$. The
factorization in $\rho_{i}$ is too long and too precise, we will partition it
into fewer clusters. Let $z_{i}$ be clock vectors (traversed by the run
$\rho$), such that $\mathop{src}\nolimits_{\rho_{i}}=z_{i-1}$ and
$\mathop{dst}\nolimits_{\rho_{i}}=z_{i}$. Let $c_{i}$ be the cell of $z_{i}$,
that is the unique $c_{e\varepsilon\varkappa}$ containing $z_{i}$. By Lem.
C.24 $c_{0}\succeq c_{1}\succeq\cdots\succeq c_{J}$, and there are at most
$f_{1}(\varepsilon)$ different cells in this sequence, let us denote them
$c^{i}$. It means that the sequence can be written as

$c^{0}=c^{0}=\dots c^{0}\succ c^{1}=\dots c^{1}\succ c^{2}\dots c^{M}$

with $M<f_{1}(\varepsilon)$. Notice that only recurrent cells can be repeated.
We will concatenate together all runs $\rho_{j}$ from $c^{i}$ to itself, and
call the result of concatenation $\zeta^{i}$; we also denote $\rho_{j}$ from
$c^{i}$ to $c^{i+1}$ by $\rho^{i}$. This yields a new factorization:

$\rho=\zeta^{0}\rho^{0}\zeta^{1}\rho^{1}\dots\zeta^{M},\quad
M<f_{1}(\varepsilon)$

with all $\zeta^{i}$ from a cell to the same cell, and all
$\mathop{path}(\rho^{i})\in X_{h}$. Applying the projection
$\mathop{word}(\cdot)$ we get a factorization $w=u^{0}v^{0}u^{1}v^{1}\dots
u^{M}$ with all $u^{i}\in\mathop{Still}_{\varepsilon}$ (or equal to the empty
word) and all $v^{i}$ satisfying the inductive hypothesis. Factorizing each
$v^{i}$ according to the inductive hypothesis, we get a required factorization
of $w$ into
$f_{1}(\varepsilon)+f_{1}(\varepsilon)(2f_{1}(\varepsilon))^{h}<(2f_{1}(\varepsilon))^{h+1}$
factors. This concludes the proof.

At the last step we build an $O(\varepsilon)$-net for all the words $w\in
L_{T}(\mathcal{A})$:

######  Construction C.32 (Net for $L_{T}$).

The elements of the net $\mathcal{N}_{3}(\varepsilon,T)$ are generated as
follows

  * •

choose $N\leq f_{3}(\varepsilon)$ and $N$ dates $0\leq t_{1}\leq
t_{2}\leq\cdots t_{N}\leq T$ which are multiples of $\varepsilon$;

  * •

at some of those dates put a letter in $\Sigma$;

  * •

at all other $t_{i}$ insert an element of
$\mathcal{N}_{2}(\varepsilon,t_{i+1}-t_{i}+\varepsilon)$.

We remark that elements of the second kind can slightly overlap with the rest
of the word, i.e., go beyond $t_{i+1}$.

######  Lemma C.33.

$\mathcal{N}_{3}(\varepsilon,T)$ is a $(3K+1/2)\varepsilon$-net for $L_{T}$
(for $\varepsilon$ small enough).

######  Proof C.34.

Let $w\in L_{T}(\mathcal{A})$, we will explain how to find a world in
$\mathcal{N}_{3}(\varepsilon,T)$ at a small distance from $w$.

To that aim, consider the factorization $w=w_{1}\dots w_{N}$ provided by Lem.
C.30. For each factor $w_{i}$ of the first kind (containing a delay and one
letter $a_{i}$) let $t_{i}=\tau(w_{1}\dots w_{i})$, i.e. the date when this
letter happens in the word $w$. For each factor of the second kind
($w_{i}\in\mathop{Still}_{\varepsilon}$) let $t_{i}=\tau(w_{1}\dots w_{i-1})$
the starting date of factor $w_{i}$. We notice that $0\leq t_{1}\leq t_{2}\leq
t_{N}$, and that for any factor $w_{i}$ of the second kind $\tau(w_{i})\leq
t_{i+1}-t_{i}$.

For every $t_{i}$, let $t^{\prime}_{i}$ be the closest $\varepsilon$-integer.
We have that $0\leq t^{\prime}_{1}\leq t^{\prime}_{2}\leq t^{\prime}_{N}$, and
for any factor $w_{i}$ of the second kind $\tau(w_{i})\leq
t^{\prime}_{i+1}-t^{\prime}_{i}+\varepsilon$. For any such $w_{i}$ of the
second kind let $w^{\prime}_{i}$ be its $2K\varepsilon$-approximation from the
net
$\mathcal{N}_{2}(\varepsilon,t^{\prime}_{i+1}-t^{\prime}_{i}+\varepsilon)$.

We are ready to build an approximated word $w^{\prime}$. For each factor
$w_{i}$ of the first kind, the word $w^{\prime}$ contains $a_{i}$ at date
$t^{\prime}_{i}$. For each factor $w_{i}$ of the second kind, the word
$w^{\prime}$ contains the approximation $w^{\prime}_{i}$ starting at
$t^{\prime}_{i}$.

By construction, $w^{\prime}\in\mathcal{N}_{3}(\varepsilon,T)$. On the other
hand, $d(w,w^{\prime})\leq\varepsilon$, indeed each factor of the first kind
in $w$ is shifted by at most $\varepsilon/2$, and each factor of the second
kind in $w$ is $3K\varepsilon$-approximated and shifted by at most
$\varepsilon/2.$

######  Lemma C.35.

The cardinality of $\mathcal{N}_{3}(\varepsilon,T)$ is bounded by
$T^{f_{3}(\varepsilon)}f_{4}(\varepsilon)2^{bT}$.

######  Proof C.36.

There are $\binom{T/\varepsilon}{f_{3}(\varepsilon)}$ ways of choosing
$f_{3}(\varepsilon)$ dates, which can be bounded by
$(T/\varepsilon)^{f_{3}(\varepsilon)}$. For each of those one can choose a
letter in $\Sigma$, or decide to put an element of $\mathcal{N}_{2}$, or put
nothing (if there are less than $f_{3}(\varepsilon)$ factors), this gives
$(\\#\Sigma+2)^{f_{3}(\varepsilon)}$ possibilities. For elements of
$\mathcal{N}_{2}$ the number of possibilities is

$\prod_{\text{some
}j<f_{3}(\varepsilon)}f_{2}(\varepsilon/2)2^{b(t_{j+1}-t_{j}+\varepsilon)}\leq
2^{bT}2^{b\varepsilon
f_{3}(\varepsilon)}f_{2}(\varepsilon/2)^{f_{3}(\varepsilon)}.$

Multiplying everything together we get an expression of the required form
$T^{f_{3}(\varepsilon)}f_{4}(\varepsilon)2^{bT}$ for an appropriate $f_{4}$.

See 3.7

######  Proof C.37.

Let $K^{\prime}=3K+1/2$. By the previous lemma, the bandwidth is bounded by

$\lim_{T\to\infty}\frac{\log\left(T^{f_{3}(\varepsilon/K^{\prime})}f_{4}(\varepsilon/K^{\prime})2^{bT}\right)}{T}=b.$

###  C.3 Proof details for lower bound

######  Lemma C.38.

If a cyclic path $\pi$ in an RsTA is not structurally meager, then
$\mathcal{BC}_{\varepsilon}(L_{\pi^{*}})=\Omega(\log(1/\varepsilon))$, and
hence $L_{\pi^{*}}$ is not a meager language.

######  Proof C.39.

Without loss of generality, we assume $\gamma_{f}(\pi)$ is idempotent. It is
not structurally meager, hence it has a $\mathbf{wide}$ self-loop on some
vertex $v$, implying $\dim P_{\pi}(v,v)\geq 1$. Now consider
$\gamma_{d}(\pi)[v,v]$. It cannot be $\mathbf{instant}$ or $\mathsf{0}$, since
$\gamma_{f}[v,v]=\mathbf{wide}$. If it is $\mathbf{fast}$, then $\pi$ is
structurally obese, thus its language is obese (and not meager). So we
consider the remaining case: $\gamma_{d}(\pi)[v,v]=\mathbf{slow}$: i.e. the
cycle cannot be executed in less than one time unit. So not only the set of
possible timings has a dimension of at least 1, but also all timings have a
total duration of at least 1. Without loss of generality, we can assume we can
select a segment of realizations such that all its timing vectors have the
same total duration (if not, take any segment: take 2 runs $\rho_{1}$ and
$\rho_{2}$ in this segment, going from $v$ to itself, with different total
duration; from now on instead of $\pi$, we consider $\pi^{2}$ and the segment
delimited by the timings of the runs $\rho_{1}\rho_{2}$ and
$\rho_{2}\rho_{1}$).

We consider the set of runs
$\sigma_{k}=\frac{k}{n}\rho_{1}+\frac{n-k}{n}\rho_{2}$ and look at the first
transition occurring at a different date in $\rho_{1}$ and $\rho_{2}$ (call
its index $m$), assuming wlog it occurs earlier in $\rho_{1}$ and let us call
$\tau$ the difference between the date of $m$-th event in $\rho_{2}$ and in
$\rho_{1}$. If $k>j$, in $\sigma_{j}$, the $m$th event cannot be matched in
$\sigma_{k}$ with a time difference smaller than $\tau/n$, implying that
$d(\sigma_{j},\sigma_{k})\geq\vec{d}(\sigma_{j},\sigma_{k})\geq\tau/n$. Now,
considering arbitrary repetitions, we define the language
$S_{n}\triangleq\left(\left(\mathop{word}(\sigma_{k})\right)_{k=1..n}\right)^{*}$).
We remark there is also a distance of at least $\tau/n$ between any two words
of $S_{n}$: indeed the factors $\sigma_{k}$ having all the same duration, the
$i|\pi|+m$th letter of a word cannot be matched with any letter of index
smaller than $i|\pi|$ in another word. Also, no letter of index greater than
$(i+1)|\pi|$ can be matched with this letter. Hence $S_{n}$ is $\tau/n$
separated. So, for any arbitrary $\varepsilon$ (smaller than $\tau$), there is
an $\varepsilon$-separated subset of $L(\bar{\pi}^{*})_{T}$ of size
$\left\lfloor\frac{\tau}{\varepsilon}\right\rfloor^{\lfloor\frac{T}{\tau(\rho_{1})}\rfloor}$.

Using Lem. A.15, it follows this is also true of $L(\pi^{*})_{T}$.

Prop. 3.8 follows immediately.

##  Appendix D -hardness is not so hard

See 5 We prove here only the -hardness of the three problems, denoted , and .
membership is proved in Sect. 5.

######  Proof D.1.

We proceed by reduction from the following -complete problem [1]:

> : given a DTA $\mathcal{A}$ and two locations $p,q$, does there exist a run
> from state $(p,0)$ to location $q$?

From an instance of we build two DTA $\mathcal{B}$ and $\mathcal{C}$ as
follows:

  * •

$\mathcal{B}$ is obtained from $\mathcal{A}$ by adding one more location $f$,
and two edges $q\to f$ and $f\to f$ with a new label $d$, no reset and the
guard true. The initial condition $I(p)$ is $x=0$, the final condition $F(f)$
is true, and all the other initial and final conditions are false.

  * •

$\mathcal{C}$ is obtained from $\mathcal{B}$ by adding one more location $s$,
and two edges $(s,s,d,x_{1}>1,\\{x_{1}\\})$, $(s,p,d,x_{1}=1,X)$ where $X$ is
the set of clocks in $\mathcal{A}$. The initial state is $I(s)=(x=0)$, the
final ones are $F(f)=F(s)=\text{{true}}$.

By construction

  * •

whenever $\myreach(\mathcal{A},p,q)$, both automata $\mathcal{B}$ and
$\mathcal{C}$ are obese: indeed, accepting runs can traverse $\mathcal{A}$
from $p$ to $q$ and then go to the obese loop on location $f$;

  * •

otherwise, $\mathcal{B}$ has empty language, and $\mathcal{C}$ is normal:
indeed, the former automaton has no accepting run, and the latter can loop on
$s$ producing a normal language.

Thanks to the polynomial reduction $(\mathcal{A},p,q)\mapsto\mathcal{B}$ we
have $\myreach\preceq\Obese$ and $(\neg\myreach)\preceq\Meager$. The other
reduction $(\mathcal{A},p,q)\mapsto\mathcal{C}$ yields
$(\neg\myreach)\preceq\Normal$. Thus the three problems , and are -hard.

##  Appendix E Extending to more general automata

See 5.2

######  Proof E.1 (Proof sketch).

Given a non-deterministic timed automaton $\mathcal{B}$ (without
$\epsilon$-transitions) with alphabet $\Sigma$, it is always possible to
relabel its transitions with a larger alphabet $\Gamma$ to make it
deterministic (for example choosing distinct letters for each transition), let
us call this deterministic automaton $\mathcal{A}$. It holds that
$L(\mathcal{B})=\mu(L(\mathcal{A}))$, where $\mu$ is a letter-to-letter
renaming from $\Gamma$ to $\Sigma$. Thm. 5 applies to $\mathcal{A}$, and we
claim that $L(\mathcal{B})$ belongs to the same class as $L(\mathcal{A})$.

To prove the claim we notice first that if $\mathcal{N}$ is an
$\varepsilon$-net for $L_{T}(\mathcal{A})$, then $\mu(\mathcal{N})$ is a
smaller $\varepsilon$-net for $L_{T}(\mathcal{B})$, hence

$\mathcal{BH}(L(\mathcal{B}))\leq\mathcal{BH}(L(\mathcal{A})).$ (7)

if $\mathcal{A}$ is meager,

then $\mathcal{B}$ is also meager by virtue of (7);

if $\mathcal{A}$ is obese,

then it is structurally obese by Thm. 4, and thus the proof of Prop. 4.6 can
be applied, yielding one cycle $\pi$ in $\mathcal{A}$ and a big
$\varepsilon$-separated subset $\mathcal{S}\subset
L_{T,\pi^{*}}(\mathcal{A})$. Since all elements of $S$ follow the same cycle,
the restriction of $\mu$ to $S$ is injective, moreover $\mu(S)$ is also a big
$\varepsilon$-separated subset in $L_{T}(\mathcal{B})$, thus $\mathcal{B}$ is
obese.

if $\mathcal{A}$ is normal,

then by (7) $\mathcal{BH}(\mathcal{B})=O(\log 1/\varepsilon)$. On the other
hand, $\mathcal{A}$ is not structurally meager, and the proof of Prop. 3.8
yields a big $\varepsilon$-separated subset along one cycle. Similarly to the
previous case this implies that $L_{T}(\mathcal{B})$ is big enough:
$\Omega(\log 1/\varepsilon)$.

##  Appendix F Completing the proof of the last theorem

See 6 The only missing element in the proof sketch in Sect. 5.2 concerned the
incompatibility of obesity Type I with thinness.

######  Proof F.1.

Consider a thick automaton, with its forgetful cycle $\pi$. If its orbit has a
single vertex, since $\pi$ has a non-punctual transition it can be realized by
several runs, hence the only edge of $\gamma_{f}(\pi)$ is $\mathbf{wide}$.
Otherwise, $\gamma(\pi)$ has a complete SCC of size at least 2, and then all
its vertices have $\mathbf{wide}$ self-loops in $\gamma_{f}(\pi^{2})$.

Now consider an automaton with structurally obese cycle $\pi$ of Type I. By
definition, $\gamma_{d}(\pi)$ has both an $\mathbf{instant}$ and a
$\mathbf{slow}$ self-loop. According to Lem. B.8, $\pi$ must be forgetful and
the automaton cannot be thin.