\section{Introduction}

A numeration system for representing nonnegative integers as well as real
numbers in a certain interval was proposed in \cite{MR1020484}.
It is based on right-infinite fixed points of substitutions.
Dumont-Thomas numeration system was later explained by
so-called prefix-suffix automata associated to a primitive substitution
\cite{MR1879663}.
It is related to the order of a Bratteli Vershik
diagram and its natural successor map \cite{zbMATH00219514,MR1322556,MR3791491}.
Their main motivation was
to prove that every dynamical system
generated by a substitution of Pisot type on $d$ letters admits as a
topological factor a minimal translation on the torus $\mathbb{T}^{d-1}$
\cite{MR1852097}. As a consequence, we obtain a numeration system representing the
elements of $\mathbb{T}^{d-1}$ by infinite paths in the prefix-suffix automaton,
see \cite{MR1970385}.

Note that the Dumont-Thomas numeration system for $\mathbb{N}$ is deduced by
considering the cylinders of finite length words \cite[Corollary
6.2]{MR1879663}.
It was also generalized to numeration systems for $\mathbb{N}$ \cite{MR1799066}
and for real numbers in an interval \cite{zbMATH01748010}
associated to arbitrary regular languages,
see also \cite[\S 7]{MR1905123}, \cite[\S 4]{MR2290784},
\cite{MR2282862}, \cite[\S 3]{MR2742574}, \cite{MR2799274}.
A recent article extending Dumont-Thomas also concerns $\beta$-numeration of
real numbers in an interval \cite{MR4143682}.

A very general framework was proposed recently to
extend the Dumont-Thomas numeration system to all integers
based on the notion of coding prescription which allows the image of
letters to be scattered words of nonconsecutive letters \cite{MR3805464}.
The goal of this contribution is to propose a simple extension of Dumont-Thomas
numeration system to all integers in $\mathbb{Z}$.
It is based on two-sided periodic points of a substitution
as opposed to right-infinite fixed points.
Intuitively, it is inspired by the adic transformation of a Bratteli-Vershik
diagram in the sense that we want to represent the integer $-n$ by a finite
word which is the $n$-th predecessor of $0$ under the successor map. The proofs
provided here are simple and follow as much as possible the approach originally
proposed by Dumont-Thomas \cite{MR1020484}.
The motivation for this work comes from the study of substitutive Wang tilings
of the plane in general (a preliminary work was done in \cite{MR4364231}) where
a theory of substitutive numeration systems for $\mathbb{Z}^2$ is needed.

\section{Preliminaries}

An \emph{alphabet} $A$ is a finite set and its elements $a\in A$
are called $\emph{letters}$.
A \emph{finite word} $u = u_0 u_1 \cdots u_{n-1}$ is a concatenation of letters
$u_i \in A$ for every $i\in \{0,1,\dots,n-1\}$ and $|u|$ denotes its \emph{length}.
The \emph{empty word} is denoted $\varepsilon$.
The set of all finite words over alphabet $A$ is denoted $A^*$
and the set of all nonempty words over alphabet $A$ is denoted
$A^+ = A^*\setminus \{\varepsilon\}$.
The set $A^*$ with concatenation as the monoid operation
and $\varepsilon$ as the neutral element
forms a monoid.

A \emph{morphism} over $A$ is a map $\eta:A^* \to A^*$
such that $\eta(uv) = \eta(u)\eta(v)$  for all words $u, v \in A^*$.
A \emph{substitution} $\eta:A^* \to A^*$ is a morphism such that
$\eta(a)\in A^+$ is nonempty
for every $a\in A$
and there exists $a\in A$ such that $\lim_{n\to +\infty} |\eta^n(a)| = +\infty$.
A morphism $\eta$ is said \emph{primitive} if
there exists $k\in\mathbb{N}$ such that
for every $a,b\in A$
the letter $a$ appears in $\eta^k(b)$.

We call $u_0 u_1 u_2 \cdots \in A^{\mathbb{Z}_{\geq 0}}$ a \emph{right-infinite word}
and $ \cdots  u_{-3} u_{-2} u_{-1} \in A^{{\mathbb{Z}_{< 0}}}$ a \emph{left-infinite word}.
We call $u\in A^{\mathbb{Z}}$ a \emph{two-sided word} and
we separate by a dot its elements $u_{-1}$ and $u_0$ to indicate the origin, i.e.,
$u = \cdots u_{-3} u_{-2} u_{-1} . u_{0} u_1 u_2 \cdots$.

Substitutions can be applied naturally to two-sided words $u\in A^{\mathbb{Z}}$ by setting
\[
\eta(\dots u_{-3} u_{-2} u_{-1} . u_0 u_1 u_2 \cdots)
= \cdots\eta(u_{-3}) \eta(u_{-2}) \eta(u_{-1}) .\eta(u_0) \eta(u_1) \eta(u_2) \cdots.
\]
Let $\mathbb{D}\in\{\mathbb{Z},{\mathbb{Z}_{\geq 0}},{\mathbb{Z}_{< 0}}\}$.
A word $u\in A^\mathbb{D}$ is called \emph{periodic point} of the substitution
$\eta$ if there exists an integer $p\geq 1$ such that $\eta^p(u)=u$.
Such an integer $p$ is called a \emph{period}.
A periodic point with a period $p=1$ is called a \emph{fixed point} of $\eta$.
The set of periodic points of $\eta$ is denoted
$\Per_\mathbb{D}(\eta)=\{u\in A^\mathbb{D} \mid \eta^p(u)=u\}$.
Since we are mostly interested in two-sided words in this contribution,
we omit the domain when $\mathbb{D}=\mathbb{Z}$ and we write
$\Per(\eta)=\Per_\mathbb{Z}(\eta)$.

A word $u\in \Per(\eta)$ of period $p$ is of the form
$u = \lim_{n\to +\infty} \eta^{pn}(b).\eta^{pn}(a)$
where $a,b\in A$ are letters such that $\eta^p(a) =au$ and
$\eta^p(b) =vb$ for some nonempty words $u,v\in A^+$.
In this case, we call $s = b.a$
the \emph{seed} of
the periodic point $u$.

Let $u=u_0 u_1 \cdots\in\Per_\mathbb{N}(\eta)$ with $u_0=a$.
The previous terminology is inspired by \cite{MR1879663}
where a prefix-suffix automaton is associated with $\eta$.
However, for our goal an automaton associated with $\eta$
as in \cite{MR2742574} is sufficient.
Let $\mathcal{D}=\left\{0,...,\max_{c\in A}|\eta(c)|-1\right\}$ be an alphabet.
The deterministic finite automaton with output (DFAO)
associated to the substitution $\eta$ and letter $a$ is
the 5-tuple,
$\mathcal{A}_{\eta,a} = (A,\mathcal{D},\delta,a,A),$
where the transition function $\delta:A\times \mathcal{D} \rightarrow A$
is a partial function
such that $\delta(b,i)=c$
if and only if
$c=w_i$ and $\eta(b)=w_0\dots w_{|\eta(b)|-1}$.
We denote by $\mathcal{L}(\mathcal{A}_{\eta,a})$ the words
accepted by the automaton $\mathcal{A}_{\eta,a}$
and for $q\in\mathbb{N}$ we denote $\mathcal{L}_q(\mathcal{A}_{\eta,a})$
the set of words $w\in\mathcal{L}(\mathcal{A}_{\eta,a})$ such that $|w|=q$.

\section{Dumont-Thomas numeration system for $\mathbb{N}$}

In this section, we recall Dumont-Thomas numeration system for $\mathbb{N}$ which was
based on  substitutions having a right-infinite fixed point \cite{MR1020484}.
It uses the definition of admissible sequences.

\begin{definition}[admissible sequence]
    {\rm\cite{MR1020484}}
Let $a\in A$ be a letter, $k$ an integer and, for each integer $i$, $0\leq i\leq k$,
$(m_i,a_i)$ be an element of $A^*\times A$. We say that the finite sequence
$(m_i,a_i)_{i=0,\dots,k}$ is \emph{admissible} if and only if, for all $i$,
$1\leq i\leq k$,
$m_{i-1}a_{i-1}$ is a prefix of $\eta(a_i)$. We say that this sequence is
\emph{$a$-admissible} if it is admissible and, moreover, $m_ka_k$ is a prefix of
$\eta(a)$.
\end{definition}

Dumont-Thomas proved the following result which we rewrite in our notation.

\begin{theorem}\label{thm:dumont-thomas}
    {\rm\cite[Theorem 1.5]{MR1020484}}
    Let $a\in A$ and let $\eta:A^*\to A^*$ be a substitution.
    Let $u=\eta(u)$ be a right-infinite fixed point of $\eta$ with $u_0 = a$.
    For every integer $n\geq1$,
    there exists a unique integer $k=k(n)$ and a unique sequence
    $(m_i,a_i)_{i=0,\dots,k}$ such that
    \begin{itemize}
        \item this sequence is $a$-admissible and $m_k\neq\varepsilon$,
        \item $u_0u_1\cdots u_{n-1} = \eta^k(m_k) \eta^{k-1}(m_{k-1}) \cdots \eta^0(m_0)$.
    \end{itemize}
\end{theorem}

The proof of the above theorem was based on the following lemmas
which we cite here as we need them in what follows.

\begin{lemma}\label{lem:admissible-sequence_sum}
    {\rm\cite[Lemma 1.1]{MR1020484}}
    Let $k$ be an integer. If
    $(m_i,a_i)_{i=0,\dots,k}$ is an admissible sequence, then
    $\sum_{j=0}^k |\eta^j(m_j)| < |\eta^k(m_k a_k)|$.
\end{lemma}

\begin{lemma}\label{lem:unique_admissible_sequence}
    {\rm\cite[Lemma 1.3]{MR1020484}}
    Let $k$ be an integer. Let $b\in A$,
    $(m_i,a_i)_{i=0,\dots,k}$ and
    $(m'_i,a'_i)_{i=0,\dots,k}$ be two $b$-admissible sequences
    and $n$ be an integer such that
    \[
        n = \sum_{j=0}^k |\eta^j(m_j)| = \sum_{j=0}^{k} |\eta^j(m'_j)|.
    \]
    Then for every $i$, $0\leq i \leq k$, we have $(m_i,a_i) = (m'_i, a'_i)$.
\end{lemma}

\begin{lemma}\label{lem:prefix_recursion}
    {\rm\cite[Lemma 1.4]{MR1020484}}
    Let $\eta\colon A^*\to A^*$ be a substitution.
    Let $\ell\geq 1$ be an integer, $a\in A$ a letter and $m\in A^*$
    a proper prefix of the word $\eta^\ell(a)$.
    Then there exist $(m',a')\in A^*\times A$ and $m''\in A^*$
    such that $m'a'$ is a prefix of $\eta(a)$,
    $m''$ is a proper prefix of $\eta^{\ell-1}(a')$
    and $m = \eta^{\ell-1}(m') m''$.
\end{lemma}

\subsection{Few extensions of Dumont-Thomas results}

In this subsection, we propose few small extensions of Dumont-Thomas lemmas.
Firstly, we observe that admissible sequences are related to automata as follows.

\begin{lemma}\label{lemma:admissible-feed-into-automaton}
    If $(m_i,a_i)_{i=0,\dots,k}$ is a $x$-admissible sequence,
    then
    \[
        a_i=\mathcal{A}_{\eta,x}(|m_{k}|,|m_{k-1}|,\dots,|m_i|), \qquad \text{ for every } i=0,\dots,k.
    \]
\end{lemma}

\begin{proof}
    The proof is done by induction on $i$.
    If $i=k$, then
        $a_i=a_k=\eta(x)[|m_k|]=\mathcal{A}_{\eta,x}(|m_{k}|)$.
    If $i<k$, then
    \begin{align*}
        a_i
        &= \eta(a_{i+1})[|m_i|]
        = \eta\left(\mathcal{A}_{\eta,x}(|m_{k}|,\dots,|m_{i+1}|)\right)[|m_i|]\\
        &= \mathcal{A}_{\eta,x}(|m_{k}|,\dots,|m_{i+1}|,|m_i|). \quad\qed
    \end{align*}
\end{proof}

The following lemma reformulates and strenghtens Lemma 1.2 from
\cite{MR1020484}.
It allows
to conclude that
two admissible sequences are of the same length.

\begin{lemma}\label{lem:intervals-for-sums}
    Let $\eta:A^*\to A^*$ be a substitution and $x\in A$.
    Let $(m_i,a_i)_{i=0,\dots,k}$
    be an $x$-admissible sequence.
    \begin{enumerate}[(i)]
    \item If $m_k \neq \varepsilon$, then
        $  |\eta^{k}(x)|
            \leq \textstyle\sum_{j=0}^k |\eta^j(m_j)|
            <    |\eta^{k+1}(x)|$.
    \item If $m_km_{k-1}\cdots m_{k-p+1} \neq \varepsilon$, then
            $ |\eta^{k-p+1}(x)|
            \leq \textstyle\sum_{j=0}^k |\eta^j(m_j)|
            < |\eta^{k+1}(x)|$.
    \item If $m_k a_k\neq \eta(x)$ and $x$ is a suffix of $\eta(x)$, then
        \[
            -|\eta^{k+1}(x)|
            \leq -|\eta^{k+1}(x)| + \textstyle\sum_{j=0}^k |\eta^j(m_j)|
            <    -|\eta^{k}(x)|.
        \]
    \item If $\eta^{p-1}(m_{k})\eta^{p-2}(m_{k-1})\cdots\eta^0(m_{k-p+1})a_{k-p+1}
        \neq\eta^p(x)$ and $x$ is a suffix of $\eta^p(x)$, then
        \[
            -|\eta^{k+1}(x)|
            \leq -|\eta^{k+1}(x)| + \textstyle\sum_{j=0}^k |\eta^j(m_j)|
            <    -|\eta^{k-p+1}(x)|.
        \]
    \end{enumerate}
\end{lemma}

\begin{proof}
    (i) Since $m_k\neq\varepsilon$, the word $m_k$ starts with letter $x$, thus
    using Lemma~\ref{lem:admissible-sequence_sum}, we have
    \[
        |\eta^{k}(x)|
        \leq |\eta^{k}(m_k)|
            \leq \textstyle\sum_{j=0}^k |\eta^j(m_j)|
            <    |\eta^{k}(m_ka_k)|
            \leq |\eta^{k+1}(x)|.
    \]

    (ii)
    If $m_km_{k-1}\cdots m_{k-p+1} \neq \varepsilon$, then
    the word $w=\eta^{p-1}(m_{k})\eta^{p-2}(m_{k-1})\cdots\eta^0(m_{k-p+1})$
    is nonempty and starts with letter $x$.
    Thus
    \[
        |\eta^{k-p+1}(x)|
        \leq |\eta^{k-p+1}(w)|
            \leq \textstyle\sum_{j=0}^k |\eta^j(m_j)|
            <    |\eta^{k}(m_ka_k)|
            \leq |\eta^{k+1}(x)|.
    \]

    (iii)
    If $m_k a_k\neq \eta(x)$ and $x$ is a suffix of
    $\eta(x)$, and using Lemma~\ref{lem:admissible-sequence_sum}, we get
        \[
            -|\eta^{k+1}(x)|
            \leq -|\eta^{k+1}(x)| + \textstyle\sum_{j=0}^k |\eta^j(m_j)|
            <    -|\eta^{k+1}(x)| + |\eta^{k}(m_ka_k)|
            <    -|\eta^{k}(x)|.
        \]

    (iv)
    Assume $w=\eta^{p-1}(m_{k})\eta^{p-2}(m_{k-1})\cdots\eta^0(m_{k-p+1})a_{k-p+1}
        \neq\eta^p(x)$ and $x$ is a suffix of $\eta^p(x)$.
    Observe that $w$ is a prefix of $\eta^p(x)$
    and $|\eta^{k+1}(x)|
         =|\eta^{k-p+1}(\eta^p(x))|
         \geq |\eta^{k-p+1}(w)| + |\eta^{k-p+1}(x)|$.
        Thus
        \begin{align*}
            -|\eta^{k+1}(x)|
            &\leq -|\eta^{k+1}(x)| + \textstyle\sum_{j=0}^k |\eta^j(m_j)| \\
            &= -|\eta^{k+1}(x)|
            + \textstyle\sum_{j=0}^{k-p} |\eta^j(m_j)|
            + \textstyle\sum_{j=k-p+1}^k |\eta^j(m_j)| \\
            &< -|\eta^{k+1}(x)|
            + |\eta^{k-p}(m_{k-p}a_{k-p})|
            + |\eta^{k-p+1}(w)| - |\eta^{k-p+1}(a_{k-p+1})|\\
            &\leq  -|\eta^{k+1}(x)| + |\eta^{k-p+1}(w)|
             \leq  -|\eta^{k-p+1}(x)|.\qquad\qed
        \end{align*}
\end{proof}

Lemma~\ref{lem:prefix_recursion} can be used to construct
an admissible sequence from a prefix of the image of a letter
under the $p$-th power of a substitution.

\begin{lemma}\label{lem:when-m-prefix-of-eta-p-a}
    Let $\eta:A^*\to A^*$ be a substitution and
    $p\geq 1$ be an integer.
    If $m\in A^*$ and $x\in A$ are such that
    $m$ is a prefix of $\eta^p(x)$, then
    there exists a unique $x$-admissible sequence
    $(m_i,a_i)_{i=0,\dots,p-1}$ such that
    \begin{equation}\label{eq:m-as-product}
        m = \eta^{p-1}(m_{p-1}) \eta^{p-2}(m_{p-2}) \cdots \eta^0(m_0).
    \end{equation}
\end{lemma}

\begin{proof}
    (Unicity)
    Let
    $(m_i,a_i)_{i=0,\dots,p}$ and
    $(m'_i,a'_i)_{i=0,\dots,p}$ be two $x$-admissible sequences satisfying the hypothesis.
    Let
    $k=\max\{i=0,\dots,p\mid m_i \neq\varepsilon\}$
    and
    $k'=\max\{i=0,\dots,p\mid m'_i \neq\varepsilon\}$.
    Then
    \[
            \textstyle\sum_{j=0}^{k} |\eta^j(m_j)|
          = |m|
          = \textstyle\sum_{j=0}^{k'} |\eta^j(m'_j)|.
    \]
    From Lemma~\ref{lem:intervals-for-sums},
    we have
    $ |\eta^{k}(a)| \leq |m| < |\eta^{k+1}(a)|$
    and
    $ |\eta^{k'}(a)| \leq |m| < |\eta^{k'+1}(a)|$,
    so that $k = k'$.
    The unicity of the sequence $(m_i,a_i)$
    follows from Lemma~\ref{lem:unique_admissible_sequence}.

    (Existence)
    We do the proof by induction on $p$.
    If $p=1$, then $m$ is a prefix of $\eta(x)$.
    Let $m_0=m$ and $a_0=x$.
    The length-1 sequence $(m_i,a_i)_{i=0}$ is $x$-admissible
    and satisfies $m=\eta^0(m_0)$.

    Now let $m\in A^*$ and $x\in A$ be such that
    $m$ is prefix of $\eta^{p+1}(x)$.
    From Lemma~\ref{lem:prefix_recursion},
    there exist $(m_p,a_p)\in A^*\times A$ and $m''\in A^*$
    such that $m_pa_p$ is a prefix of $\eta(x)$,
    $m''$ is a proper prefix of $\eta^{p}(a_p)$
    and $m = \eta^{p}(m_p) m''$.
    By the induction hypothesis,
    there exists a $a_p$-admissible sequence
    $(m_i,a_i)_{i=0,\dots,p-1}$ such that
    \[
        m'' = \eta^{p-1}(m_{p-1}) \eta^{p-2}(m_{p-2}) \cdots \eta^0(m_0).
    \]
    Therefore,
    \[
        m = \eta^{p}(m_p) m''
          = \eta^{p}(m_p)\eta^{p-1}(m_{p-1}) \eta^{p-2}(m_{p-2}) \cdots \eta^0(m_0).
    \]
    The extended sequence $(m_i,a_i)_{i=0,\dots,p}$ is $x$-admissible
    since $m_{p-1}a_{p-1}$ is a prefix of $\eta(a_p)$
    and $m_pa_p$ is a prefix of $\eta(x)$.\qquad \qed
\end{proof}

Let $\eta:A^*\to A^*$ be a substitution and
$\mathcal{D}=\left\{0,...,\max_{c\in A}|\eta(c)|-1\right\}$.
Lemma~\ref{lem:when-m-prefix-of-eta-p-a} allows to define
a map for every integer $p\geq 1$ and $x\in A$ as follows
	\[
	\begin{array}{rccl}
        \tail_{\eta,p,x}:&\{0,1,\dots,|\eta^p(x)|-1\} & \to & \mathcal{D}^p\\
		&n & \mapsto & |m_{p-1}|,|m_{p-2}|,\dots,|m_0|.
	\end{array}
	\]
where
$(m_i,a_i)_{i=0,\dots,p-1}$ is the unique $x$-admissible sequence
satisfying Equation~\eqref{eq:m-as-product}
with $m$ being the prefix of length $n$ of $\eta^p(x)$.
The map $\tail_{\eta,p,x}$ will be used in Section~\ref{sec:NS-for-periodic-points}.

\begin{lemma}\label{lem:automaton_q_r}
    Let $\eta:A^*\to A^*$ be a substitution and $p\geq 1$ be an integer.
    Let $x\in A$. Then for every $\ell\in\{0,1,\dots, |\eta^p(x)|-1\}$ we have
    \begin{equation*}
        \eta^p(x)[\ell] = \mathcal{A}_{\eta,x}(\tail_{\eta,p, x}(\ell)).
    \end{equation*}

\end{lemma}

\begin{proof}
    Let $m$ be the prefix of $\eta^p(x)$ of length $\ell$.
    From Lemma~\ref{lem:when-m-prefix-of-eta-p-a},
    there exists a unique $x$-admissible sequence
    $(m_i,a_i)_{i=0,\dots,p-1}$ such that
    \[
        m = \eta^{p-1}(m_{p-1}) \eta^{p-2}(m_{p-2}) \cdots \eta^0(m_0).
    \]
    The word $ma_0$ is a prefix of $\eta^p(x)$, thus
    $\eta^p(x)[\ell]=a_0$.
    From Lemma~\ref{lemma:admissible-feed-into-automaton},
    \[
        \eta^p(x)[\ell]=
        a_0=\mathcal{A}_{\eta,x}(|m_{p-1}|,|m_{p-2}|,\dots,|m_0|)
           =\mathcal{A}_{\eta,x}(\tail_{\eta,p, x}(\ell)).\quad\qed
    \]
\end{proof}

\section{Dumont-Thomas numeration system for $\mathbb{Z}$}

In this section, we prove extensions of
Theorem~\ref{thm:dumont-thomas} to right-infinite and left-infinite periodic
points of substitutions.

\begin{theorem}\label{thm:dumont-thomas-right-p}
    Let $a\in A$ and $\eta:A^*\to A^*$ be a substitution.
    Let $u\in \Per_{{\mathbb{Z}_{\geq 0}}}(\eta)$ with a period $p\geq 1$ such that $u_0 = a$.
    For every integer $n\geq1$,
    there exists a unique integer $k=k(n)$
    such that $p$ divides $k+1$
    and a unique sequence $(m_i,a_i)_{i=0,\dots,k}$ such that
    \begin{enumerate}[(i)]
        \item this sequence is $a$-admissible and
            $m_{k} m_{k-1} \cdots m_{k-p+1}\neq\varepsilon$,
        \item $u_0u_1\cdots u_{n-1}
            = \eta^{k}(m_{k}) \eta^{k-1}(m_{k-1}) \cdots \eta^0(m_0)$.
    \end{enumerate}
\end{theorem}

\begin{proof}
    Let $n\geq 1$ be an integer.
    There exists a unique integer $k\in\mathbb{N}$
    such that $p$ divides $k+1$
    and
    \[
        |\eta^{k-p+1}(a)| \leq n <
        |\eta^{k+1}(a)|.
    \]
    The word $m = u_0u_1\cdots u_{n-1}$ is thus a proper prefix
    of $\eta^{k+1}(a)$.
    From Lemma~\ref{lem:when-m-prefix-of-eta-p-a},
    there exists a unique $a$-admissible sequence
    $(m_i,a_i)_{i=0,\dots,k}$ such that
    \[
        m = \eta^{k}(m_{k}) \eta^{k-1}(m_{k-1}) \cdots \eta^0(m_0).
    \]
    Assume by contradiction that $m_{k} m_{k-1} \cdots m_{k-p+1}=\varepsilon$.
    Then $a_{k-p+1}=a$ and
    from Lemma~\ref{lem:admissible-sequence_sum}, we have
    \[
        n = |m|
        = \textstyle\sum_{j=0}^{k-p}|\eta^j(m_j)|
        < |\eta^{k-p}(m_{k-p})|
        \leq |\eta^{k-p+1}(a_{k-p+1})|,
    \]
    a contradiction.
    Thus $m_{k} m_{k-1} \cdots m_{k-p+1}\neq\varepsilon$.
    \qed
\end{proof}

We now adapt Dumont-Thomas's theorem to the left-infinite periodic points.

\begin{theorem}\label{thm:dumont-thomas-for-left-side-p}
    Let $b\in A$ and $\eta:A^*\to A^*$ be a substitution.
    Let $u\in \Per_{{\mathbb{Z}_{< 0}}}(\eta)$ with a period $p\geq 1$
    such that $u_{-1} = b$.
    For every integer $n\leq -2$,
    there exists a unique integer $k=k(n)$
    such that $p$ divides $k+1$
    and a unique sequence
    $(m_i,a_i)_{i=0,\dots,k}$ such that
    \begin{enumerate}[(i)]
        \item this sequence is $b$-admissible and
            \begin{equation}\label{eq:left-periodic-condition}
                \eta^{p-1}(m_{k})\eta^{p-2}(m_{k-1})\cdots\eta^0(m_{k-p+1})a_{k-p+1}
                \neq\eta^p(b),
            \end{equation}
        \item $u_{-|\eta^{k+1}(b)|}\cdots u_{n-2}u_{n-1}
            = \eta^{k}(m_{k}) \eta^{k-1}(m_{k-1}) \cdots \eta^0(m_0)$.
    \end{enumerate}
\end{theorem}

\begin{proof}
    Let $n\leq -2$ be an integer.
    There exists a unique integer $k\in\mathbb{N}$
    such that $p$ divides $k+1$
    and
    \[
        -|\eta^{k+1}(b)|\leq n  < -|\eta^{k-p+1}(b)|.
    \]
    Therefore the word
    $m = u_{-|\eta^{k+1}(b)|}\cdots u_{n-2}u_{n-1}$ of length
    \[
    |m| = |\eta^{k+1}(b)| + n
        < |\eta^{k+1}(b)| - |\eta^{k-p+1}(b)|
        < |\eta^{k+1}(b)|
    \]
    is a proper prefix of the word $\eta^{k+1}(b)$.
    From Lemma~\ref{lem:when-m-prefix-of-eta-p-a},
    there exists a unique $b$-admissible sequence
    $(m_i,a_i)_{i=0,\dots,k}$ such that
    \[
        m = \eta^{k}(m_{k}) \eta^{k-1}(m_{k-1}) \cdots \eta^0(m_0).
    \]
    By contradiction, assume that \eqref{eq:left-periodic-condition}
    is an equality. Then $a_{k-p+1}=b$ and
    \begin{equation*}
        \begin{aligned}
        |m|

        &= |\eta^{k-p+1}(\eta^p(b))| - |\eta^{k-p+1}(a_{k-p+1})|
          + \textstyle\sum_{j=0}^{k-p}|\eta^{j}(m_{j})|\\
        &\geq |\eta^{k+1}(b)| - |\eta^{k-p+1}(b)|,
        \end{aligned}
    \end{equation*}
    a contradiction. \qed
\end{proof}

\section{Numeration systems for $\mathbb{Z}$ based on periodic points}\label{sec:NS-for-periodic-points}

In this section, we define a numeration system for $\mathbb{Z}$
using the results proved in the previous section.

\begin{definition}[Numeration system]\label{def:rep-not-prolongable}
    Let $\eta:A^*\to A^*$ be a substitution and
    let $u\in\Per(\eta)$.
    Let $\mathcal{D}=\left\{0,...,\max_{c\in A}|\eta(c)|-1\right\}$.
    We define
	\[
	\begin{array}{rccl}
		\rep_{u}:&\mathbb{Z} & \to & \mathcal{D}^*\\
		&n & \mapsto &
		\begin{cases}
            \mathtt{0},|m_{k}|,|m_{k-1}|,\dots,|m_0|               & \text{ if } n \geq 1,\\
			\mathtt{0}                                          & \text{ if } n = 0,\\
			\mathtt{1}                                          & \text{ if } n =-1,\\
			\mathtt{1},|m_{k}|,|m_{k-1}|,\dots,|m_0|               & \text{ if } n \leq -2.
		\end{cases}
	\end{array}
	\]
    where $k=k(n)$ is the unique integer and
    $(m_i,a_i)_{i=0,\dots,k}$ is the unique sequence
    obtained from Theorem~\ref{thm:dumont-thomas-right-p}
    (Theorem~\ref{thm:dumont-thomas-for-left-side-p}) applied on $u|_{\mathbb{Z}_{\geq 0}}$
    ($u|_{\mathbb{Z}_{< 0}}$)
    if $n\geq 1$
    (if $n\leq -2$, respectively).
\end{definition}

\noindent
Note that if $p\in\mathbb{N}$ is a period of $u$,
then it divides $|\rep_{u}(n)|-1$ for every $n\in\mathbb{Z}$.

When $u=\eta^p(u)$ is a periodic point of a substitution $\eta$,
then it is also a fixed point of the substitution $\eta^p$.
Thus, Theorem~\ref{thm:dumont-thomas} may be used to define a
numeration system for $\mathbb{N}$, but it
leads to a much larger alphabet size $\#\mathcal{D}$.
One advantage of Definition~\ref{def:rep-not-prolongable} is
that the size of the alphabet $\mathcal{D}$ is independent of the period $p$.

\begin{definition}[quotient, remainder]\label{def:quotient-p}
    Let $\eta:A^*\to A^*$ be a substitution and
    let $u\in\Per(\eta)$.
    Let $n\in\mathbb{Z}\setminus\{-1,0\}$ be an integer
    and $k=k(n)$ be the unique integer and
    $(m_i,a_i)_{i=0,\dots,k}$ be the unique sequence
    obtained from Theorem~\ref{thm:dumont-thomas-right-p}
    (Theorem~\ref{thm:dumont-thomas-for-left-side-p}) applied on $u|_{\mathbb{Z}_{\geq 0}}$
    ($u|_{\mathbb{Z}_{< 0}}$)
    if $n\geq 1$
    (if $n\leq -2$, respectively).
    We define the \emph{$u$-quotient} of $n$ as
    \[
        q=
		\begin{cases}
            |\eta^{k-p}(m_{k}) \eta^{k-p-1}(m_{k-1}) \cdots \eta^0(m_p)|
			            & \text{ if } n \geq 1,\\
            |\eta^{k-p}(m_{k}) \eta^{k-p-1}(m_{k-1}) \cdots \eta^0(m_p)| -|\eta^{k-p+1}(b)|
			            & \text{ if } n \leq -2,
		\end{cases}
    \]
    and the \emph{$u$-remainder} of $n$  as
    $r=|\eta^{p-1}(m_{p-1}) \eta^{p-2}(m_{p-2})\cdots\eta^0(m_0)|$.
\end{definition}

Notice that the $u$-quotient $q$ and $u$-remainder $r$ of an integer
$n\in\mathbb{Z}\setminus\{-1,0\}$ fulfil that if $n \geq1$ then $0\leq q < n$ and if $n \leq
-2$ then $-1 \geq q > n$. Consequently, $|q| < |n|$.  Also, if $\eta$ is $d$-uniform,
then the $u$-quotient and $u$-remainder of $n$ correspond to the quotient and
remainder of the division of $n$ by~$d^p$.

\begin{remark}
Note that if we know the $u$-quotient $q$ and the $u$-remainder $r$, we
can recover the sequence $|m_{p-1}|,|m_{p-2}|,\cdots,|m_0|$.
Indeed, it is equal to $\tail_{\eta,p,u_q}(r)$.
\end{remark}

\begin{lemma}\label{lem:rep_recurrence-p}
    Let $\eta:A^*\to A^*$ be a substitution and
    $u\in \Per(\eta)$ with period $p\geq 1$.
    Let $n\in\mathbb{Z}\setminus\{-1,0\}$ be an integer.
    If $q\in\mathbb{Z}$ is the $u$-quotient
    and $r\in\mathbb{N}$ is the $u$-remainder
    of $n$, then
    \begin{equation*}
        u_n  =  \eta^p(u_q)[r]
        \quad
        \text{ and }
        \quad
        \rep_{u}(n) = \rep_{u}(q)\cdot \tail_{\eta,p,u_q}(r).
    \end{equation*}
\end{lemma}

\begin{proof}
    Let $n\in\mathbb{Z}\setminus\{-1,0\}$
    and let $q$ be the $u$-quotient and $r$ the $u$-remainder of~$n$.
    Let $u\in\Per(\eta)$ and let $a,b\in A$ denote letters such that $u_{-1}=b$ and $u_0=a$.

    Suppose $n\geq 1$.
    From Theorem~\ref{thm:dumont-thomas-right-p},
    there exists a unique $a$-admissible sequence
    $(m_i,a_i)_{i=0,\dots,k}$
    such that
    $u_0 \dots u_{n-1} = \eta^{k}(m_{k}) \dots \eta^0(m_0)$.
    Also $\eta^{k}(m_{k}) \dots \eta^0(m_0)a_0$
    is a prefix of $\eta^{k+1}(a)$ which is a prefix of $u$,
    thus $u_n=a_0$.
    Since $u$ has period $p$, the word
    \[
        \eta^{k-p}(m_{k}) \eta^{k-p-1}(m_{k-1}) \cdots \eta^0(m_p) a_p
    \]
    is a prefix of $\eta^{k+1-p}(a)$ which is a prefix of $u$.
    Thus $a_p=u_q$.
    Since $\eta^{p-1}(m_{p-1})\cdots \eta^{0}(m_{0})a_0$ is a prefix of
    $\eta^p(a_p)$, we deduce that
    $u_n = a_0 = \eta^p(a_p)[r] = \eta^p(u_q)[r]$.

    Suppose $n\leq -2$.
    From Theorem~\ref{thm:dumont-thomas-for-left-side-p},
    there exists a unique $b$-admissible sequence
    $(m_i,a_i)_{i=0,\dots,k}$ such that
    $u_{-|\eta^{k+1}(b)|} \dots u_{n-1}
    = \eta^{k}(m_{k}) \dots \eta^0(m_0)$.
    Also $\eta^{k}(m_{k}) \dots \eta^0(m_0)a_0$
    is a prefix of $\eta^{k+1}(b)$,
    which is a prefix of
    $u_{-|\eta^{k+1}(b)|} \dots u_{-1}$, thus $u_n=a_0$.
    Since $u$ has period $p$, the word
    \[
        \eta^{k-p}(m_{k}) \eta^{k-p-1}(m_{k-1}) \cdots \eta^0(m_p) a_p
    \]
    is a prefix of $\eta^{k+1-p}(a)$ which is a prefix of
    $u_{-|\eta^{k-p+1}(b)|} \dots u_{-1}$, thus $a_p=u_q$.
    Since $\eta^{p-1}(m_{p-1})\cdots \eta^{0}(m_{0})a_0$ is a prefix of
    $\eta^p(a_p)$, we deduce that
    $u_n = a_0 = \eta^p(a_p)[r] = \eta^p(u_q)[r]$.

    To finish the proof for both cases simultaneously, if $n\geq 1$ ($n\leq -2$),
    applying Theorem~\ref{thm:dumont-thomas-right-p}
    (Theorem~\ref{thm:dumont-thomas-for-left-side-p})
    on the $u$-quotient $q$ gives for $\mathtt{d} = \mathtt{0}$ ($\mathtt{d} = \mathtt{1}$)
    $$\rep_{u}(q) = \mathtt{d}, |m_{k}|,|m_{k-1}|,\dots,|m_p|.$$
    As $n\geq 1$ if and only if $q\geq 0$, we have
    \begin{equation*}
        \begin{aligned}
            \rep_{u}(n)
            &=\mathtt{d},\ |m_{k}|,|m_{k-1}|,\dots,|m_p|, |m_{p-1}|, \dots, |m_0| \\
            &= \rep_{u}(q)\cdot |m_{p-1}|, \dots, |m_0|
            = \rep_{u}(q)\cdot \tail_{\eta,p, u_q}(r).
            \qquad \qed
        \end{aligned}
    \end{equation*}
\end{proof}

\section{Periodic points as Automatic Sequences}

Let $\eta: A^*\to A^*$ be a substitution and let $u\in\Per(\eta)$.
Denote $s = (u_{-1},u_0)$
and $\mathcal{D}=\left\{0,...,\max_{c\in A}|\eta(c)|-1\right\}$.
We associate an automaton $\mathcal{A}_{\eta,s}$ with $(\eta,s)$
by adding a new state $\texttt{start}$ and two additional
edges to the automaton $\mathcal{A}_{\eta, a}$ defined in~\cite{MR2742574}.
The automaton $\mathcal{A}_{\eta,s} = (A\cup\left\{\texttt{start}\right\},\mathcal{D},
\delta, \texttt{start}, A)$ has the transition function
$\delta:A\cup\{\texttt{start}\}\to A$ such that
\begin{itemize}
    \item $\delta(\texttt{start},\mathtt{0}) = s_0 =a$, $\quad\delta(\texttt{start},\mathtt{1}) =s_{-1}= b$,
    \item for every $c,d\in A$,
        every $w=w_0 w_1\dots w_{\ell-1}\in A^\ell$ and every $i\in \mathcal{D}$,
        it holds that
        $\delta(c,i)=d$ if and only if $\eta(c)=w$ and $w_i=d$.
\end{itemize}

Examples of automata associated to the Fibonacci substitution are shown in
Figure~\ref{fig:automataZ}.
\begin{figure}[h]
	\begin{center}
		\begin{tikzpicture}[auto]
		\begin{scope}[xshift=-.1cm]

		\node[draw,circle] (A) at (0,0) {$a$};
		\node[draw,circle] (B) at (1.5,0) {$b$};

		\draw[bend left,->] (A) to node {\scriptsize 1} (B);
		\draw[bend left,->] (B) to node {\scriptsize 0} (A);

		\draw[loop left,->] (A) to node {\scriptsize 0} (A);

		\draw[<-] (A) -- ++ (0,1) node[above] {};

		\draw[->] (A) -- ++ (0,-0.5);
		\draw[->] (B) -- ++ (0,-0.5);
		\end{scope}
		\begin{scope}[xshift=3.5cm]

		\node[draw,circle] (A) at (0,0) {$a$};
		\node[draw,circle] (B) at (1.5,0) {$b$};

		\draw[bend left,->] (A) to node {\scriptsize 1} (B);
		\draw[bend left,->] (B) to node {\scriptsize 0} (A);

		\draw[loop left,->] (A) to node {\scriptsize 0} (A);

		\draw[<-] (B) -- ++ (0,1) node[above] {};

		\draw[->] (A) -- ++ (0,-0.5);
		\draw[->] (B) -- ++ (0,-0.5);
		\end{scope}
		\begin{scope}[xshift=7cm]

		\node[draw] (S) at (.75,1.2) {$\texttt{start}$};
		\node[draw,circle] (A) at (0,0) {$a$};
		\node[draw,circle] (B) at (1.5,0) {$b$};

		\draw[bend left=20,->] (A) to node {\scriptsize 1} (B);
		\draw[bend left=20,->] (B) to node {\scriptsize 0} (A);
		\draw[bend right,->] (S) to node[left] {\scriptsize 0} (A);
		\draw[bend left,->] (S) to node[right] {\scriptsize 1} (B);

		\draw[<-] (S) -- ++ (0,.5) node[above] {};

		\draw[loop left,->] (A) to node {\scriptsize 0} (A);

		\draw[->] (A) -- ++ (0,-0.5);
		\draw[->] (B) -- ++ (0,-0.5);
		\end{scope}
		\end{tikzpicture}
	\end{center}
	\caption{Automata $\mathcal{A}_{\varphi,a}$, $\mathcal{A}_{\varphi,b}$ and
		$\mathcal{A}_{\varphi,s}$ for $\varphi:a\mapsto ab,b\mapsto a$ and $s=b.a$.}
	\label{fig:automataZ}
\end{figure}

The automaton $\mathcal{A}_{\eta,s}$
is related to the usual automata
$\mathcal{A}_{\eta,a}$ and $\mathcal{A}_{\eta,b}$ according to the following equalities
for every $w\in A^*$:
\begin{equation}
\label{eq:automata-relations}
    \mathcal{A}_{\eta,s}(\0w) = \mathcal{A}_{\eta,a}(w)
    \qquad
    \text{and}
    \qquad
    \mathcal{A}_{\eta,s}(\1w) = \mathcal{A}_{\eta,b}(w).
\end{equation}
Also if $\mathcal{A}_{\eta,s}(w) = a$ for some $w\in A^+$, then
for every $u\in A^*$
\begin{equation}
\label{eq:automata-relations-2}
    \mathcal{A}_{\eta,a}(u) = \mathcal{A}_{\eta,s}(wu).
\end{equation}

A theorem of Cobham \cite{MR457011} says that
a sequence $u=(u_n)_{n\geq0}$ is $k$-automatic
with $k\geq2$
if and only if it is the image,
under a coding, of a fixed point of a $k$-uniform morphism
\cite[\S 6]{MR1997038}.
It was extended to non-uniform morphisms \cite{zbMATH01916667},
see also
\cite[\S 3]{MR2742574}.
The following extends the above results to the case of two-sided periodic
points of non-uniform substitutions.

\begin{theorem}\label{th:periodic_point_automatic}
    Let $\eta:A^*\to A^*$ be a substitution.
    Let $u\in \Per(\eta)$ and denote $s = (u_{-1},u_0)$.
	Then for every $n\in\mathbb{Z}$
	\[
		u_n = \mathcal{A}_{\eta,s}(\rep_{u}(n)).
	\]
\end{theorem}
\begin{proof}
    If $n \in\{0,-1\}$ then by definition
    we have
    $u_n = s_n = \mathcal{A}_{\eta,s}(\rep_{u}(n))$.

    Let $n \in\mathbb{Z}\setminus \{0,-1\}$.
    Induction hypothesis: for every $m\in\mathbb{Z}$ such that $|m| < |n|$
	it holds that $x_m = \mathcal{A}_{\eta,s}(\rep_{u}(m))$.
	Let $q$ be the $u$-quotient and $r$ the $u$-remainder
	of $n$. As $|q| < |n|$, $q$ fulfils the induction hypothesis, i.e.,
    $u_q=\mathcal{A}_{\eta,s}(\rep_{u}(q))$.
    From Lemma~\ref{lem:rep_recurrence-p} we have
	$u_n  = \eta^p(u_q)[r]$ and
    $\rep_{u}(n) = \rep_{u}(q)\cdot\tail_{\eta,p,u_q}(r)$.
    Using Lemma~\ref{lem:automaton_q_r} and
    Equation~\eqref{eq:automata-relations-2}, we have
	\begin{equation*}
		\begin{aligned}
		u_n &= \eta^p(u_q)[r]
             = \mathcal{A}_{\eta,u_q}(\tail_{\eta,p,u_q}(r)) \\
            &= \mathcal{A}_{\eta,s}(\rep_{u}(q)\cdot \tail_{\eta,p,u_q}(r))
			 = \mathcal{A}_{\eta,s}(\rep_{u}(n)).\qquad \qed
		\end{aligned}
	\end{equation*}
\end{proof}

\section{Numeration systems for $\mathbb{Z}^d$ based on periodic points}\label{sec:NS-for-Zd}

A numeration system for $\mathbb{Z}^d$ can be deduced from the numeration system for
$\mathbb{Z}$ based on a periodic point. Since not all integers are represented by words
of the same length, we propose here a way to pad them to a common length.

Let $\eta:A^*\to A^*$ be a substitution and $u\in \Per(\eta)$ with period $p\geq 1$.
Let ${\mathtt{W}_{\min}}$ and ${\mathtt{W}_{\max}}$ be the following minimum and the maximum element
under the $\tail$ map with particular parameters:
\begin{equation*}
\begin{aligned}
    {\mathtt{W}_{\min}} &= \tail_{\eta,p,u_{0}}(0) = \mathtt{0}^p,\\
    {\mathtt{W}_{\max}} &= \tail_{\eta,p,u_{-1}}(|\eta^p(u_{-1})|-1).
\end{aligned}
\end{equation*}
The words ${\mathtt{W}_{\min}}$ and ${\mathtt{W}_{\max}}$ play the role of neutral words in the
numeration system as illustrated in the next lemma.

\begin{lemma}
    Let $\eta:A^*\to A^*$ be a substitution.
    Let $u\in \Per(\eta)$ with period $p\geq 1$ and denote $s = (u_{-1},u_0)$.
    Let $w\in\mathcal{L}(\mathcal{A}_{\eta,s})$. Then
    \[
		\mathcal{A}_{\eta,s}(w) =
        \begin{cases}
            \mathcal{A}_{\eta,s}(\mathtt{0} ({\mathtt{W}_{\min}})^* v)
            & \text{ if } w=\mathtt{0} v,\\
            \mathcal{A}_{\eta,s}(\mathtt{1} ({\mathtt{W}_{\max}})^* v)
            & \text{ if } w=\mathtt{1} v.
        \end{cases}
    \]
\end{lemma}

\begin{proof}
    It holds that
    $\mathcal{A}_{\eta,s}(u_0, \mathtt{0}^p) = u_0$
    and $\mathcal{A}_{\eta,s}(u_{-1}, {\mathtt{W}_{\max}}) = u_{-1}$. \qed
\end{proof}

It is useful to pad words to a certain length using neutral words as follows
using a pad function.
Let $s = (u_{-1}, u_0)$.
Let $w\in\mathcal{L}_{\ell p+1}(\mathcal{A}_{\eta,s})$ for some $\ell\in\mathbb{N}$.
Let $t\in\mathbb{N}$ such that $t\geq |w|$ and $t \bmod p = 1$.
    We define
    \[
        \pad_t(w)
        =
        \begin{cases}
            \mathtt{0} ({\mathtt{W}_{\min}})^m v  & \text{ if } w=\mathtt{0} v,\\
            \mathtt{1} ({\mathtt{W}_{\max}})^m v  & \text{ if } w=\mathtt{1} v
        \end{cases}
    \]
where $m=(t-|w|)/p$.
The padding map can be used to pad words so that they all
have the same length. For instance, it allows to represent coordinates in
$\mathbb{Z}^d$ in dimension $d\geq1$.

\begin{definition}[Numeration system for $\mathbb{Z}^d$]
	Let ${\boldsymbol{n}}=(n_1,n_2,\dots,n_d)\in\mathbb{Z}^d$.
	We define
	\[
	\rep_u({\boldsymbol{n}})=\left(
	\begin{array}{c}
        \pad_t(\rep_u(n_1))\\
        \pad_t(\rep_u(n_2))\\
        \dots\\
        \pad_t(\rep_u(n_d))
	\end{array}
	\right)
    \in\{\mathtt{0},\mathtt{1}\}^d(\mathcal{D}^d)^*
	\]
    where $t=\max\{|\rep_u(n_i)|\colon 1\leq i\leq d\}$.
\end{definition}

\section{A Total Order}

The radix order is a total order such that $u <_{rad} v$ if and only if
    $|u| < |v|$ or $|u| = |v|$ and $u <_{lex} v$.
We define reversed-radix order as a total order such that $u <_{rev} v$ if and only if
    $|u| > |v|$ or $|u| = |v|$ and $u <_{lex} v$.
We define a total order on $\{\mathtt{0},\mathtt{1}\}\mathcal{D}^*$
and we show that $\rep_{u}$ is an increasing bijection with respect to it.
\begin{definition}[total order $\prec$]\label{def:order}
    For every $u,v \in \{\mathtt{0},\mathtt{1}\}\mathcal{D}^*$,
	we define $u \prec v$ if and only if
	\begin{itemize}
		\item $u\in \mathtt{1} \mathcal{D}^*$ and $v\in \mathtt{0} \mathcal{D}^*$, or
        \item $u,v \in \mathtt{0} \mathcal{D}^*$ and $u <_{rad} v$, or
        \item $u,v \in \mathtt{1} \mathcal{D}^*$ and $u <_{rev} v$.
	\end{itemize}
\end{definition}

\begin{proposition}\label{prop:rep-u-is-increasing}
    Let $\eta:A^*\to A^*$ be a substitution and
    let $u\in\Per(\eta)$ with period $p\geq 1$ and the seed~$s$.
    The map
    $\rep_{u}:\mathbb{Z}  \to  \bigcup_{\ell\in\mathbb{N}}
    \mathcal{L}_{\ell p+1}(\mathcal{A}_{\eta,s}) \setminus \{\mathtt{0}{\mathtt{W}_{\min}}, \mathtt{1}{\mathtt{W}_{\max}}\} \mathcal{D}^*$ is
    an increasing bijection
    with respect to the order $\prec$.
\end{proposition}

The proof of Proposition~\ref{prop:rep-u-is-increasing}
is ommited and will be included in an extended version of this article.
It follows the proof of similar results, see
\cite[\S 5]{MR1879663} and \cite[\S 4]{MR2290784}.
In some other work on numeration systems, such increasing bijection
is not a consequence, but rather a hypothesis.
For example, a bijection $\mathbb{N}\to\mathcal{L}$ serves as the definition of abstract
numeration systems in \cite{MR1799066}.

\vspace{-5pt}
\section{Examples}
\label{sec:fibo-num-system}

Let
$\psi_{2}: a\mapsto ab, b\mapsto cb, c\mapsto ac$ denote some 2-uniform substitution,
$\psi_{TM}: a\mapsto ab, b\mapsto ba$ denote the Thue-Morse,
$\varphi_{F}: a\mapsto ab, b\mapsto a$ the Fibonacci,
and
$\varphi_{T}: a\mapsto ab, b\mapsto ac, c\mapsto a$ the Tribonacci substitution.
Let also $\rho: a\mapsto ac, b\mapsto cb, c\mapsto c$ be a non-primitive substitution.
We denote $\alpha\in\Per(\psi_{2})$ with the seed $b.a$ and period $1$,
$\beta\in\Per(\psi_{TM})$ with the seed $a.a$ and period $2$,
$\gamma,\delta\in\Per(\varphi_F)$ with the seed $b.a$, $a.a$ and period $2$,
$\tau\in\Per(\varphi_T)$ with the seed $c.a$ and period $3$,
and
$\xi\in\Per(\rho)$ with the seed $b.a$ and period $1$.
The~numeration systems derived from these periodic points
are in Table~\ref{tab:num_systems}.

\begin{table}[h]
\begin{center}
    \scriptsize
    \begin{tabular}{c||r|r|r|r|r|r}
        substitution & 2-uniform & Thue-Morse & Fibonacci & Fibonacci & Tribonacci & non-primitive\\
        images & $(ab,cb,ac)$ & $(ab,ba)$ & $(ab, a)$ & $(ab, a)$ & $(ab,ac,a)$ & $(ac,cb,c)$ \\
        seed & $b.a$ & $a.a$ & $b.a$ & $a.a$ & $c.a$ & $b.a$ \\
        \hline
        $n$ & $\rep_{\alpha}(n)$ & $\rep_{\beta}(n)$ & $\rep_{\gamma}(n)$ & $\rep_{\delta}(n)$ & $\rep_{\tau}(n)$ & $\rep_{\xi}(n)$\\
        \hline
        &&&&\\[-2mm]

        10 & \texttt{01010}  &  \texttt{01010}    &  \texttt{0010010}   & \texttt{0010010} & \texttt{0001011} & \texttt{01000000000} \\
        9  & \texttt{01001}  &  \texttt{01001}    &  \texttt{0010001}   & \texttt{0010001} & \texttt{0001010} & \texttt{0100000000} \\
        8  & \texttt{01000}  &  \texttt{01000}    &  \texttt{0010000}   & \texttt{0010000} & \texttt{0001001} & \texttt{010000000} \\
        7  & \texttt{0111}   &  \texttt{00111}    &  \texttt{01010}     & \texttt{01010}   & \texttt{0001000} & \texttt{01000000} \\
        6  & \texttt{0110}   &  \texttt{00110}    &  \texttt{01001}     & \texttt{01001}   & \texttt{0110}    & \texttt{0100000}    \\
        5  & \texttt{0101}   &  \texttt{00101}    &  \texttt{01000}     & \texttt{01000}   & \texttt{0101}    & \texttt{010000}    \\
        4  & \texttt{0100}   &  \texttt{00100}    &  \texttt{00101}     & \texttt{00101}   & \texttt{0100}    & \texttt{01000}    \\
        3  & \texttt{011}    &  \texttt{011}      &  \texttt{00100}     & \texttt{00100}   & \texttt{0011}    & \texttt{0100}    \\
        2  & \texttt{010}    &  \texttt{010}      &  \texttt{010}       & \texttt{010}     & \texttt{0010}    & \texttt{010}    \\
        1  & \texttt{01}     &  \texttt{001}      &  \texttt{001}       & \texttt{001}     & \texttt{0001}    & \texttt{01}    \\
        0  & \texttt{0}      &  \texttt{0}        &  \texttt{0}         & \texttt{0}       & \texttt{0}       & \texttt{0}       \\
       -1  & \texttt{1}      &  \texttt{1}        &  \texttt{1}         & \texttt{1}       & \texttt{1}       & \texttt{1}       \\
       -2  & \texttt{10}     &  \texttt{110}      &  \texttt{100}       & \texttt{101}     & \texttt{1010}    & \texttt{10}    \\
       -3  & \texttt{101}    &  \texttt{101}      &  \texttt{10010}     & \texttt{100}     & \texttt{1001}    & \texttt{100}    \\
       -4  & \texttt{100}    &  \texttt{100}      &  \texttt{10001}     & \texttt{10101}   & \texttt{1000}    & \texttt{1000}    \\
       -5  & \texttt{1011}   &  \texttt{11011}    &  \texttt{10000}     & \texttt{10100}   & \texttt{1010110} & \texttt{10000} \\
       -6  & \texttt{1010}   &  \texttt{11010}    &  \texttt{1001010}   & \texttt{10010}   & \texttt{1010101} & \texttt{100000} \\
       -7  & \texttt{1001}   &  \texttt{11001}    &  \texttt{1001001}   & \texttt{10001}   & \texttt{1010100} & \texttt{1000000} \\
       -8  & \texttt{1000}   &  \texttt{11000}    &  \texttt{1001000}   & \texttt{10000}   & \texttt{1010011} & \texttt{10000000} \\
       -9  & \texttt{10111}  &  \texttt{10111}    &  \texttt{1000101}   & \texttt{1010101} & \texttt{1010010} & \texttt{100000000} \\
       -10 & \texttt{10110}  &  \texttt{10110}    &  \texttt{1000100}   & \texttt{1010100} & \texttt{1010001} & \texttt{1000000000} \\

    \end{tabular}
\end{center}
    \caption{Numeration systems for periodic points
    $\alpha$, $\beta$, $\gamma$, $\delta$, $\tau$, $\xi$ with given seed.}
    \label{tab:num_systems}
\end{table}

\vspace{-5pt}
\subsection{Two's complement numeration system}

Let $\Sigma = \{\mathtt{0},\mathtt{1}\}$.
In the two's complement representation of integers
the value of a binary word $w=w_{k-1} w_{k-2}\cdots w_0\in\Sigma^{k}$
is $\val_{2c}(w) = \sum_{i=0}^{k-1}w_i 2^i - w_{k-1}2^{k}$, see \cite[\S 4.1]{MR3077153}.
For every $n\in\mathbb{Z}$ there exists a unique word
$w\in\Sigma^+\setminus \left( \mathtt{0}\0\Sigma^* \cup \mathtt{1}\1\Sigma^* \right)$
such that $n=\val_{2c}(w)$.
The word $w$ is called the \emph{two's complement representation} of the integer $n$,
and we denote it by $\rep_{2c}(n)$.
It can be shown that the map
$\rep_{2c}:\mathbb{Z}\to \Sigma^+\setminus \left( \mathtt{0}\0\Sigma^* \cup \mathtt{1}\1\Sigma^* \right)$
is an increasing bijection with respect to the  order~$\prec$.
This implies the following.

\begin{proposition}\label{prop:rep_equality_2c}
    If $\alpha=\psi(\alpha)$ is a two-sided fixed point for some $2$-uniform
    substitution $\psi$, then $\rep_{\alpha}=\rep_{2c}$.
\end{proposition}

\vspace{-5pt}
\subsection{Fibonacci's complement numeration system}

In what follows, the Fibonacci sequence
$(F_n)_{n\geq 0}$,
$F_{n} = F_{n-1} + F_{n-2}$, for all $n \geq 2$,
is defined with the initial conditions
$ F_0 = 1$, $F_1 = 2$.
We denote $\Sigma = \{\mathtt{0},\mathtt{1}\}$.

In \cite{2205.02574}, the Fibonacci's complement numeration system for both nonnegative
and negative integers was defined
from the value map $\val_{\Fcal c}:\Sigma^*\to\mathbb{Z}$
defined for every binary word
$w=w_{k-1}\cdots w_0\in\Sigma^{k}$ as
    $\val_{\Fcal c}(w)
    = \sum_{i=0}^{k-1}w_i F_{i} - w_{k-1}F_{k}$.
It is an analog of the two's complement value map $\val_{2c}$,
using Fibonacci numbers instead of powers of 2.
It was proved in \cite{2205.02574} that
for every $n\in\mathbb{Z}$ there exists a
unique odd-length word
$w\in L=\Sigma(\Sigma\Sigma)^*\setminus
    \left( \Sigma^*11\Sigma^* \cup 000\Sigma^* \cup 101\Sigma^*\right)$
such that $n=\val_{\Fcal c}(w)$.
It defines the map
$\rep_{\Fcal c}:\mathbb{Z}\to L$ by the rule $n\mapsto w$.

We can show that the numeration system obtained from the two-sided Fibonacci
word is Fibonacci's complement numeration system introduced in~\cite{2205.02574}.

\begin{proposition}\label{prop:rep_equality}
	Let $\varphi_F:a\mapsto ab,b\mapsto a$ be the Fibonacci substitution
    and let $\gamma\in\Per(\varphi_F)$ with the seed $s = b.a$.
    Then $\rep_{\gamma}=\rep_{\Fcal c}$.
\end{proposition}

\begin{proof}
    We observe
    \begin{equation}\label{eq:equality_languages}
        \begin{aligned}
        L

            &= (\mathtt{0}(\mathcal{L}(\mathcal{A}_{\varphi_F,a})\setminus\mathtt{0}\0\Sigma^*)\cup
        \mathtt{1}(\mathcal{L}(\mathcal{A}_{\varphi_F,b})\setminus\mathtt{0}\mathtt{1}\Sigma^*))
        \cap \Sigma(\Sigma\Sigma)^*\\
            &= \mathcal{L}(\mathcal{A}_{\eta,s}) \setminus \{\mathtt{0}{\mathtt{W}_{\min}}, \mathtt{1}{\mathtt{W}_{\max}}\} \mathcal{D}^*
        \cap \Sigma(\Sigma\Sigma)^*\\
        \end{aligned}
    \end{equation}
    From \cite{2205.02574}, the map $\rep_{\Fcal c}$ is an increasing bijection $\mathbb{Z} \to
    L$ with respect to the order $\prec$.

    By Proposition~\ref{prop:rep-u-is-increasing} and
    Equation~\eqref{eq:equality_languages},
    $\rep_{\gamma}$ is an
    increasing bijection $\mathbb{Z}\to L$ with respect to the order $\prec$.
    Moreover,
    $\rep_{\gamma}(0) = \mathtt{0} = \rep_{\mathcal{F} c}(0)$.
    Since
    there is a unique inscreasing bijection
    $\mathbb{Z}\to L$ such that $0\mapsto\mathtt{0}$,
    $\rep_{\Fcal c} = \rep_{\gamma}$. \qed
\end{proof}

\subsubsection{Acknowledgements.}
This work was partially funded in France by
ANR CODYS (ANR-18-CE40-0007) and ANR IZES (ANR-22-CE40-0011).
The second author acknowledges financial support by the Barrande fellowship programme
and the  Grant Agency of Czech Technical University in Prague
(SGS20/183/OHK4/3T/14).

\bibliographystyle{alpha}


\section{Introduction}\label{sec:introduction}

RIS is a promising low-cost and low-power \textit{physical layer} (PHY) technology to enable sustainable wireless networks. This technology can produce controllable anomalous reflection of the incoming signal to create hot spots in areas of interest in the communication cell without any power amplifier (PA), consuming much less energy than common active PHY technologies \cite{liaskos2018}.
On the matter of EE, it is shown in \cite{huang2019} that RIS-assisted networks can achieve up to a threefold increase in EE when compared with networks assisted by multiple-antenna amplify-and-forward relays.
This benefit on EE is particularly favorable for IoT networks, which need to achieve low-power consumption and extended coverage to serve hundreds of battery-powered MTDs. In this sense, in \cite{cao2022, croisfelt2022}, efficient random access protocols are proposed for RIS-assisted networks, introducing frameworks to coordinate the optimization of the RIS reflecting coefficients with the device transmissions.
Moreover, in \cite{souza2022}, the EE of the random access channel in a RIS-assisted IoT network is evaluated, revealing that simultaneously optimizing the RIS setup and the transmission protocol is paramount to attain competitive EE and throughput combined with low-power consumption.

In this article, we study how RISs can improve the EBL of MTDs in IoT networks, focusing on the PHY aspects.
Firstly, we derive an expression for the required transmit power to attain a target SNR considering a channel model that accounts for the RIS discretization into sub-wavelength reflecting elements \cite{croisfelt2022}. Secondly, we develop an expression for the EBL of the MTDs, revealing that the numbers of reflecting elements and reflecting angle configurations at the RIS have significant impact on both system EE and network coverage.
Differently from the work \cite{souza2022}, in this article we focus on the EE problem exclusively at the devices-side, which needs more attention since the IoT devices are powered by limited-capacity batteries that are in general expensive and difficult to replace.
Numerical evaluations demonstrate that the RIS can significantly improve the EBL of the MTDs by reducing the transmit power. Nevertheless, since the EBL is simultaneously limited by the number of RIS elements and configurations, the RIS setup must be carefully designed to achieve energy-efficient networks that can fully exploit the potential of the RIS.

\section{System Model}\label{sec:system-model}

In this section, we describe the system model. We consider a communication setup as depicted in Fig. \ref{fig:communication-cell-setup}, where the single-antenna MTDs are connected with the single-antenna AP via the reflected path produced by the RIS, since the direct radio links between the AP and the MTDs are highly attenuated due to a blockage.
In the communication scheme, the AP and MTDs are located at the $xy$-plane. Let $\chi_k = (d_k, \theta_k)$ denotes the position of the $k$-th MTD in the service area, where $d_{\min} \leq d_k \leq d_{\max}$ is the distance between the MTD and the origin, and $0 \leq \theta_k \leq \frac{\pi}{2}$ is the angle formed by the MTD with the RIS boresight. Similarly, let $\chi_{\textsc{ap}} = (d_{\textsc{ap}}, \theta_{\textsc{ap}})$ denotes the position of the AP.

\begin{figure}[b!]
\vspace{-7mm}
\centering
\subfigure[Setup of the communication scheme]{
\includegraphics[width=.8\columnwidth]{figures/communication-cell}
\label{fig:communication-cell-setup}
}
\subfigure[TDMA frame]{
\includegraphics[width=\columnwidth]{figures/tdma-frame}
\label{fig:tdma-frame}
}
\caption{a) AP, RIS, and service area of the communication cell where the MTDs are located; b) TDMA frame.}
\label{fig:tdma-frame-communication-cell-setup}
\end{figure}

The RIS is a thin surface located at the $xz$-plane with center at the origin. The surface is constituted by $N_x \in \mathbb{Z}_+$ reflecting elements in the $x$-axis direction and $N_z \in \mathbb{Z}_+$ in the $z$-axis direction, totaling $N = N_x N_z$ elements.
From the operational standpoint, we consider that the RIS introduces a phase shift $0 \leq \theta_r \leq \frac{\pi}{2}$ with marginal amplitude attenuation to the impinging signal. Importantly, the introduced phase shift belongs to a limited set of reflecting angle configurations, proposed to reduce the complexity of the RIS hardware and its control mechanism. Let $C \in \mathbb{Z}_+$ denotes the number of available configurations, and $\delta \triangleq \frac{\pi}{2(C+1)}$ denotes the angular resolution of the RIS. The set of reflecting angle configurations is defined as:
\begin{equation}
\label{eq:set-reflecting-angle-configurations}
\Theta \triangleq \set{\theta_r \mid \theta_r = c \delta, \; c = 1,\dots,C}.
\end{equation}

In this article, we focus on the UL channel, assuming that the packet generation by each MTD is modeled as a Poisson process.
The UL transmissions are carried out through time-division multiple access (TDMA) frames with duration less than the channel coherence time, $T_c > 0$. The TDMA frame, depicted in Fig. \ref{fig:tdma-frame}, is comprised by a \textit{training} block of length $T_t > 0$, an \textit{access} block for data transmission with length $T_a > 0$, and an \textit{acknowledgement} block of length $T_{\text{ack}} > 0$.
In the training block, in coordination with the RIS, the AP broadcasts a signal to the MTDs to prepare for the data transmission. Then, the MTDs transmit their data signals in the access block. Lastly, the AP sends a message to recognize the successfully decoded data packets in the acknowledgement block.
To focus purely on the PHY aspects of the system, we adopt this generic description of the TDMA frame. For comprehensive information on designing transmission protocols for RIS-assisted networks for MTDs, see \cite{cao2022, croisfelt2022}.

During the access block, the received data signal of the $k$-th MTD at the AP considering single-device transmission is equal to:
\begin{equation}
\label{eq:received-signal}
\mathbf{y} \triangleq \sqrt{\rho_k} h_k \mathbf{v}_k + \mathbf{w},
\end{equation}
where $\rho_k > 0$ is the MTD transmit power, $h_k \in \mathbb{C}$ denotes the channel coefficient, $\mathbf{v}_k \in \mathbb{C}^{L}$ such that $\mathbb{E}[\norm{\mathbf{v}_k}{2}^2] = 1$ denotes the transmitted data signal with $L \in \mathbb{Z}_+$ symbols, and $\mathbf{w} \in \mathbb{C}^L$ such that $\mathbf{w} \cscgdist{\mathbf{0}}{\sigma_w^2\mathbf{I}_L}$ denotes the additive white Gaussian noise vector, where $\sigma_w^2 > 0$ is the noise power.
From \eqref{eq:received-signal}, the instantaneous SNR for the $k$-th MTD is equal to:
\begin{equation}
\gamma_k \triangleq \frac{\rho_k |h_k|^2}{\sigma_w^2}.
\end{equation}
Based on the channel model of \cite{ozdogan2020, croisfelt2022} for communication schemes as depicted in Fig. \ref{fig:communication-cell-setup}, the SNR can be rewritten as:
\begin{equation}
\label{eq:snr}
\gamma_k = \frac{\rho_k \beta_k |A_k|^2}{\sigma_w^2},
\end{equation}
where $\beta_k > 0$ denotes the \textit{total path loss} and $A_k \in \mathbb{C}$ denotes the \textit{array factor} due to the RIS discretization into sub-wavelength reflecting elements \cite{croisfelt2022}, respectively defined as:
\begin{gather}
\label{eq:total-path-loss}
\beta_k = \frac{\beta_0}{d_{\textsc{ap}}^2 d_k^2} \cos^2 \theta_k,\\
\label{eq:array-factor}
A_k = N_z \sum_{n = 1}^{N_x} e^{j 2\pi (\sin \theta_k - \sin \theta_r) n},
\end{gather}
where $\beta_0 > 0$ denotes the path loss at the reference distance and $j = \sqrt{-1}$.
From \eqref{eq:array-factor}, one can notice that the RIS array factor directly depends on the reflecting angle $\theta_r$, which is limited by the set $\Theta$ defined in eq. \eqref{eq:set-reflecting-angle-configurations}.
Finally, substituting \eqref{eq:total-path-loss} and \eqref{eq:array-factor} in \eqref{eq:snr}, we obtain the following expression of the instantaneous SNR:
\begin{equation}
\label{eq:snr-complete}
\gamma_k = \frac{\rho_k \beta_0 N_z^2 \left| \sum_{n = 1}^{N_x} e^{j 2\pi (\sin \theta_k - \sin \theta_r) n} \right|^2 \cos^2 \theta_k}{\sigma_w^2 d_{\textsc{ap}}^2 d_k^2}.
\end{equation}
Therefore, one can note that, besides the MTD and AP positions, the RIS setup, specifically the number of reflecting elements, $N = N_x N_z$, and the reflecting angle configuration, $\theta_r \in \Theta$, has a significant impact on the instantaneous SNR.

\section{Device Energy Consumption Model}\label{sec:model-device-energy-consumption}

In this section, we develop a model for the MTDs energy consumption. We propose an expression for the EBL as EE metric specially focused on the devices-side.
Let $\bar{\gamma} \in \mathbb{R}$ denotes the target SNR at the AP for an MTD to experience reliable communication. From \eqref{eq:snr-complete}, we can derive the transmit power of the $k$-th MTD to attain the average SNR $\bar{\gamma}$ as:
\begin{equation}
\label{eq:required-transmit-power}
\hspace{-2mm}\rho_k(\bar{\gamma}) = \bar{\gamma} \left( \frac{\beta_0 N_z^2 \left| \sum_{n = 1}^{N_x} e^{j 2\pi (\sin \theta_k - \sin \theta_r) n} \right|^2 \cos^2 \theta_k}{\sigma_w^2 d_{\textsc{ap}}^2 d_k^2} \right)^{-1}\hspace{-5mm}.\hspace{-3mm}
\end{equation}
From \eqref{eq:required-transmit-power}, one can notice that the transmit power depends on the position of the MTD, $\chi_k = (d_k, \theta_k)$, as well as on the number of elements at the RIS, $N = N_x N_z$, and the angle of reflection of the RIS, $\theta_r$. Deriving the radiofrequency (RF) transmit power is paramount to analyze the MTD EE as it constitutes most of the dissipated power during the TDMA
frame.

To develop the model for the \textit{device energy consumption}, we consider the MTDs under two device modes: \textit{i)} \textit{transmission} mode, and \textit{ii)} \textit{receive} mode. From Fig. \ref{fig:tdma-frame}, one can perceive that the MTDs are in the receive mode during the training and acknowledgement blocks, while they are in the transmit mode during the access block. Therefore, the \textit{energy consumption} $E(\chi_k) > 0$ of the $k$-th MTD at the position $\chi_k$ is defined by:
\begin{equation}
E(\chi_k) \triangleq E_s + T_t P_{\text{Rx}} + T_a (P_c + \xi \rho_k) + T_{\text{ack}} P_{\text{Rx}},
\end{equation}
where $E_s > 0$ denotes the static energy consumption, $P_{\text{Rx}} > 0$ denotes the power dissipated in the receive mode, $P_{\text{Tx}} = P_c + \xi \rho_k$ denotes the power dissipated in the transmission mode, where $P_c > 0$ denotes the power dissipated by the device circuits, and $\xi > 1$ denotes the inverse of efficiency of the RF PA.

The EBL is a metric to evaluate the device EE given its battery capacity, energy consumption, and reporting period \cite{azari2021}. Let $T_r > 0$ denotes the expected length between consecutive \textit{reporting periods} of the MTD. The EBL in seconds of the $k$-th MTD at the position $\chi_k$ is equal to:
\begin{equation}
\label{eq:expected-battery-lifetime}
L(\chi_k) \triangleq \frac{E_0\, T_r}{E_s + T_a (P_c + \xi \rho_k) + (T_t + T_{\text{ack}}) P_{\text{Rx}}} ,
\end{equation}
where $E_0 > 0$ denotes the battery capacity of the MTD in Joule. From the transmission protocol standpoint, the EBL depends mainly on the length of the TDMA frame blocks and the transmit power. Especially, as suggested by \eqref{eq:required-transmit-power}, the transmit power is strongly linked to the RIS setup, particularly the number of RIS elements and reflecting angle configurations. Therefore, carefully designing the RIS setup is essential to improve the system EE in IoT networks, particularly at the devices-side.

\section{Numerical Results}\label{sec:numerical-results}

In this section, we analyze the EE of the RIS-assisted IoT network using the EBL as the main metric.
In the simulations, we calculate the required transmit power to attain the target SNR, defined in eq. \eqref{eq:required-transmit-power}, at each position $\chi_k$. Moreover, we assume that the transmit power cannot exceed the maximum transmit power, $\rho_{\max} > 0$, \textit{i.e.}, $\rho_k(\bar{\gamma}) \leq \rho_{\max}$. In this sense, when the MTD needs more power than $\rho_{\max}$ to attain the target SNR, such MTD is under outage.
All the parameter values deployed to generate the numerical results are listed in Table \ref{tab:numerical-results-parameter-values}.

\begin{table}[b]
\centering
\caption{Parameter values used to generate the numerical results.}
\label{tab:numerical-results-parameter-values}
\begin{tabular}{p{.28\columnwidth}|p{.6\columnwidth}}
\hline
\textbf{Parameter} & \textbf{Description}\\
\hline
$\chi_{\textsc{ap}} = (20 \text{m}, \pi/4)$ & AP position\\
$d_k \in [20, 100]$ m & Distance of the MTD from the origin\\
$\theta_k \in [0, \pi/2]$ & MTD-RIS angle\\
\hline
${N \in [4,100]}$ & \# RIS elements ($N_x = N_z$)\\
$C \in \set{2,4,8,16}$ & \# RIS reflecting angle configurations\\
\hline
$T_c = 50$ ms & Channel coherence time\\
$T_a = 0.85 T_c$ & Training block length\\
$T_t = 0.10 T_c$ & Access block length\\
$T_{\text{ack}} = 0.05 T_c$ & Acknowledgement block length\\
$\beta_0 = - 52$ dB & Path loss at the reference distance\\
$\sigma_w^2 = -94$ dBm & Noise power\\
\hline
$T_r = 300$ s & Length between consecutive reporting periods\\
$E_0 = 2.5$ kJ & Battery capacity\\
$E_s = 10 \mu$J & Static energy consumption\\
$P_c = 1 $ mW & Power dissipated by the MTD circuits\\
$P_{\text{Rx}} = 100$ mW & Power dissipated in the receive mode\\
$\xi = 1.33$ & Inverse of efficiency of the RF PA\\
$\rho_{\max} = 24$ dBm & Maximum transmit power\\
$\bar{\gamma} = 10$ dB & Target SNR\\
\hline
\end{tabular}
\end{table}

Fig. \ref{fig:power} depicts $\rho_k(\bar{\gamma})$ required to attain the target SNR $\bar{\gamma} = 10$ dB across the service area of the communication cell. We assume that the RIS has two different reflecting angle configurations, \textit{i.e.}, $C = 2$. Additionally, at each position, $\rho_k(\bar{\gamma})$ is calculated considering the best RIS configuration, that is, the configuration that results in the smallest transmit power.
Analyzing Fig. \ref{fig:power}, one can see that the minimum $\rho_k(\bar{\gamma})$ observed across the service area decreases with $N$ due to the enhanced array factor of the RIS, defined in eq. \eqref{eq:array-factor}. At the same time, the outage region area reduces as $N$ increases, improving the network coverage.
For $N = 100$, there are two main beams in the service area (dark blue color), where the required $\rho_k(\bar{\gamma})$ is less than the values in the other positions. Specifically, these beams are pointed towards the reflecting angles configured at the RIS, $\Theta$, which in the analyzed scenario with $C = 2$ are equal to $30^\circ$ and $60^\circ$. Hence, these beams represent the regions where the RIS can efficiently reflect much of the signal power.

\begin{figure}[t]
\centering
\includegraphics[width=\columnwidth]{figures/power}
\vspace{-7mm}
\caption{$\rho_k(\bar{\gamma})$ across the service area. $C = 2$, $\bar{\gamma} = 10$ dB, and $\rho_{\max} = 24$ dBm.}
\label{fig:power}
\vspace{-3mm}
\end{figure}

Based on the results of Fig. \ref{fig:power}, Fig. \ref{fig:ebl-C-2} depicts the EBL $L(\chi_k)$ in years across the service area for $C = 2$. From \eqref{eq:expected-battery-lifetime}, it is straightforward to see that $L(\chi_k)$ must follow the inverse behavior of $\rho_k(\bar{\gamma})$. Accordingly, in Fig. \ref{fig:ebl-C-2}, one can notice that the increase on the RIS array factor due to the higher $N$ improves the maximum $L(\chi_k)$, reducing the outage region area, and simultaneously improving the devices EE and the network coverage.

In order to analyze the effect of increasing the number of RIS reflecting angle configurations, Fig. \ref{fig:ebl-C-8} depicts $L(\chi_k)$ across the service area for $C = 8$.
Comparing this result with the same $N$ to Fig. \ref{fig:ebl-C-2}, one can notice that increasing $C$ improves the EBL $L(\chi_k)$ across the service area and reduces the outage region size. Such improvements arise since the RIS with an increased number of reflecting angle configurations can beamform the signal towards a greater number of directions.
Despite the improvement on coverage, one can notice that specifically for $N = 100$ there is a permanent outage region into the service area near to $\theta_k = \frac{\pi}{2}$. Such region is due to the setup of the communication cell, depicted in Fig. \ref{fig:communication-cell-setup}, where the MTDs with $\theta_k\approx\frac{\pi}{2}$ are located in approximately the same plane as the RIS, an unfavorable region for signal reflection as revealed by the cosine term in \eqref{eq:total-path-loss}.

\begin{figure}[t]
\centering
\subfigure[$C = 2$]{
\includegraphics[width=\columnwidth]{figures/ebl-C-2}
\label{fig:ebl-C-2}
}
\subfigure[$C = 8$]{
\includegraphics[width=\columnwidth]{figures/ebl-C-8}
\label{fig:ebl-C-8}
}
\vspace{-5mm}
\caption{$L(\chi_k)$ across the service area. $C \in \set{2,8}$, $T_r = 300$ s, $\bar{\gamma} = 10$ dB, and $\rho_{\max} = 24$ dBm.}
\vspace{-5mm}
\end{figure}

\begin{figure}[b]
\vspace{-3mm}
\centering
\subfigure[Average $\rho_k(\bar{\gamma})$ and $L(\chi_k)$]{
\includegraphics[width=.492\columnwidth]{figures/average-power-and-ebl}
\label{fig:average-power-and-ebl}
}
\subfigure[Outage region area]{
\includegraphics[width=.428\columnwidth]{figures/outage-region-area}
\label{fig:outage-region-area}
}
\caption{a) Average $\rho_k(\bar{\gamma})$ and average $L(\chi_k)$ as a function of $N$; b) Outage region area as a function of $N$. $C \in \set{2,4,8,16}$, $T_r = 300$ s, $\bar{\gamma} = 10$ dB, and $\rho_{\max} = 24$ dBm.}
\end{figure}

Fig. \ref{fig:average-power-and-ebl} depicts the average $\rho_k(\bar{\gamma})$ and $L(\chi_k)$ over the service area as a function of $N$. Following the behavior observed in the previous results, the average $\rho_k(\bar{\gamma})$ decreases with $N$, while the average $L(\chi_k)$ increases with it.
Specifically for $C \in \set{2,4}$ and $N > 36$, one can notice that the average $\rho_k(\bar{\gamma})$ has a clear oscillating behavior. This is due to the low number of main beams produced by the small number of RIS reflecting angle configurations $C$ and the fact that increasing $N$ may increase the signal power at the main beams at the expense of decreasing it at the side beams.
Moreover, for a fixed $C$, one can notice that the average $\rho_k(\bar{\gamma})$ and, consequently, the average $L(\chi_k)$ are limited by $N$, demonstrating that the RIS setup, \textit{i.e.}, $N$ and $C$, must be carefully designed to avoid a setup that cannot be fully exploited by the network.

Lastly, Fig. \ref{fig:outage-region-area} depicts the percentage of the outage region area as a function of $N$. This result reinforces that the outage region decreases asymptotically both with $N$ and $C$, indicating that the RIS setup is directly associated with the network coverage. Indeed, such a result demonstrates that, even with large values of $N$ and $C$, there is a permanent outage region for $\theta_k \approx \frac{\pi}{2}$ due to the communication cell setup. Therefore, if the aim is to enhance the network coverage in the simulated setup, a RIS with $(N,C) = (81,8)$ is sufficient to get an outage region with area as small as $2\%$.

\section{Conclusions}\label{sec:conclusions}

In this article, we study the design of energy-efficient IoT networks assisted by a RIS. Firstly, we derive an expression for the required transmit power to attain a target SNR considering the RIS discretization into sub-wavelength reflecting elements. Secondly, we develop an expression for the EBL of the MTDs.
The numerical results demonstrate that the RIS can significantly improve the EBL of the MTDs by reducing the transmit power. Additionally, the RIS can enhance the network coverage as long as it has the right numbers of reflecting elements and reflecting angle configurations.
Nevertheless, since the EBL is simultaneously limited by the number of RIS elements and configurations, the RIS setup must be carefully designed to achieve energy-efficient networks that can fully exploit the potential of the RIS.

\bibliographystyle{IEEEtran}


\section{Introduction}
\label{sec:intro}

Sound event detection has long relied on strongly annotated data for training and evaluation \cite{Mesaros2017,Mesaros2019,serizel2020}, namely data that contains class labels, and temporal boundaries in terms of start time and end time for each event instance. Development of robust methods for SED was hindered by the small size of strongly-labeled datasets \cite{Mesaros2016_EUSIPCO}, motivating the use of alternative training methods based on weak labels (without temporal information) \cite{Dinkel2021}, synthetic data \cite{salamon2014}, or combinations \cite{Turpault2020a}. Currently, the largest strongly-labeled dataset contains 67k clips of 10~s, with an average number of 3.5 sound events per file \cite{Hershey2021_ICASSP}. The length of the clips is artificially small and therefore might misrepresent the true sound events distribution within a longer timeframe. The only datasets with minutes-long recordings are the TUT SED 2016 and 2017 datasets, created by manually annotating all audible event instances and postprocessing of the labels \cite{ Mesaros2017, Mesaros2016_EUSIPCO}.

An often used alternative to manual annotation is crowdsourcing, which was used to produce many datasets for different domains, such as: image classification with ImageNet \cite{Deng2009} or Microsoft COCO \cite{Lin2014}; music classification with OpenMIC \cite{Humphrey2018} or TROMPA\_MER \cite{GomezCanon2022}; audio captioning with CLOTHO \cite{Drossos2020} or audio tagging with MATS \cite{martin2021_EUSIPCO}.
To benefit from the simplicity of collecting weak labels through crowdsourcing, in our earlier work we proposed a method to estimate temporally strong labels from weakly-labeled overlapping segments of an audio clip \cite{martin2021_WASPAA}. Strong labels are estimated by reconstructing the temporal order of the annotated segments and counting activity indicators for each annotated sound instance.
The obtained count-based activity indicators are values between 0 and 1, representing the aggregated opinion of multiple annotators, which can also be interpreted as reflecting the uncertainty of the annotators pool about the label. These non-binary values can be seen as \emph{soft labels} \cite{Mendez2022}, as opposed to  the normal case of \emph{hard labels} where each event class has a binary activity level associated indicating if the sound is active (1) or not (0).

Human uncertainty represented as soft labels was shown to make classification more robust and improve generalization in image classification \cite{Peterson2019}, helping the model define transitions between ambiguous classes \cite{Grossmann2022}. Soft labels are typically used through labels smoothing regularization \cite{Szegedy2016}, and are also produced in mixup augmentation by interpolating the one-hot encoding training labels \cite{Zhang2018}, leading to a smoother estimate of uncertainty. In contrast to the one-hot classification case, the special characteristic of sound event detection is the multi-label setup, where one time-segment of audio can have one or multiple events present at once. The predicted outputs in the network do not need to sum up to one, which makes the use of soft labels a readily suitable alternative to the usual multi-hot encoding training scenario.

In this paper we investigate if the soft labels contain information  useful for the training process, and how such information can be used to improve detection performance. The paper presents two main contributions: first, we release a new dataset, MAESTRO-Real, containing temporally strong labels for sound events in real-life environments. The data was annotated using the procedure in \cite{martin2021_WASPAA} and is provided with soft and hard labels. Second, we show that a SED system trained using soft labels is capable of learning the soft input representation, and able to detect under-represented classes that in a normal setup based on hard labels are not detected.

\vspace{-10pt}
\section{Soft labels dataset creation}
\label{sec:method}
Crowdsourcing for annotating sound events in long audio recordings has been proposed in \cite{martin2021_WASPAA} and shown to produce reasonable annotations. The method consists of a single-pass multi-label annotation \cite{Cartwright2019} with weak labels; the presence of a particular sound is explicitly indicated by annotators by selecting the corresponding label from a predefined set of target sounds, while the absence is indicated implicitly by not selecting a label.

\subsection{Annotation and label estimation procedure}
The annotation process uses weak labeling of densely overlapping segments, and reconstructs the temporal activity of the target sound events as a count-based value based on the annotator opinions. The process is illustrated in Fig. \ref{fig:ann}. The annotation process creates segments $t$ with a length determined by the annotation hop, each such segment being part of multiple annotation segments. For each annotation segment there are multiple opinions. For aggregation, one can use for example majority vote among the $M$ available opinions for segment $t$, to obtain either 0 (sound event inactive) or 1 (sound event active). A one-second annotation hop results in a temporally strong annotation with a resolution of 1~s. While not exactly fitting the strict definition of strong labels, the additional temporal information available in comparison with a weak label (e.g. per 10~s) was shown to bring significant improvement in performance for example to audio event classification \cite{Hershey2021_ICASSP}.

We aggregate the multiple opinions by taking into account the annotator competence estimated using MACE (multi-annotator competence estimation) \cite{hovy2013} as described in \cite{martin2021_WASPAA}. We use a slightly different procedure than \cite{martin2021_WASPAA} to determine the soft label: instead of using MACE to estimate the ``true" weak label, we use it only for competence estimation. We then process the annotator opinions for each segment $t$ by combining them based on annotators' competence as follows:

\begin{equation}
    a_t = \frac{{\sum_{j=1}^{M} \left ( \theta_j \cdot v_j \right ) }}{\sum_{j=1}^{M} \theta_j}
    \label{eq:estim}
\end{equation}

\noindent where $a_{t}$ is the activity level $a$ for one class in segment $t$, $M$ is the number of annotators for that segment, $\theta_j$ is the competence of annotator $j$ estimated using MACE, and $v_j$ indicates the annotator's opinion, being $1$ for the presence and $0$ for the absence of the label. The estimation is done independently for each class. For complete details about the annotation process and the annotator competence estimation procedure, we refer the reader to \cite{martin2023}.

\begin{figure}[!t]
    \centering
    \includegraphics[width=0.9\columnwidth]{figure_1.pdf}
    \caption{Annotation procedure and event activity estimation: the soft label in segment $t$ takes into account the individual opinions available for the segment, weighed by annotator's competence.}
    \label{fig:ann}
    \vspace{-12pt}
\end{figure}

The resulting value $a_{t}$ is a number between 0 and 1 that can be considered a \emph{soft label}. In this respect, the soft labels are activity indicators for each event class in consecutive segments, which reflect the aggregated uncertainty of the annotators. To produce \emph{hard labels} (binary activity indicators, as typically used in SED training) we apply a 0.5 threshold, i.e. events with activity indicators above 0.5 are considered active (1), while those below 0.5 are considered inactive (0).

The formulation in eq.~\ref{eq:estim} means that a minority of annotators (e.g.~2 of 5) can produce a soft label over 0.5 if they are highly reliable annotators, therefore producing a hard label of 1, even though it is not a majority. This is the intended effect of estimating the reliability of the annotators, and trusting more the more diligent ones.

\subsection{MAESTRO-Real Dataset}
\label{sec:dataset}

\begin{table*}[]
    \centering
    \begin{tabular}{l|l l l l l l l l l l l l l l l l l |l l}
    \toprule
          Scene &
          \rotatebox{90}{announcement} &\rotatebox{90}{birds singing} & \rotatebox{90}{brakes squeaking} & \rotatebox{90}{car} &\rotatebox{90}{cash register} & \rotatebox{90}{children voices} & \rotatebox{90}{coffee machine} & \rotatebox{90}{cutlery/dishes} & \rotatebox{90}{door opens/closes} & \rotatebox{90}{footsteps} & \rotatebox{90}{furniture dragging} & \rotatebox{90}{large vehicle} &\rotatebox{90}{metro approaching} &\rotatebox{90}{metro leaving} & \rotatebox{90}{people talking}  &
          \rotatebox{90}{shopping cart} &\rotatebox{90}{wind blowing} & \rotatebox{90}{No. of files} & \rotatebox{90}{Duration} \\
         \midrule
         Cafe/restaurant & - & - & - & - & - & 27 & 8 & 71 & - & 6 & 3 & - & - & - & 48 & - & - & 15 & 56.91 \\
         City center  & - & - & 37 & 92 & - & 4 & - & - & - & 62 & - & 117 & - & - & 49 & - & - & 15 & 61.47 \\
         Grocery store  & 0 & - & - & - & 0 & 6 & - & - & - & 27 & - & - & - & - & 61 & 5 & - & 14 & 49.53 \\
         Metro station  & - & - & - & - & - & 9 & - & - & 4 & 116 & - & - & 92 & 99 & 129 & - & - & 14 & 59.21 \\
         Residential area  & - & 60 & - & 76 & - & 10 & - & - & - & 26 & - & - & - & - & 20 & - & 38 & 17 & 59.82 \\
         \midrule
         Total  & - & 60 & 37 & 168 & - & 56 & 8 & 71 & 4 & 237 & 3 & 117 & 92 & 99 & 307 & 5 & 38 & 75 & 286.94 \\

         \bottomrule
    \end{tabular}
    \caption{Dataset statistics: event instances according to the hard labels, number and total duration of audio files in minutes.}
        \label{tab:dataset_stats}

        \end{table*}

We produced the MAESTRO-Real (Multi-Annotator Estimated STROng labels) dataset consisting of real-life recordings belonging to five different acoustic scenes: cafe/restaurant, city center, grocery store, metro station and residential area, a subset of TUT Acoustic Scenes 2016 dataset \cite{Mesaros2016_EUSIPCO}. The audio was recorded as 3-5 minutes long clips, which were split into short segments for the release of TUT Acoustic Scenes 2016. In this work we used the original long recordings.

Each file was annotated using Amazon Mechanical Turk, according to the procedure proposed in \cite{martin2021_WASPAA}. The annotators had to select which sounds were active in a 10~s segment from a list of six classes for each acoustic scene; some event classes are common to all the scenes (e.g. children voices, footsteps, people talking), while others are scene-specific (e.g. birds singing or metro leaving). The collected weak labels were aggregated into temporally strong labels according to eq.~\ref{eq:estim}, resulting in soft labels; these were then converted to hard labels using a threshold of 0.5.

The statistics of the event classes for the different acoustic scenes are presented in Table~\ref{tab:dataset_stats}, based on the hard labels. From the table we notice that the data is highly unbalanced: some classes have a very low number of event instances, while for some classes no instances exist in the hard labels (e.g. cash register which was given as a label for the grocery store files). An inspection of the soft labels reveals that for such classes there are many non-zero values, but they are below 0.5. We speculate that learning from soft labels will take advantage of this additional information and facilitate learning of the under-represented classes to some extent.

The dataset is publicly available\footnote{MAESTRO-Real, 10.5281/zenodo.7244360} and consists of 75 audio files and their corresponding annotations in two versions: one set of annotations with hard labels and one with soft labels. The hard labels format contains start time, end time, and textual label for each sound instance, with the particular feature that the timestamps are rounded to seconds due to the annotation procedure (e.g. 2 11 car). The soft labels format contains consecutive 1~s segments in a similar format, with start time, end time, and textual label, and in addition a value indicating the soft label for each event class in the given segment (e.g. 2 3 car 0.9; 2 3 footsteps 0.7; 3 4 car 0.85; etc).

\section{Training SED with soft labels}
\label{sec:sed_training}

We employ a basic CRNN architecture that we train in different setups, using the hard or the soft labels for comparison. We used  the same 5-fold training procedure for all the training setups. %

\subsection{SED model}

The model follows the CRNN architecture from \cite{Adavanne2017}, which consists of three convolutional layers and two bi-directional gated recurrent units (GRU), with a sigmoid layer as output layer. As input the model uses mel energies calculated using a window size of 2048 samples with a hop length equivalent to 20 ms, and 64 mel filter banks, with the lower and upper frequencies set to 50 and 14kHz.
When training with hard labels the system uses BCE loss, which allows independent outputs between 0 and 1. To train with soft labels, we first employ the same BCE loss, forcing the system to predict outputs as close as possible to binary activity indicators, as would be the case when using data augmentation or label smoothing. In addition, we investigate training using MSE loss, to teach the system to predict outputs as close as possible to the provided soft activity indicators instead of binary. In this case, the output layer is linear, to allow for linear regression.
In the remainder of the paper these setups are denoted as:

\begin{itemize}[noitemsep,nolistsep,leftmargin=*]
    \item $\text{H\_BCE\_sig}$: hard labels for training, BCE loss, and a dense output layer with sigmoid activation.
    \item $\text{S\_BCE\_sig}$: soft labels for training, BCE loss, and a dense output layer with sigmoid activation.
    \item $\text{S\_MSE\_lin}$: soft labels for training, MSE loss, and a dense output layer with linear activation.
\end{itemize}

\begin{figure*}[!t]
    \centering
     \vspace{-10pt}
    \includegraphics[width=1.0\textwidth]{fscore_avg.pdf}
    \vspace{-20pt}
    \caption{F1-score values for each of the models, with x-axis ordered from higher number of instances to lower number of instances per class. H\_BCE\_sig and S\_MSE\_lin\_s values are calculated using a class-dependent threshold.}
    \label{fig:fscore}
    \vspace{-8pt}
\end{figure*}

\subsection{Evaluation}

We evaluate the outputs by comparing them with the reference labels. The sigmoid outputs are probabilities between 0 and 1, so a threshold of 0.5 is applied on each output to determine the predicted event class activity independently. These outputs are then evaluated against the hard labels using 1~s segment-based F1-score and error rate \cite{Mesaros2019}.
Because the binary outputs do not explain the uncertainty, we calculate the Kullback-Leibler divergence (KLD) between the soft system output (before threshold) and the reference labels as provided in training. KLD allows a better insight into how much the distribution of the predicted labels differs from the reference annotation \cite{Murphy2012}, and is particularly suitable for comparing the system output to the soft labels.

\section{Experimental results}
\label{sec:results}

Table \ref{tab:metrics} shows that the performance of the three models is very similar when evaluated using micro-averaged metrics. Based on the values of KLD, we can say that training with BCE and soft labels provides system outputs closer to the reference than training with hard labels, but is detrimental to the overall metrics. Training with MSE and soft labels results in an output distribution close to the target, and highest overall performance, similar to the hard labels case. For the evaluation in Table~\ref{tab:metrics}, the S\_MSE\_lin system outputs were transformed to binary with a 0.5 threshold and compared with the hard labels, but KLD was calculated from the soft outputs to the soft reference labels.

\begin{table}[]
    \centering
    \begin{tabular}{l|c|cc||c}
    \toprule
     Method    & Threshold & ER & F1  & KLD  \\
     \midrule
     $\text{H\_BCE\_sig}$  & 0.5  & 0.44 & 70.60\% & 3.710  \\
     $\text{S\_BCE\_sig}$  & 0.5  & 0.48 & 68.25\% & 3.334  \\

     $\text{S\_MSE\_lin}$  & 0.5  & 0.44 & 70.82\% & 1.383   \\
     $\text{S\_MSE\_lin}$  & class-dependent  & 0.47 & 67.30\% & --   \\
    \bottomrule
    \end{tabular}
    \caption{Overall ER and F1-score in 1~s segments for the different training setups, evaluated against reference labels. The last column is the KL divergence between the system output (soft value) and the reference (binary for BCE, soft for MSE).}
    \label{tab:metrics}
    \vspace{-10pt}
\end{table}

An in-depth analysis of the class-wise performance shows that the under-represented classes are not detected by the H\_BCE\_sig model. This behavior has been observed in previous work \cite{Adavanne2017}, and is a result of the training process: the system optimizes to learn as well as possible the large classes, and be penalized less by the cross-entropy for ignoring the small classes. The same happens for the H\_BCE\_sig model.
When trained with MSE, the outputs are expected to be close to the provided soft labels, which in many cases are below 0.5. For this reason, binarizing its output with the 0.5 threshold does not show any improvement. This case is shown in Fig.~\ref{fig:fscore} as the S\_MSE\_lin\_h system, with \textit{h} indicating that reference and system outputs are the hard labels as for the previous two cases.

To understand the dynamics of the output w.r.t. the soft reference labels, we apply a class-wise threshold determined as the trimmed midrange of the soft labels in the training data. This is equivalent to operating point optimization per class in a SED system, except that we apply it on both soft reference and system output. The choice of midrange is motivated by the traditional 0.5 threshold typically used to binarize the sigmoid outputs: 0.5 is the midrange of the reference annotation values (binary activity, 0 or 1), not the mean (which would depend on the actual distribution of the values). Because we are working with human opinions, we use a 10\% trimmed midrange, to make the value more robust to outliers.

The results are presented in Fig.~\ref{fig:fscore} as the S\_MSE\_lin\_s system, with \textit{s} indicating that we compare the output with soft reference labels. It becomes apparent that the system does detect activity for all the classes, but this output is lost in the postprocessing when using the same threshold for all the classes. Class-wise average F1-score in this case is clearly higher than the others. Micro-average ER and F1-score for this case are shown in Table \ref{tab:metrics}, 0.47 and 67.3\%, respectively, indicating that there are overall more errors (higher ER) as a trade-off to detecting activity for all the classes.

\section{Conclusions}
\label{sec:concl}
Sound event detection is still one of the most challenging tasks in environmental audio analysis. Because there are few available datasets with long recordings, recent studies focused on using heterogeneous data for training, with evaluation based on small-size, manually annotated data. With this work we contribute to the data for SED by providing a new dataset consisting of five real-life acoustic scenes, with 17 sound event classes annotated through crowdsourcing, including soft and hard labels. We also showed that soft labels can be successfully used to learn acoustic models, and system outputs can be processed to produce hard labels with individual per-class thresholds.
Future work will consider tailoring models to the unbalanced nature of the datasets, which may arise from sound events being genuinely rare, or due to some sounds  being recognized only by a minority of the annotators.

\bibliographystyle{IEEEbib}{}