\section{Introduction}
Lip reading, aiming to recognize spoken sentences according to the given video of lip movements without
relying on the audio stream, has attracted great interest
~\cite{chung2017lip,martinez2020lipreading,assael2016lipnet,stafylakis2017combining,petridis2018audio,afouras2018deep,xu2018lcanet,zhang2019spatio}
due to the application in many scenarios
including dictating instructions in public areas or a noisy environment, and providing help for
hard-of-hearing people.
It remains a challenging task even for excellent lip readers~\cite{assael2016lipnet}.

Although prior works that explore lip reading
have obtained salient achievements, they are all trained in a non-simultaneous manner where the predictions are generated requiring
access to the full video.
Therefore, simultaneous lip reading, where a video segment containing fix number of frames is processed
while spoken sentence is generated concurrently,
is a more difficult but necessary extension for real-time understanding~(e.g. live video streaming).
Due to the low latency of simultaneous decoding, simultaneous lip reading are able to deal with massive video data~(e.g. long films)
without ``watching'' the entire video first.
In this paper, we study the task of simultaneous lip reading that recognizes sentences based on partial input.
However, it is very challenging to decode simultaneously for vision-text cross-modal translation in following aspects:

Firstly, for simultaneous decoding,
the model is required to learn the monotonic alignments
between video segments and target tokens, and pick a suitable moment that achieves a good trade-off between latency and accuracy
to predict the next token.
Due to the significant discrepancy of length of same token in different videos, it is difficult to estimate the duration of tokens
and learn such monotonic alignments.
Prior autoregressive methods~\cite{chung2017lip,afouras2018deep,zhang2019spatio,martinez2020lipreading,zhao2020hearing}
leverage the semantic information of entire videos and work in a word-synchronized mode without considering monotonic alignments,
making it non-simultaneous in nature.
A naive method is to scale the CTC-based model~\cite{assael2016lipnet,stafylakis2017combining,petridis2018audio,xu2018lcanet,chen2020duallip}
to simultaneous decoding by limiting each frame to see only its previous frames.
However, the target sentences always show a strong correlation across time~\cite{liu2020fastlr}, but the CTC-based model
generate different tokens conditionally independent of each other, ignoring the syntactic information.
In our paper, inspired by neural transducer~\cite{graves2012sequence,jaitly2016online}, we devise a lip reading transducer that generates
tokens in a frame-synchronized mode where an empty transfer is allowed
to read next video segment at each time step~(See Figure~\ref{fig:example}), and also considers the syntactic structure of the generated sentences.
With the reading of video segments, the tokens generate frame-by-frame and then are merged to the ultimate predictions.
We also design several effective training strategies including CTC pre-training, model warm-up and curriculum learning to promote the training
of lip reading transducer.

Secondly, to learn better spatio-temporal representations for cross-modal decoding, prior non-simultaneous methods~\cite{zhang2019spatio,liu2020fastlr}
employ multiple 3D convolution and self-attention layers in the visual encoder, which cannot be transferred to our simultaneous model due to their
expanding receptive field on the whole video.
To obtain a better simultaneous encoder and reduce the gap between our method and non-simultaneous methods, we construct a truncated 3D convolution
for spatio-temporal representations learning and time-restricted self-attention layer
to perform the frame-to-frame interaction among available video segments.

\begin{figure}[t]

  \includegraphics[width=1.0\linewidth]{figures/example.pdf}
  \caption{
        The frame-synchronized simultaneous decoding of the proposed lip reading transducer.
        At each time step, an empty transfer~(watch) is allowed to read next video segment or
        a context-aware token can be generated~(write).
  }
  \label{fig:example}
\end{figure}

Thirdly, in real scenarios, the storage is always limited by the extremely long input sequence~(e.g. massive video data).
Therefore, for simultaneous decoding, history segments may also be unavailable, making it more difficult to predict a new token with limited visual context.
To achieve a good storge-accuracy trade-off, inspired by memory networks~\cite{graves2014neural,graves2016hybrid},
we devise a novel attention-guided adaptive memory to organize semantic information of history segments and enhance the
visual representations using limited context.
Also, given the memory, the computation of the commonly-used self-attention mechanism is no longer conducted over all the history segments,
which reduces the computation-aware latency for simultaneous decoding~\cite{ma2020simulmt}.
Specially, the attention-guided memory is constructed to absorb new segments by momentum update and discard obsolete
features using the least frequently used~(LFU) algorithm guided by attention scores.
Based on the proposed adaptive memory, the simultaneous model incorporates both global context and adjacent semantic information
with acceptable computation-aware latency.

In summary, we study the task of simultaneous lip reading with limited history
and devise a vision-text cross-modal transducer SimulLR and devise
several effective training strategies to promote the performance.
For the simultaneous encoder, we construct a truncated 3D convolution and time-restricted self-attention layer
to learn better spatio-temporal representations for video segments.
Further, considering the limited storage and computational cost,
we further devise a novel attention-guided adaptive memory to organize semantic information of history segments
for simultaneous decoding with acceptable computation-aware latency.

The experiments show that the SimulLR achieves the translation speedup 9.10$\times$ compared with the state-of-the-art
non-simultaneous methods, and also obtains competitive results, which indicates the effectiveness of our proposed methods.

\section{Related Works}
\subsection{Lip Reading}
Lip reading aims to recognize spoken sentences according to the given video of lip movements without
relying on the audio stream.
Early works focus on single word classification~\cite{chung2016lip,wand2016lipreading}
and then switched to full sentences prediction~\cite{assael2016lipnet,stafylakis2017combining,chung2017lip,petridis2018audio,afouras2018deep,xu2018lcanet,zhang2019spatio}.
These works mainly study lip reading in a non-simultaneous manner with CTC-based model~\cite{assael2016lipnet,stafylakis2017combining,petridis2018audio,xu2018lcanet,chen2020duallip}
and autoregressive model~\cite{chung2017lip,afouras2018deep,zhang2019spatio,martinez2020lipreading,zhao2020hearing}.
Among them, LipNet~\cite{assael2016lipnet} takes advantage of spatio-temporal convolutional features and context modeling of RNNs.
Chen et al.~\cite{chen2020duallip} design a system that leverages the task duality of lip reading and lip generation to improve both tasks.
Afouras et al.~\cite{afouras2018deep} first introduce Transformer self-attention architecture into lip reading.
Zhao et al.~\cite{zhao2020hearing} enhance the training of lip reading model by distilling multi-granularity knowledge
from speech recognition.
Besides, instead of CTC decoder, Liu et al.~\cite{liu2020fastlr} further study non-autoregressive lip reading by leveraging integrate-and-fire module to
estimate the length of output sequence and alleviate the problem of time correlation.

However, these methods explore lip reading in a non-simultaneous manner, where the sentence prediction
relies on the entire video of talking face during inference.
In this paper, we further study the task of simultaneous lip reading that recognizes sentences based on partial input,
which owns more application scenarios.

\subsection{Simultaneous Decoding}
Due to lower latency and broader scenarios, simultaneous decoding has attracted a lot interest in many fields such as
neural machine translation~(NMT)~\cite{gu2016learning,grissom2014don},
automatic speech recognition~(ASR)~\cite{rao2017exploring,zhang2020unified,li2020towards,sainath2019two},
speech to text translation~\cite{oda2014optimizing,dalvi2018incremental,ren2020simulspeech,chen2020developing},
speech to speech translation~\cite{sudoh2020simultaneous} and so on.
In real-time scenarios, the simultaneous decoding aims to generate the predictions based on the given partial input
instead of the whole sequence, and the history context could be limited due to the rapid increase in the length of input.
Some widely used approaches for simultaneous decoding includes
reinforcement learning~(RL)~\cite{gu2016learning,grissom2014don},
connectionist temporal classification~(CTC)~\cite{amodei2016deep},
transducers~\cite{rao2017exploring,sainath2019two,chen2020developing}
and attention-based encoder-decoder~\cite{ren2020simulspeech,moritz2019triggered}.
Among them, at each time step, transducers generate the next target token, or an empty transfer to read next source input.

In this paper, we concentrate on vision-text cross-modal simultaneous decoding
and propose a novel lip reading transducer with an adaptive memory
where the history frames are limited.

\begin{figure*}[t]

  \includegraphics[width=1.0\linewidth]{figures/framework.pdf}
  \caption{
        (a) The overall framework of SimulLR: a truncated 3D spatio-temporal convolutional network to extract the visual features, a transformer-based sequence
        encoder, a transducer-based cross-modal decoder for language modeling and token prediction,
        an attention-guided adaptive memory to organize semantic information of history segments and enhance the
        visual representations.
        (b) The update and access of memory: absorb new segments by momentum update and discard obsolete
        features using the least frequently used~(LFU) algorithm guided by attention scores.
  }
  \label{fig:framework}
\end{figure*}

\subsection{Memory}
Memory module introduces external memory to store the past context and absorb new information, which is proposed to
improve the learning capability and boost the performance.
The neural turing machine~(NTM)~\cite{graves2014neural} and differentiable neural computer~(DNC)~\cite{graves2016hybrid}
are the typical memory for memorization and reasoning.
For few-shot learning, memory module mainly stores the information contained in the support set~\cite{munkhdalai2017meta,vinyals2016matching}
and attempts to learn the common access mechanism across tasks.
Memory module has also been incorporated into generative models~\cite{bornschein2017variational,li2016learning}
and sequence modeling~\cite{le2018variational} that conditions on the global contextual information provided in external
memory. The recurrent neural networks such as GRU~\cite{chung2014empirical} are also commonly-used differentiable memory
module for sequence modeling, although they still suffer from gradual forgetting of early contents after memorizing long sequences.

In this paper, considering the limited storage and computational cost,
we devise a novel attention-guided adaptive memory module to compress the history semantic
information and absorb upcoming video segments.

\section{Problem Formulation}
In this section, we first introduce the problem formulation of simultaneous lip reading.
Given a sequence of video segments ${\boldsymbol s} = \{{\boldsymbol s}_{1},{\boldsymbol s}_{2},...,{\boldsymbol s}_{n}\}$
without the audio stream, lip reading aims to predict the words sequence
${w} = \{{w}_{1},{w}_{2},...,{w}_{u}\}$ that the lip is speaking, where ${\boldsymbol s}_{t}$ is the $t$-th video segments
containing several frames, $n$ is the number of video segments, $n_f$ is the number of frames in a segment,
${w}_{i}$ is the $i$-th token and $u$ is the length of target sequence.
Under the simultaneous setting, the lip reading model is required to generate the $i$-th token ${w}_{i}$ with only partial input
${\boldsymbol s_{p_{i}}} = \{{\boldsymbol s}_{1},{\boldsymbol s}_{2},...,{\boldsymbol s}_{n(w_i)}\}$, where $n(w_i)$ is
the number of segments needed to predict the $i$-th token ${w}_{i}$ and $n(w_i) >= n(w_{i-1})$ for monotonic alignments.
Also, in our paper, only the adjacent segments are available due to the limited storage, making the partial input
${\boldsymbol s_{p_{i}}} = \{{\boldsymbol s}_{n(w_i)-a+1},{\boldsymbol s}_{n(w_i)-a+2},...,{\boldsymbol s}_{n(w_i)}\}$,
where $a$ is the number of available segments for the $i$-th token prediction.
For simultaneous lip reading model, the monotonic alignments to predict the target sequence $w$ are not given explicitly,
which means that the decoding segment path ${d} = \{\boldsymbol s_{p_{1}},{\boldsymbol s_{p_{2}}},...,{\boldsymbol s_{p_{u}}}\}$
is not unique. Therefore, the optimize object can be computed as follows:
\begin{eqnarray}
  {P}(w|{\boldsymbol s}) = \sum_{{d \in \phi(w)}}\prod_{i=1}^{u}{P}(w_i|{\boldsymbol s_{p_{i}}})
\end{eqnarray}
where ${P}(w|{\boldsymbol s})$ is the probability of generating the target sequence $w$, which is the sum
over all possible decoding segment paths $d \in \phi(w)$.

\section{Approaches}
In this section, we describe the SimulLR approach thoroughly.
As shown in Figure~\ref{fig:framework}(a), the proposed model is composed of a truncated
3D spatio-temporal convolutional network to extract the visual features, a transformer-based sequence
encoder, a transducer-based cross-modal decoder for language modeling and token prediction,
an attention-guided adaptive memory to organize semantic information of history segments and enhance the
visual representations with acceptable computation-aware latency.

We also design several effective training strategies including CTC pre-training, model warm-up and curriculum learning to promote the training
of the lip reading transducer.
The details of our method are described in the following subsections.

\subsection{Visual Encoder}
\textbf{Truncated C3D.}
To learn better spatio-temporal representations for cross-modal decoding, prior non-simultaneous methods~\cite{zhang2019spatio,liu2020fastlr}
employ multiple 3D convolution in the visual encoder, which cannot be transferred to our simultaneous model directly
due to their expanding receptive field on the whole video.
To address this challenge, in our paper, we truncate the 3D convolutional network in the temporal dimension and perform
spatio-temporal convolution only within one single segment ${\boldsymbol s}_{t}$, as shown in Figure~\ref{fig:framework}(a),
which introduces sufficient spatial-temporal context for representations learning while maintaining a simultaneous manner without absorbing the information of the entire video.

\noindent\textbf{Sequence Encoder.}
The sequence modeling of video segments is based on the stacked multi-head self-attention layers and feed-forward layers,
as proposed in Transformer~\cite{vaswani2017attention} and transformer-based lip reading models~(TM-seq2seq)~\cite{afouras2018deep}.
Moreover, to enable the simultaneous decoding, we employ the time-restricted self-attention, where the unavailable and future
frames are masked and each video frame can only see its previous several segments $\{{\boldsymbol s}_{t-a+1},{\boldsymbol s}_{t-a+2},...,{\boldsymbol s}_{t}\}$,
to simulate the streaming inputs and limited history storage. We denote the encoded visual representations of the $t$-th video segment ${\boldsymbol s}_{t}$ as ${\boldsymbol h}_{t}^v$,
as shown in Figure~\ref{fig:framework}.

\subsection{Simultaneous Cross-Modal Decoder}
The simultaneous cross-modal decoder is built based on the neural transducer~\cite{graves2012sequence,jaitly2016online}.
Concretely, at each time step, the decoder~(joint network) chooses to predict the next token ${\boldsymbol w}_{i}$
based on the partial input ${\boldsymbol s_{p_{i}}}$, or generate an empty transfer $\epsilon$
to read next video segment ${\boldsymbol s}_{n(w_i)+1}$, making $n(w_i) = n(w_i) + 1$.
Also, the syntactic structure of the generated sentences $\{{\boldsymbol w}_{1},{\boldsymbol w}_{2},...,{\boldsymbol w}_{i-1}\}$
are taken into consideration with a language model ${\rm LM(\cdot)}$.
With the reading of video segments, the tokens are generated frame-by-frame and then merged to the ultimate predictions.

\noindent\textbf{Language Model.}
Rather than recurrent neural network~(RNN), we also build a uni-directional transformer-based language model that comprises of
multi-head self-attention and feed-forward layers to leverage the history context of generated sentences.
Specially, the semantic representations of different words are denoted as $\{{\boldsymbol h}_{1}^w,{\boldsymbol h}_{2}^w,...,{\boldsymbol h}_{m}^w\}$.

\noindent\textbf{Joint Network.}
Based on the visual representations given by the simultaneous visual encoder and the semantic representations
given by the uni-directional language model, we employ a fully-connected layer with softmax to compute the joint matrix ${R}$,
where ${R}_{t,i}$ is the distribution over token vocabulary with ${\boldsymbol h}_{t}^v$ and ${\boldsymbol h}_{w}^i$.
A possible decoding path ${d} = \{\boldsymbol s_{p_{1}},{\boldsymbol s_{p_{2}}},...,{\boldsymbol s_{p_{u}}}\}$ can be simply
represented as a path from the start $(0,0)$ to the end $(n,m)$ in the joint matrix.
Therefore, the prior optimize object is further denoted as:
\begin{equation}
  {P}_{td}(w|{\boldsymbol s}) = \sum_{{d \in \phi(w)}}{P}(d|{R})
\end{equation}

\subsection{Attention-guided Adaptive Memory}
In real scenarios, the storage is always limited by the extremely long input sequence~(e.g. massive video data).
Therefore, for simultaneous decoding, history segments may be unavailable, making it more difficult to predict a new token with limited visual context.
To achieve a good storage-accuracy trade-off,
we introduce a novel attention-guided adaptive memory to organize semantic information of history segments and enhance the
visual representations with acceptable computation-aware latency.
Specially, the attention-guided memory containing $k$ memory banks,
is constructed to absorb new segments by momentum update and discard obsolete
features using the least frequently used~(LFU) algorithm guided by attention scores.

\noindent\textbf{Enhanced Visual Feature.}
As shown in Figure~\ref{fig:framework}(b),
given the adaptive memory ${\boldsymbol M} = \{\boldsymbol m_{{1}},\boldsymbol m_{{2}},...,{\boldsymbol m_{k}}\}$,
we compute a encoder-memory inter-attention for ${\boldsymbol h}_{t}^v$ to enhance the visual representations, given by
\begin{eqnarray}
  \begin{split}
    & {\boldsymbol {\tilde h}}_{t}^v = {\boldsymbol {h}}_{t}^v + \sum_{i=1}^k{\tilde\alpha}_{i}\boldsymbol m_{{i}},~~
    {\tilde\alpha}_{i} = \frac{\exp({\alpha}_{i})}{\sum_{j=1}^k\exp({\alpha}_{j})}
  \end{split}
\end{eqnarray}
where ${\alpha}_{i}$ is the attention score of the $i$-th memory bank $\boldsymbol m_{i}$ and video segment ${\boldsymbol s}_t$,
and ${\boldsymbol {\tilde h}}_{t}^v$ is the enhanced visual feature that absorbs earlier segments.
The enhanced visual feature is actually used for computation of the joint matrix $R$.
Note that we employ the dot-product attention~\cite{vaswani2017attention} to obtain scores over all the memory banks.

\noindent\textbf{Absorb New Segment.}
Since the attention distribution ${\tilde\alpha}$ reflects the similarity between current video segment and
existing segments in the memory banks, some replacements on the memory bank seem to be redundant
if the segment is close enough to some existing one. To enable higher memory efficiency and avoid storing redundant
information, we adaptively absorb the new segment based on the information entropy ${I_t}$ guided by the attention distributed ${\tilde\alpha}$, given by
\begin{equation}

  {I_t} = -\sum_{i=1}^k{\tilde\alpha_i}\cdot\log({\tilde\alpha_i})
\end{equation}
High information entropy ${I_t}$ represents a more smoothed attention distribution and indicates
that more information different from the memory is contained in video segment ${\boldsymbol v}_t$,
while low information entropy indicates redundancy.
To enable higher memory efficiency, we absorb these redundant visual features having ${I_t} < \gamma_e$
by momentum updating,
as shown in Figure~\ref{fig:framework}(b), given by
\begin{equation}
  \begin{split}
    & {\boldsymbol m}_j = {\gamma_m}\cdot {\boldsymbol m}_j + (1-{\gamma_m})\cdot Summarize({\boldsymbol s}_t), \\
    & j = \argmaxA_j{\tilde\alpha_j}
  \end{split}
\end{equation}
where $\gamma_e$ is the information entropy threshold,
${\gamma_m}$ is the parameter to control the impact of moving average, and
$Summarize(\cdot)$ is the operation~(e.g. max-pooling) to aggregate features from different frames within a segment.

\noindent\textbf{Discard Obsolete Segment.}
For these video segments that are distinct from the existing ones in the memory bank,
we simply replace the least frequently used segment in the adaptive memory.
Also, the counting index is updated based on the soft attention distribution, given by
\begin{equation}
  count({m}_i) = count({m}_i) + \tilde\alpha_i
\end{equation}
And the LFU index is computed as follows:
\begin{equation}
  {LFU}({m}_i) = \frac{count({m}_i)}{life({m}_i)}
\end{equation}
where $count({m}_i)$ and $life({m}_i)$ are separately the counting index of ${\boldsymbol m}_i$ and
timespan that ${\boldsymbol m}_i$ stays in the memory bank.

\subsection{Training}
\noindent\textbf{Pre-training with CTC Loss.}
To stable the training of the lip reading transducer, we first pre-train the model with an ordinary CTC loss without considering
the syntactic structure of target sequences.
The CTC also works in frame-synchronized mode and introduces a set of intermediate CTC path $\varphi(w)$ where each path is
composed of target tokens and blanks that can be reduced to the target sequence $w$.
The CTC loss can be computed as follows:
\begin{equation}
  \mathcal{L}_{CTC} = -\log{P_{ctc}(w|s)} = -\log{\sum_{c \in \varphi(w)}P(c|s)}
\end{equation}
With the pre-trained model, we can train the lip reading transducer with the simultaneous lip readig loss as follows:
\begin{equation}
  \mathcal{L}_{SimulLR} = -\log{P}_{td}(w|{\boldsymbol s}) = -\log{\sum_{{d \in \phi(w)}}{P}(d|{R})}
\end{equation}

\noindent\textbf{Model Warm-up.}
Although a better visual encoder~(stacked self-attention and feed-forward layers) can effectively promote the prediction,
it also becomes difficult to train especially with deeper structure for transducer-based methods~\cite{hu2020exploring}.
In this paper, we devise a strategy called model warm-up for the training of lip reading transducer with deeper structure.
Specially, (1) We first apply a shallower sequence encoder~(e.g. less self-attention and feed-forward layers)
and focus on the training of truncated C3D layer, which warms up the C3D encoder.
(2) We then freeze the parameters of truncated C3D and employ a deeper network structure, which warms up the sequence encoder.
(3) We train both the visual encoder that has been warmed up
and simultaneous decoder with the proposed loss.

\noindent\textbf{Curriculum Learning.}
To further make the training procedure stable, we exploit the novel training paradigm based on the curriculum learning
that starts with short videos, learns the easier aspects of lip reading and then gradually increase the length of
training videos.

\section{Experiments}
\subsection{Datasets}
\noindent\textbf{GRID.}
The GRID~\cite{cooke2006audio} dataset contains 34,000 sentences uttered by 34 speakers.
This dataset is easy to learn since the spoken sentences are in a restricted grammar and composed of 6$\sim$10 words.
The vocabulary of GRID is also small, comprising 51 different words including 4 commands, 4 color, 4 prepositions,
25 letters, 10 digits and 4 adverbs.
All the videos of lip movements have the same length of 75 frames with a frame rate of 25fps.
Following prior works~\cite{assael2016lipnet,chen2020duallip,liu2020fastlr}, we randomly select 255 sentences
for evaluation.

\noindent\textbf{TCD-TIMIT.}
The TCD-TIMIT~\cite{harte2015tcd} dataset contains 59 speakers that utters approximately 100 phonetically rich sentences,
making this dataset more challenging but closer to the natural scene.
Also, the video length and sentence in the TCD-TIMIT dataset are longer than GRID and variable.
Following prior work~\cite{harte2015tcd}, we use the recommended train-test splits for training and evaluation.

\subsection{Implementation Details}
\noindent\textbf{Data Preprocessing.}
For the videos, to extract lip movements, we first obtain a $256 \times 256$ aligned face with Dlib detector~\cite{king2009dlib},
crop the $160 \times 80$ mouth-centered region from the aligned face and then resize the region to $100 \times 60$ as the video input.
To improve the recognition accuracy, we use the strategy of data augmentation that involves horizontal flips with 40\% probability,
crop 0$\sim$5\% of horizontal or vertical pixels with 40\% probability.
In particular, we convert the video frames to grey scale for the easier GRID dataset to reduce computation cost.
For the sentences, we build a vocabulary at word-level for the GRID dataset while phoneme-level for the TCD-TIMIT dataset
following previous works~\cite{harte2015tcd}.

\noindent\textbf{Model Setting.}
For simultaneous decoding, we set the number of available segments $a$ to 2, and the number of frames in a video segment
$n_f$ to 3 for GRID dataset and to 5 for TCD-TIMIT dataset.
The number of memory banks $k$ is set to 20.
The information entropy threshold $\gamma_e$ is set to $0.6 \times \log_2{k}$ and moving step $\gamma_m$ is set to 0.7.
For the truncated C3D to extract spatial-temporal representations, we stack six 3D convolutional layers with 3D max pooling,
RELU activation, and two fully connected layers. The kernel size of 3D convolution and pooling is set to $3 \times 3$.
For both the segment sequence encoder and language model, we stack four self-attention layers with feed-forward network.
We set $d_{hidden} = 256$ for GRID dataset and $d_{hidden} = 512$ for TCD-TIMIT dataset respectively.
The joint network is simply a two-layer non-linear transformation.

\noindent\textbf{Training Setup.}
For GRID dataset, We pretrain the model using the CTC loss with 10 epochs, warmup the visual encoder using two sequence encoder layers
with 20 epochs and then train the whole model using four encoder layers with 100 epochs.
For TCD-TIMIT dataset, We pretrain the model using the CTC loss with 50 epochs, warmup the visual encoder using two sequence encoder layers
with 50 epochs and then train the whole model using four encoder layers with 150 epochs.
To train the SimulLR model, we employ the Adam optimizer with a initial learning rate 0.0005 for GRID dataset and 0.0003 for TCD-TIMIT dataset,
and with a shrink rate of 0.99 according to the updating step.

\subsection{Evaluation Metrics}
During the inference stage, the SimulLR model perform simultaneous decoding with the adaptive memory.
Following prior works~\cite{chen2020duallip}, to evaluate the recognition quality, we use the metrics of
character error rate~(CER) and word error rate~(WER) on the GRID dataset, and phoneme error rate~(PER)
on the TCD-TIMIT dataset since the output of this dataset is phoneme sequence.
The different types of error rate can be computed as follows:
\begin{equation}
  ErrorRate = \frac{(S + D + I)}{M}
\end{equation}
where $S, D, I, M$ are separately the number of the substitutios, deletions, insertions and reference
tokens~(character, word or phoneme).

To compute the latency of simultaneous decoding, we consider the non computation-aware~(NCA) latency,
as proposed in~\cite{ma2020simulmt}.
Specially,
The NCA latency for ${\boldsymbol w}_i$, $d_{NCA}({w}_i)$, equals to $n({w}_i)\cdot n_f\cdot{T_s}$,
where $T_s$ (ms) is the frame sampling rate.
The average NCA latency $AL_{NCA}$ is defined as:
\begin{equation}
  AL_{NCA} = \frac{1}{\tau({w})}\sum_{i=1}^{\tau(w)}d_{NCA}({w}_i) - r\cdot(i - 1)\cdot{T_s}
\end{equation}
where $\tau({w})$ denotes the index of the first generated token when the model read the entire video,
and $r = {(n \cdot n_f)}/{u}$ is the length ratio between source and target sequence.

\begin{table}[t]
  \centering
  \caption{The word error rate~(WER) and character error rate~(CER) on the GRID dataset, and
  the phoneme error rate~(PER) on the TCD-TIMIT dataset.}
  \scalebox{1.0}{
  \begin{tabular}{ccccc}
      \toprule
      \multicolumn{2}{l}{}       & \multicolumn{2}{c}{GRID} & TCD-TIMIT \\
      \cmidrule(lr){3-4} \cmidrule(lr){5-5}
      \multicolumn{2}{l}{Method} & WER(\%) & CER(\%) & PER(\%)\\
      \midrule
      \multicolumn{4}{l}{\textit{Non-Simultaneous Methods}} \\
      \midrule
      \multicolumn{2}{l}{LSTM~\cite{wand2016lipreading}}      & 20.4    & /   & / \\
      \multicolumn{2}{l}{LipNet~\cite{assael2016lipnet}}      & 4.8     & 1.9 & /\\
      \multicolumn{2}{l}{FastLR~\cite{liu2020fastlr}}         & 4.5     & 2.4 & /\\
      \multicolumn{2}{l}{LCANet~\cite{xu2018lcanet}}          & 4.215   & 1.532 & /\\
      \multicolumn{2}{l}{DualLip~\cite{chen2020duallip}}      & {\bf 2.71}    & {\bf 1.16} & {\bf 46.2} \\
      \midrule
      \multicolumn{4}{l}{\textit{Simultaneous Methods}} \\
      \midrule
      \multicolumn{2}{l}{LR-RNN-CTC}              & 28.884 & 19.912 & 67.021\\
      \multicolumn{2}{l}{LR-TM-CTC}      & 20.691 & 15.223 & 63.428 \\
      \multicolumn{2}{l}{LR-RNN-TD}       & 11.570 & 7.263 & 64.213\\
      \multicolumn{2}{l}{LR-TM-TD}      & {3.125} & {1.588}  & {62.831} \\

      \multicolumn{2}{l}{SimulLR(Ours)} & {\bf 2.738} & {\bf 1.201} & {\bf 56.029}\\
      \bottomrule
  \end{tabular}
}
\label{table:main_result}
\end{table}

\begin{table}[t]
  \centering
  \caption{The comparison of NCA latency and corresponding recognition accuracy
  with different segment size $n_f$ on TCD-TIMIT dataset.
  The evaluation is conducted with 1 Nvidia 2080Ti GPU. }
  \scalebox{1.0}{
  \begin{tabular}{ccccc}
      \toprule
      \multicolumn{2}{l}{Methods}  & PER(\%) & Latency(ms) & Speedup\\
      \midrule
      \multicolumn{2}{l}{DualLip~\cite{chen2020duallip}}                 & 46.200   & 4580.0 & 1.00$\times$\\
      \multicolumn{2}{l}{SimulLR~($n_f = 3$)}     & {58.182} & 384.93  & 11.91$\times$\\
      \multicolumn{2}{l}{SimulLR~($n_f = 5$)}     & {56.029} & 502.83  & 9.10$\times$\\
      \multicolumn{2}{l}{SimulLR~($n_f = 20$)}    & {49.743} & 973.62  & 4.70$\times$\\
      \bottomrule
  \end{tabular}
}
\label{table:latency_result}
\end{table}

\subsection{Main Results}
Since prior methods are trained in a non-simultaneous setting, to verify the effectiveness of our proposed methods,
we first build several simultaneous lip reading baselines as follows:

\noindent\textbf{LR-RNN-CTC.}
Using the convolutional network and uni-directional recurrent neural network as visual encoder, we train the simultaneous
model with the mentioned CTC loss.
Note that RNN is already a natural memory network to organize the history information.

\noindent\textbf{LR-RNN-TD.}
Further considering the syntactic structure of generated sequences, we introduces language model and train the simultaneous
model with the transducer loss.

\noindent\textbf{LR-TM-CTC.}
By replacing the RNN sequence encoder with the popular transformer architecture, we train the model with the mentioned CTC loss.

\noindent\textbf{LR-TM-TD.}
With the transformer architecture, we introduce the language model and train the network with the transducer loss.

We compare our methods with some mainstream state-of-the-art non-simultaneous models and the constructed baselines.
The overall evaluation results on two datasets are presents in Table~\ref{table:main_result}.
We can see that (1) The proposed SimulLR outperforms all the simultaneous baselines by a large margin, indicating
the effectiveness of our method for simultaneous lip reading. (2) The SimulLR also achieves comparable results
with the state-of-the-art non-simultaneous method DualLip~\cite{chen2020duallip}, especially on GRID datasets,
demonstrating the potential of our method. (3) With the same visual encoder, the transducer-based models obtain better
performance than CTC-based models, verifying the effectiveness of modeling of syntactic structure.

\begin{figure}[t]
  \includegraphics[width=0.9\linewidth]{figures/length_latency-eps-converted-to.pdf}
  \caption{
      The NCA latency of target sentences with different length for DualLip and SimulLR
      on TCD-TIMIT dataset.
  }
  \label{fig:nca_length}
\end{figure}

\begin{figure}[t]
  \includegraphics[width=0.9\linewidth]{figures/nca_tcd-eps-converted-to.pdf}
  \caption{
      The recognition accuracy against the NCA latency with different segment size $n_f$
      on TCD-TIMIT dataset.
  }
  \label{fig:nca_tcd}
\end{figure}

\subsection{Latency Analysis}
In this section, to further explore the time-efficiency of the proposed SimulLR method,
we record the prediction latency of both simultaneous and non-simultaneous models
to make a comparison.

We first measure the inference NCA latency and corresponding recognition accuracy of DualLip~\cite{chen2020duallip} and SimulLR
with $n_f = 5$ and $n_f = 20$, which is listed in Table~\ref{table:latency_result}.
As the results shows, compared with the non-simultaneous method DualLip,
the SimulLR speeds up the prediction by 9.10$\times$ with $n_f = 5$, and 4.70$\times$ with $n_f = 20$.
Also, the SimulLR~($n_f = 20$) even achieves competitive results~(PER 49.743\%) with less waiting time,
indicating the great ability of the adaptive memory to incorporate history information.
The speedup rate increases rapidly especially for longer sentences, as shown in Figure~\ref{fig:nca_length}.
During inference, the non-simultaneous models wait for the entire video to process, making the NCA latency increases
with respect to the length of target sequence, while the NCA latency nearly holds a small constant for SimulLR.
Further, considering the computation-aware~(CA) latency
that is the time elapsing from the processing of corresponding input to the prediction of a token,
compared with attention-based TM-Seq2Seq~\cite{afouras2018deep},
the SimulLR achieves a speedup of 1.6$\times$ on GPU and 13.3$\times$ on CPU, indicating the effectiveness
of memory to reduce the computation-aware cost.

To explore the performance of simultaneous decoding, we also measure the NCA latency and phoneme error rate with different segment size $n_f$
on TCD-TIMIT dataset, as shown in Figure~\ref{fig:nca_tcd}.
Note that for ``$n_f = {\rm inf}$'', we remove the memory and all the history segments are available.
The recognition accuracy increases as the segment size increases, with the sacrifice of NCA latency.
Notice that the SimulLR~($n_f = 20$) even obtain better performance than model with all the history segments.
which indicates that compared with direct interaction with all the history segments,
the proposed memory can better organize history information, discard obsolete segments
and extract useful context for prediction.

\begin{table}[t]
  \centering
  \caption{The ablation results on the GRID and TCD-TIMIT dataset.
  We add the proposed techniques and evaluate their effectiveness progressively.}
  \scalebox{0.9}{
  \begin{tabular}{ccccc}

      \toprule
      \multicolumn{2}{l}{}       & \multicolumn{2}{c}{GRID} & TCD-TIMIT \\
      \cmidrule(lr){3-4} \cmidrule(lr){5-5}
      \multicolumn{2}{l}{Models} & WER(\%) & CER(\%) & PER(\%)\\
      \midrule
      \multicolumn{2}{l}{Naive LR Transducer}      & {3.125} & {1.588}  & {62.831}\\
      \midrule

      \multicolumn{2}{l}{+CTC}      & {3.029} & {1.503} & {62.032}\\
      \multicolumn{2}{l}{+CTC+TC3D}      & {2.978} & {1.339} & {60.397}\\

      \multicolumn{2}{l}{+CTC+TC3D+WARM}   & {2.963}  & {1.302} & {59.428}\\
      \midrule
      \multicolumn{2}{l}{+CTC+TC3D+WARM+MEM~}      \\
      \multicolumn{2}{l}{(SimulLR)}      & {\bf 2.738} & {\bf 1.201} & {\bf 56.029}\\
      \bottomrule
  \end{tabular}
}
\label{table:ab_result}
\end{table}

\begin{table}[t]
  \centering
  \caption{The effect of different memory strategies on the GRID and TCD-TIMIT dataset.}
  \scalebox{1.0}{
  \begin{tabular}{ccccc}

      \toprule
      \multicolumn{2}{l}{}       & \multicolumn{2}{c}{GRID} & TCD-TIMIT \\
      \cmidrule(lr){3-4} \cmidrule(lr){5-5}
      \multicolumn{2}{l}{Memory strategy} & WER(\%) & CER(\%) & PER(\%)\\
      \midrule
      \multicolumn{2}{l}{FIFO Queue}    & 2.894 & 1.313  & 57.731\\
      \multicolumn{2}{l}{LFU}           & 2.881 & 1.292 & 57.384\\

      \multicolumn{2}{l}{Ours~(LFU + Momentum)}     & {\bf 2.738} & {\bf 1.201} & {\bf 56.029}\\
      \bottomrule
  \end{tabular}
}
\label{table:mem_type_result}
\end{table}

\subsection{Ablation Analysis}
In this section, to explore the effectiveness of the proposed techniques in SimulLR, we first conduct ablation experiments
on the GRID and TCD-TIMIT datasets.
The evaluation results are presented in Table~\ref{table:ab_result}.

\noindent\textbf{Naive LR Transducer~(Base).}
We construct the base model with only the convolutional network and transformer architecture as visual encoder
and the frame-synchronized simultaneous transducer-based decoder.

\noindent\textbf{Base+CTC.}
To stable the training and promote the performance, we first employ the CTC pre-training for base model, and
the results demonstrate that CTC pre-training is helpful for the cross-modal alignment between visual frames
and textual tokens.

\noindent\textbf{Base+CTC+TC3D.}
To enhance the visual representations while maintaining the simultaneous manner, we replace the 2D convolutional network
with truncated C3D layer in the visual encoder, and the results show that the truncated C3D layer can effectively
boost the feature representation ability of visual encoder.

\noindent\textbf{Base+CTC+TC3D+WARM.}
To further improve the performance, we apply the proposed model warm-up strategy where we
train a deeper network step by step.
As shown by the results, the warm-up technique can further facilitate the features learning of visual encoder and
improve the performance.

\noindent\textbf{Base+CTC+TC3D+WARM+MEM.}
With limited history and to reduce the computational cost, we further add the proposed attention-guided adaptive memory
to organize semantic information of history segments and enhance the visual representations.
Table~\ref{table:ab_result} shows that using the adaptive memory can boost the performance significantly, showing that
the proposed memory can effectively organize history information and incorporate global context for visual representations
enhancement.

\begin{table}[t]
  \centering
  \caption{The effect of memory size $k$ on the GRID and TCD-TIMIT dataset.}
  \scalebox{1.0}{
  \begin{tabular}{ccccc}

      \toprule
      \multicolumn{2}{l}{}       & \multicolumn{2}{c}{GRID} & TCD-TIMIT \\
      \cmidrule(lr){3-4} \cmidrule(lr){5-5}
      \multicolumn{2}{l}{Memory size} & WER(\%) & CER(\%) & PER(\%)\\
      \midrule
      \multicolumn{2}{l}{k = 5}       & 2.881 & 1.289  & 56.896\\
      \multicolumn{2}{l}{k = 10}      & 2.796 & 1.259 & 56.528\\
      \multicolumn{2}{l}{k = 20}      & {\bf 2.738} & {\bf 1.201} & {\bf 56.029}\\
      \multicolumn{2}{l}{k = inf}     & {2.760} & {1.236} & {56.173}\\
      \bottomrule
  \end{tabular}
}
\label{table:mem_size_result}
\end{table}

\begin{table}[t]
  \centering
  \caption{The effect of different ways of summarization on the GRID and TCD-TIMIT dataset.}
  \scalebox{1.0}{
  \begin{tabular}{ccccc}

      \toprule
      \multicolumn{2}{l}{}       & \multicolumn{2}{c}{GRID} & TCD-TIMIT \\
      \cmidrule(lr){3-4} \cmidrule(lr){5-5}
      \multicolumn{2}{l}{Summarization} & WER(\%) & CER(\%) & PER(\%)\\
      \midrule
      \multicolumn{2}{l}{conv}      & {2.872} & {1.286} & {57.461}\\
      \multicolumn{2}{l}{max-pooling}      & {2.763} & {1.267} & {57.116}\\
      \multicolumn{2}{l}{avg-pooling}      & {\bf 2.738} & {\bf 1.201} & {\bf 56.029}\\
      \bottomrule
  \end{tabular}
}
\label{table:summarize_result}
\end{table}

Besides, we further study the effectiveness of the proposed adaptive memory from the perspective of
the memory strategy, the memory size and the way to summarize semantic information from new segments.
As results shows in Table~\ref{table:mem_type_result}, we first devise different memory strategies to organize history segments
including first-in-first-out~(FIFO) queue, and attention-guided least frequently used~(LFU) algorithm.
The memory with FIFO queue achieves the worst performance, demonstrating that the LFU can effectively extract useful
history information, while the adaptive memory with momentum updating obtains the best performance, indicating that
the attention-guided strategy with entropy can avoid storing redundant information and enable higher memory efficiency.

We then explore the effect of memory size on the recognition accuracy.
As shown in Table~\ref{table:mem_size_result}, increasing the memory size $k$ can firstly absorb more history information
for better recognition, while there is an error rate increase for ``$k = {\rm inf}$'' where relatively unimportant contexts are introduced
as noise.

We also conduct different ways to summarize semantic information from new segments including convolution, max-pooling
and avg-pooling, and the evaluation results are presented in Table~\ref{table:summarize_result}.
Compared with ``conv'' and ``max-pooling'', the ``avg-pooling'' can better summarize the semantic information of a video
segment.

\begin{figure}[t]
  \includegraphics[width=0.9\linewidth]{figures/alignment1.png}
  \includegraphics[width=0.9\linewidth]{figures/alignment2.png}
  \caption{
    The visualization of monotonic alignment between target sequence and source video on TCD-TIMIT dataset~(memory size $k = 10$).
    The second row represents a longer video with more frames.
    The brightness of the color represents the degree of alignment between tokens and frames.
  }
  \label{fig:tcd_ali}
\end{figure}

\subsection{Qualitative Results}
As shown in Figure~\ref{fig:tcd_ali}, by normalizing the distribution of target token over all frames,
we visualize the monotonic alignment learned by SimulLR between target sequence and source video on TCD-TIMIT dataset.
The brightness of the color represents the matching degree between tokens and frames.
The approximate monotonic alignment in the figure indicates the effectiveness of our proposed methods to learn the cross-modal alignment under simultaneous setting
and with limited history.

\section{Conclusions}
In this paper, we study the task of simultaneous lip reading and devise SimulLR,
a simultaneous lip Reading transducer with attention-guided adaptive memory.
To address the challenging of monotonic alignments while considering the syntactic structure of the generated sentences,
we build a transducer-based model with adaptive memory and design several effective training strategies including CTC pre-training, model warm-up and curriculum learning to promote the training
of the lip reading transducer.
Also, to learn better spatio-temporal representations for simultaneous encoder, we construct a truncated 3D convolution and time-restricted
self-attention layer to perform the frame-to-frame interaction within a video segment.
Further, the history information is always limited due to the storage in real-time scenarios.
To achieve a good trade-off, we devise a novel attention-guided adaptive memory to organize semantic information of history segments and enhance the
visual representations with acceptable computation-aware latency.
Experiments on GRID and TCD-TIMIT datasets shows that the SimulLR outperforms the baselines and has great time-efficiency,
demonstrating the effectiveness of our methods for simultaneous lip reading.

\begin{acks}
  This work was supported in part by the National Key R\&D Program of China under Grant No.2018AAA0100603,
  National Natural Science Foundation of China under Grant No.61836002, No.62072397
  and Zhejiang Natural Science Foundation under Grant LR19F020006.
\end{acks}

\bibliographystyle{ACM-Reference-Format}
\balance


\section{Introduction}
\label{Intro}
In the framework of combinatorial algorithms,  one of the most documented questions consists in the development of methods
in order to generate, exactly once, all the objects in some specific class \cite{LEH64}.
Many topics are concerned by such a problem: suffice it to mention sequence counting \cite{BLPP99},
signal encoding \cite{L81}, and  data compression \cite{R86}.

The so-called {\it binary Gray codes}
first appeared in \cite{G58}:
given a binary alphabet $A$ and some positive integer $n$,
they referred to  sequences  with maximum length of pairwise different $n$-tuples  of characters (that is, words in  $A^n$), provided that any pair of consecutive items  differ by exactly one character.
Shortly after, a similar study was drawn in the framework of non-binary alphabets \cite{C63,E84}.
With regard to other famous combinatorial classes of objects, the  term of {\it combinatorial Gray code}, for its part,
appeared in \cite{JWW80}:
actually,  the difference between successive items, although being fixed, need not to be small \cite{S97}.
Generating all permutations of  a given $n$-element set
constitutes a noticeable example \cite{E73}.
Subsets of fixed size are also concerned \cite{EMcK84},
as well as cross-bifix-free words \cite{BBPSV14}, Debruijn sequences \cite{FM86}, set partitions \cite{K76}, necklaces \cite{RSW92}:
the list is  far to be exhaustive.
Combinatorial Gray sequences are often needed to be {\it cyclic} \cite{CDG92},
 in the sense that
the initial term itself can be retrieved as  successor of the last one.
Such a condition justifies the terminology of {\it Gray cycle} \cite[Sect. 7.2.1.1]{K05}.

In view of some formal framework, we notice that each of the sequences we mentioned above involves some word binary relation $\tau\subseteq A^*\times A^*$, where $A$ stands for a finite alphabet, and $A^*$ for the free monoid it generates.
For its part, the combinatorial class of objects can be modelled by some finite langage $X\subseteq A^*$.
Given  a sequence of words we denote in square brackets the corresponding indices: this will allow us to make a difference from $w_i$, the character in {\it position} $i$ in a given word $w$.
We define a {\it cyclic Gray sequence over $X$, with respect to $\tau$} (for short: {\it $\tau$-Gray cycle over $X$}) as
every finite sequence of words $\left(w_{[i]}\right)_{i\in [0,|X|-1]}$ satisfying each of the three following conditions:
\begin{enumerate}[label={\rm (G\arabic*)},leftmargin=2cm]
\item
\label{iva}
For every word $x\in X$, some $i\in [0,|X|-1]$ exists such that we have $x=w_{[i]}$;
\item
\label{ivb}
 For every $i\in [1,|X|-1] $,  we have $w_{[i]}\in\tau\left(w_{[i-1]}\right)$; in addition, the condition $w_{[0]}\in\tau\left(w_{[|X|-1]}\right)$ holds;
\item
\label{ivc} For every pair $i,j\in [0,|X|-1]$, $i\neq j$ implies $w_{[i]}\neq w_{[j]}$.
\end{enumerate}
With this definition, the set $X$ need not to be {\it uniform} that is, in the Gray cycle the terms may have a variable length.
For instance, given the alphabet $A=\{0,1\}$, take for $\tau$  the word binary relation $\Lambda_1$ which,
with every word $w$ associates all the strings located  within a {\it Levenshtein distance} of $1$ from $w$ (see e.g.  \cite{N21});
with such a relation, the  sequence $(0,00,01,11,10,1)$ is a $\Lambda_1$-Gray cycle over $X=A\cup A^2$.

Actually, in addition to the topics we mentioned above, two other  famous topics are involved by those Gray cycles.
Firstly,  with regard to graph theory, a $\tau$-Gray cycle over $X$ exists if, and only if,
there is some hamiltonian circuit  in the  graph of the relation $\tau$ (see e.g. \cite{S97}).
Secondly, given a binary word relation $\tau\subseteq A^*\times A^*$, and given $X\subseteq A^*$,
if some $\tau$-Gray cycle exists over $X$, then $X$ is $\tau$-{\it closed}  \cite{N21} that is,  the inclusion $\tau(X)\subseteq X$ holds, where $\tau(X)$ stands for the set of the images of the words in $X$ under the relation $\tau$.
Such closed sets actually constitute a special subfamily in the famous {\it dependence systems} (see \cite{C1965,JK1997}).
Notice that,  given a $\tau$-{\it closed}
set $X\subseteq A^*$, there do not necessarily exist non-empty $\tau$-Gray cycles over $X$.
A typical example is provided by $\tau$ being $id_{A^*}$, the identity over $A^*$, with respect to which
every finite set $X\subseteq A^*$ is closed;
however non-empty $\tau$-Gray cycle can exist only over singletons.

In the present paper, given a positive integer $n$, and denoting by $A^{\le n}$ the set of the words with length not greater than $n$, we consider
the family of  all sequences
that can be a $\tau$-Gray cycle over
some subset $X$ of  $A^{\le n}$.
This is a natural question to study those sequences of maximum  length which, of course, correspond to subsets $X$ of maximum cardinality;
such a length, which we denote by $\lambda_{A,\tau}(n)$, means introducing some  complexity measure for the word binary relation $\tau$.
With regard to the preceding examples we have $\lambda_{\{0,1\},\Lambda_1}(2)=6$; moreover,  for every alphabet $A$ and positive integer $n$, the identity $\lambda_{A,id_{A^*}}(n)=1$ holds.
We focus on  the case where $\tau$ is  $\sigma_k$, the so-called {\it $k$-character substitution}:
with every word with length at least $k$, say $w$, this relation associates all  the words $w'$, with $|w'|=|w|$, and such that the character $w'_i$ differs from $w_i$ in exactly $k$ values of  $i\in[1,|w|]$.
As commented in \cite{JK1997,N21}, $\sigma_k$ has noticeable inference in the famous framework of {\it error detection}.
On the other hand,  by definition, $w'\in\sigma_k(w)$ implies $|w'|=|w|$ therefore,  if  there is some $\sigma_k$-Gray cycle over $X$, then $X$ is a uniform set.
From this point of view, the classical Gray codes, which allow to generate all $n$-tuples over $A$,
correspond to $\sigma_1$-Gray cycles over $A^n$, furthermore
we have $\lambda_{A,\sigma_1}(n)=|A|^n$.
In addition, in the case where $A$ is  a binary alphabet,
it can be easily proved that, for every $n\ge3$,  we have $\lambda_{A,\sigma_2}(n)=2^{n-1}$ \cite[Exercice 8, p. 77]{K05}.
However, in the most general case, although an exhaustive description of $\sigma_k$-closed variable-length codes has been  provided in \cite{N21},
the question of computing some $\sigma_k$-Gray cycle of maximum length  has remained open.
In our paper we establish the following result:\\
\ \\
 {\bf Theorem}
 {\it
Let $A$ be  a finite alphabet, $k\ge 1$, and $n\ge k$.
Then exactly one of the following conditions  holds:

{\rm (i)} $|A|\ge 3$, $n\ge k$, and $\lambda_{A,\sigma_k}(n)=|A|^n$;

{\rm (ii)}  $|A|=2$,   $n=k$, and $\lambda_{A,\sigma_k}(n)=2$;

{\rm (iii)}  $|A|=2$,  $n\ge k+1$, $k$ is odd and  $\lambda_{A,\sigma_k}(n)=|A|^n$;

{\rm (iv)} $|A|=2$, $n\ge k+1$, $k$ is even, and $\lambda_{A,\sigma_k}(n)=|A|^{n-1}$.\\
In addition, in each case some $\sigma_k$-Gray cycle of maximum length can be explicitly computed.}

\smallbreak
We now shortly describe the contents of the paper. In  Sect. \ref{Prelim}, we recall the  two famous examples of
the  {\it binary} (resp., $|A|$-{\it ary}) {\it reflected Gray code}.
By applying some induction based methods, in  Sect. \ref{A>3} and  Sect.  \ref{S4}, these sequences allow to compute special families of $\sigma_k$-Gray cycles with maximum length.
In  Sect. \ref{Cons}, in the case where $A$ is a binary alphabet, and $k$ an even positive integer,
we  also compute a  family of  Gray cycles with maximum length;
in addition some further development is raised.
\section{Preliminaries}
\label{Prelim}
Several definitions and notation  have already been fixed.
In  the whole paper, $A$ stands for some finite alphabet, with $|A|\ge 2$.
Given a word $w\in A^*$,  we denote by $|w|$ its length;  in addition, for every $a\in A$, we denote by $|w|_a$  the number of occurrences of the character (or character) $a$ in $w$.\\
\ \\
{\it The reflected binary Gray cycle}\\
Let $A=\{0,1\}$, and $n\ge 1$. The most famous example of $\sigma_1$-Gray cycle over $A^n$ is certainly the  so-called {\it reflected binary Gray code} (see e.g. \cite{G58} or \cite[p. 6]{K05}):
 in the present paper we denoted it by $g^{n,1}$. It can be defined by the recurrent sequence initialized  with  $g^{n,1}_{[0]}=0^n$, and satisfying the following property:
for every $i\in [1,|A|^n-1]$,  a unique integer $j\in [1,n]$ exists such that,  in both  words $g^{n,1}_{[i]}$ and  $g^{n,1}_{[i-1]}$ the corresponding characters in position $j$ differ;
in addition, the position $j$  is chosen to be maximum in such a way that $g^{n,1}_{[i]}\notin\{g^{n,1}_{[0]},\cdots,g^{n,1}_{[i-1]}\}$.
 %
\begin{example}
\label{Ex1}
In what follows we provide a column representation of $g^{2,1}$ and $g^{3,1}$:
$$
{\small
\begin{array}{c}
 g^{2,1}\\ \overbrace{}\\00\\ 01\\11\\~10
\ \\ \ \\ \ \\ \ \\ \ \\
\end{array}
~~~~~~~~~~~~~~~~
\begin{array}{c}
 g^{3,1}
\\ \overbrace{~~~~~~}\\000\\ 001\\ 011\\ 010\\ 110\\ 111 \\101\\ 100\\
\end{array}
}
$$
\end{example}
By construction, for every $n\ge 1$, each of the following identities holds:
\begin{eqnarray}
\label{g-termes-remarquables}
g^{n,1}_{[0]}=0^n,~~g^{n,1}_{[1]}=0^{n-1}1,~~g^{n,1}_{[2^{n}-2]}=10^{n-2}1,~~g^{n,1}_{[2^{n}-1]}=10^{n-1}
\end{eqnarray}
{\it The  $|A|$-ary reflected Gray cycle}\\
The preceding construction can be extended in order to obtain the so-called {\it $|A|$-ary reflected Gray code}  \cite{C63,E84},
a $\sigma_1$-Gray cycle over $A^n$, which we denote by $h^{n,1}$.
Set $A=\{0, \cdots,p-1\}$ and denote  by $\theta$  the cyclic permutation $(0,1,\dots p-1)$.
The sequence  $h^{n,1}$ is initialized with  $h^{n,1}_{[0]}=0^n$.
In addition, for every $i\in [1,|A|^n-1]$, a unique integer $j$ exists such that $c$ and  $d$, the characters respectively in position $j$ in $h^{n,1}_{[i-1]}$ and  $h^{n,1}_{[i]}$,
 satisfy both the following conditions:
(i) $d=\theta (c)$;
(ii) $j$ is the greatest integer in $[1,n]$ such that $h^{n,1}_{[i]}\notin\{h^{n,1}_{[0]},\cdots,h^{n,1}_{[i-1]}\}$.
\begin{example}
\label{Ex2}
For $A=\{0,1,2\}$ the sequence $h^{3,1}$
is the concatenation in this order of the three following subsequences:
$$
{\small
\begin{array}{c}
h^{3,1}
\\ \overbrace{~~~~~~}\\000\\ 001\\ 002\\ 012\\ 010\\ 011 \\021\\ 022\\  020
\end{array}
~~~~~~~~
\begin{array}{c}
\ \\ \ \\ 120\\ 121\\ 122\\ 102\\ 100\\ 101 \\111\\  112\\110
\end{array}
~~~~~~~~
\begin{array}{c}
\ \\ \ \\  210\\ 211\\ 212\\ 222\\ 220 \\221\\ 201\\  202\\200
\end{array}
}
$$
\end{example}
\section{The case where we have $k\ge 1$ and $|A|\ge 3$}
\label{A>3}
Let  $n\ge k\ge 1$, $p\ge 3$, and $A=\{0,1,\cdots,p-1\}$. We will indicate the construction of  a peculiar  $\sigma_k$-Gray cycle over $A^n$, namely  $ h^{n,k}$.
This will be done by applying some induction over $k\ge 1$: in view of that we set $n_0=n-k+1$.
The starting point corresponds to $h^{n_0,1}$, the  $p$-ary reflected Gray code over  $A^{n_0}$ as reminded  in  Sect. \ref{Prelim}.
 For the induction stage, starting with some $\sigma_{k-1}$-Gray cycle over $A^{n-1}$, namely   $ h^{n-1,k-1}$,
we compute the sequence $ h^{n,k}$ as indicated in what follows:
let $i\in [0,p^{n}-1]$, and let $q\in [0,p-1]$, $r\in [0,p^{n-1}-1]$ be  the unique pair of non-negative integers such that $i=qp^{n-1}+r$. We  set:
\begin{eqnarray}
\label{Gamma-A-ge3}
h^{n,k}_{[i]}=h^{n,k}_{[qp^{n-1}+r]}=
\theta^{q+r}(0) h^{n-1,k-1}_{[r]}
\end{eqnarray}
As illustrated by Example \ref{E3}, the resulting sequence  $ h^{n,k}$ is actually the concatenation in this order of $p$ subsequences namely $C_0, \dots,  C_{p-1}$,
with $C_q=\left( h^{n,k}_{[qp^{n-1}+r]}\right)_{0\le r\le p^{n-1}-1}$, for each $q\in [0,p-1]$.
Since $\theta$ is one-to-one, given a pair of different integers $q,q'\in [0,p-1]$,
for every  $r\in [0,p^{n-1}-1]$,  in each of  the  subsequences $C_q$, $C_{q'}$, the words  $h^{n,k}_{[qp^{n-1}+r]}$ and $h^{n,k}_{[q'p^{n-1}+r]}$ only differ in their initial characters,
which  respectively are $\theta^{q+r}(0)$ and $\theta^{q'+r}(0)$.
In addition, since $h^{n-1,k-1}$ is a $\sigma_{k-1}$-Gray cycle over $A^{n-1}$, we have $\left | h^{n,k}\right |=p\left | h^{n-1,k-1}\right |=p^n$.
\begin{example}
\label{E3}
{\rm Let $A=\{0,1,2\}$,  $n=3$, $k=2$, thus  $p=3$, $n_0=2$. By starting with the sequence $h^{n-1,k-1}=h^{2,1}$,
$ h^{n,k}$ is  the concatenation of $C_0$, $C_1$, and $C_2$ :
$$
{\small
\begin{array} {c}
 h^{n-1,k-1}\\ \overbrace{~~~~~}\\00\\ 01\\ 02\\ 12\\ 10\\ 11 \\21\\ 22\\~20
\ \\ \ \\
\end{array}
~~~~~~~~~~~~~~~~
\begin{array}{c}
 h^{n,k}
\\ \overbrace{~~~~~~}\\000\\ 101\\ 202\\ 012\\ 110\\ 211 \\021\\ 122\\ 220\\
\\
\end{array}
~~~~~
\begin{array}{c}
\ \\100 \\ 201\\ 002\\ 112\\ 210\\ 011 \\121\\ 222\\ 020
\end{array}
~~~~~
\begin{array}{c}
\ \\ 200\\ 001\\ 102\\ 212\\ 010\\ 111\\ 221\\ 022\\ 120\\
\end{array}
}
$$
}
\end{example}
\begin{proposition}
\label{Cycle-Age3-n-k}
$h^{n,k}$
is a $\sigma_k$-Gray cycle over $A^n$.
\end{proposition}
\begin{proof}
We argue by induction over $k\ge 1$.
With regard to the base case, as indicated above  $h^{n_0,1}$
 is the $|A|$-ary reflected Gray sequence.
In view of the induction stage, we assume that the finite sequence $ h^{n-1,k-1}$ is a  $\sigma_{k-1}$-Gray cycle over $A^{n-1}$, for some $k\ge 2$.\\
(i) We start by proving that $h^{n,k}$ satisfies Condition  \ref{ivb}. This will be  done through the three following steps:

(i.i) Firstly, we prove that, for each $q\in [0,p-1]$, in  the subsequence $C_q$
two consecutive terms  are necessarily in correspondence under $\sigma_k$.
Given $r\in [0, p^{n-1}-1]$, by definition, we have $\theta^{r+q}(0)\in\sigma_1\left(\theta^{r+q-1}(0)\right)$.
Since $ h^{n-1,k-1}$ satisfies Condition \ref{ivb},  we have  $ h^{n-1,k-1}_{[r]}\in\sigma_{k-1}\left( h^{n-1,k-1}_{[r-1]}\right)$.
We obtain $\theta^{r+q}(0) h^{n-1,k-1}_{[r]}\in\sigma_k\left(\theta^{r+q-1}(0) h^{n-1,k-1}_{[r-1]}\right)$, thus  according to (\ref{Gamma-A-ge3}):
$h^{n,k}_{[qp^{n-1}+r]}\in\sigma_k\left( h^{n,k}_{[qp^{n-1}+r-1]}\right)$.

(i.ii) Secondly, we prove that, for each $q\in [1,p-1]$, the last term of $C_{q-1}$
and the initial term of $C_{q}$ are also connected by $\sigma_k$.
Take $r=0$ in Eq.  (\ref{Gamma-A-ge3}):
it follows from $\theta^{p^{n-1}}=id_A$ that we have
$h^{n,k}_{[qp^{n-1}]}=\theta^{q}(0) h^{n-1,k-1}_{[0]}=\theta^{p^{n-1}+q}(0) h^{n-1,k-1}_{[0]}$.
In (\ref{Gamma-A-ge3}) take $r=p^{n-1}-1$, moreover substitute $q-1\in [0,p-2]$ to $q\in [1,p-1]$: we obtain
$h^{n,k}_{[qp^{n-1}-1]}=\theta^{q+p^{n-1}-2}(0) h^{n-1,k-1}_{[p^{n-1}-1]}$.
It follows from $p=|A|\ge 3$ that $\theta(0)\neq\theta^{-2}(0)$: since $\theta$ is one-to-one this implies
$\theta^{q+p^{n-1}}(0)\neq \theta^{q+p^{n-1}-2}(0)$, thus  $\theta^{q+p^{n-1}}(0)\in\sigma_1\left(\theta^{q+p^{n-1}-2}(0)\right)$.
By induction
we have $ h^{n-1,k-1}_{[0]}=\sigma_{k-1}\left( h^{n-1,k-1}_{[p^{n-1}-1]}\right)$, thus
$h^{n,k}_{[qp^{n-1}]}\in\sigma_k\left(\theta^{q+p^{n-1}-2}(0) h^{n-1,k-1}_{[qp^{n-1}-1]}\right)$ that is,
 $h^{n,k}_{[qp^{n-1}]}\in\sigma_k\left( h^{n,k}_{[qp^{n-1}-1]}\right)$.

(i.iii)
At last, we  prove that the first term of $C_0$ is an image under $\sigma_k$ of the last term of $C_{p-1}$.
In  Eq. (\ref{Gamma-A-ge3}), take  $q=0$ and $r=0$: we obtain $h^{n,k}_{[0]}=0h^{n-1,k-1}_{[0]}$.
Similarly, by setting $q=p-1$ and $r=p^{n-1}-1$,
we obtain $h^{n,k}_{[(p-1)p^{n-1}+p^{n-1}-1]}=\theta^{p^{n-1}+p-2}(0) h^{n-1,k-1}_{[p^{n-1}-1]}$,
thus $h^{n,k}_{[p^n-1]}=\theta^{-2}(0)h^{n-1,k-1}_{[p^{n-1}-1]}$.
Since $ h^{n-1,k-1}$  is a $\sigma_{k-1}$-Gray cycle over $A^{n-1}$, we have $ h^{n-1,k-1}_{[0]}\in\sigma_{k-1}\left( h^{n-1,k-1}_{[p^{n-1}-1]}\right)$.
In addition, it follows from $p\ge 3$, that $\theta^{-2}(0)\neq 0$, thus $0\in\sigma_1\left(\theta^{-2}(0)\right)$.
We obtain
$ h^{n,k}_{[0]}
\in\sigma_k\left(\theta^{-2}(0)h^{n-1,k-1}_{[p^{n-1}-1]}\right)$, thus  $h^{n,k}_{[0]}\in\sigma_k\left( h^{n,k}_{[p^{n}-1]}\right)$ that is, the required property.\\
(ii) Now, we prove that,
in the sequence $ h^{n,k}$ all terms are pairwise different.
Let $i,i'\in [0,p^n-1]$ such that $h^{n,k}_{[i]}= h^{n,k}_{[i']}$ and consider the unique  $4$-tuple  of integers
$q,q'\in[0,p-1]$, $r,r'\in [0,p^{n-1}-1]$ such that $i=qp^{n-1}+r$ and $i'=q' p^{n-1}+r'$.
According to  (\ref{Gamma-A-ge3}) we have $\theta^{q+r}(0)h^{n-1,k-1}_{[r]}=\theta^{q'+r'}(0)h^{n-1,k-1}_{[r']}$, thus
$\theta^{q+r}(0)=\theta^{q'+r'}(0)\in A$ and $h^{n-1,k-1}_{[r]}=h^{n-1,k-1}_{[r']}$.
Since $h^{n-1,k-1}$ satisfies \ref{ivc}, the second equation implies $r=r'$, whence
 the first one implies $\theta^{q}(0)=\theta^{q'}(0)$, thus  $q=q'\bmod p$. Since we have $q,q'\in [0,p-1]$ we obtain $q=q'$, thus  $i=i'$.\\
(iii)  Finally, since $ h^{n,k}$ satisfies  \ref{ivc}, we have $\left|\bigcup_{0\le i\le p^{n}-1}\{h^{n,k}_{[i]}\}\right|=p^{n}$, hence $ h^{n,k}$ satisfies Condition \ref{iva}.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$\square$
\end{proof}
\section{The case where $A$ is a binary alphabet, with $k$ odd}
\label{S4}
Let $A=\{0,1\}$ and $n\ge k$.
Classically, the cyclic permutation  $\theta$, which was introduced in  Sect. \ref{Prelim}, can be extended into a one-to-one monoid homomorphism onto $A^*$:
in view of this, we set $\theta(\varepsilon)=\varepsilon$ and,  for any non-empty $n$-tuple of characters $a_1,\cdots, a_n\in A$, $\theta(a_1\cdots a_n)=\theta(a_1)\cdots\theta(a_n)$.
Trivially, in the case where we have $n=k$, if a non-empty $\sigma_k$-Gray code exists over $X\subseteq A^n$, then  we have $X=\{x,\theta(x)\}$, for some $x\in A^n$.
In the sequel of the paper, we assume $n\ge k+1$.
In what follows, we indicate the construction of a peculiar  pair of  $\sigma_k$-Gray cycles over $A^n$, namely $\gamma^{n,k}$ and $\rho^{n,k}$.
This will be done by induction over $k'$, the unique non-negative integer such that  $k=2k'+1$. Let $n_0=n-2k'=n-k+1$.\\
-- For the base case, $\gamma^{n_0,1}$ and $\rho^{n_0,1}$ are computed by applying  some
reversal (resp., shift) over the sequence $g^{n_0,1}$ from   Sect. \ref{Prelim}:
\begin{eqnarray}
\label{gamma-init}
\gamma^{n_0,1}_{[0]}=g^{n_0,1}_{[0]}~~{\rm and}~~
\gamma^{n_0,1}_{[i]}=g^{n_0,1}_{[2^{n_0}-i]}~~(1\le i\le 2^{n_0}-1);\\
\label{gamma-init1}
\rho^{n_0,k}_{[0]}=g^{n_0,1}_{[2^{n_0}-1]}~~{\rm and}~~
\rho^{n_0,k}_{[i]}=g^{n_0,1}_{[i-1]}~~(1\le i\le 2^{n_0}-1).
\end{eqnarray}
By construction,  $\gamma^{n_0,1}$ and $\rho^{n_0,1}$ are $\sigma_1$-Gray cycles over $A^{n_0}$. Moreover we have:
\begin{eqnarray}
\label{termes-initiaux}
\gamma^{n_0,1}_{[0]}=g^{n_0,1}_{[0]}=0^{n_0}~~{\rm and}~~\rho^{n_0,1}_{[0]}=g^{n_0,1}_{[2^{n_0}-1]}=10^{n_0-1};\\
\label{termes-initiaux1}
\gamma^{n_0,1}_{[2^{n_0}-1]}=g^{n_0,1}_{[1]}=0^{n_0-1}1~~{\rm and}~~\rho^{n_0,1}_{[2^{n_0}-1]}=g^{n_0,1}_{[2^{n_0}-2]}=10^{n-2}1.
\end{eqnarray}
\begin{example}
\label{Ex3}
For $n_0=3$ we obtain the following sequences:
$$
{\small
\begin{array} {c}
g^{3,1}\\ \overbrace{~~}\\ 000\\ 001\\ 011\\ 010\\ 110\\ 111\\ 101\\ 100
\end{array}
~~~~~~~~~~~~~~~~~
\begin{array} {c}
\gamma^{3,1}\\ \overbrace{~~}\\ 000\\ 100\\ 101\\ 111\\ 110\\ 010\\ 011\\ 001
\end{array}
~~~~~~~~~~~~~~~~~
\begin{array} {c}
\rho^{3,1}\\ \overbrace{~~}\\ 100\\ 000\\ 001\\ 011\\ 010\\ 110\\ 111\\ 101
\end{array}
}
$$
\end{example}
-- In view of the induction step, we assume that we have computed  the $\sigma_k$-Gray cycles $\gamma^{n,k}$ and $\rho^{n,k}$.
Notice that we have $n+2=n_0+2(k'+1)=n_0+(k+2)-1$:
below we explain  the construction of  the two corresponding $2^{n+2}$-term sequences $\gamma^{n+2,k+2}$ and $\rho^{n+2,k+2}$.
Let $i\in [0,2^{n+2}-1]$, and let $q\in [0,3]$, $r\in [0,2^{n}-1]$ be the unique pair of integers such that $i=q2^n+r$.
Since we have $r\in [0,2^{n}-1]$, taking for $q$ the value  $q=0$ (resp., $1$, $2$, $3$), we state the corresponding equation (\ref{6}) {\large (}resp., (\ref{7}),(\ref{8}),(\ref{9}) {\large)}:
\begin{subeqnarray}
\gamma^{n+2,k+2}_{[r]}=\theta^{r}(00)\gamma^{n,k}_{[r]}; \slabel{6}\\
\gamma^{n+2,k+2}_{[2^n+r]}=\theta^{r}(01)\rho^{n,k}_{[r]}; \slabel{7}\\
\gamma^{n+2,k+2}_{[2.2^n+r]}=\theta^{r}(11)\gamma^{n,k}_{[r]}; \slabel{8}\\
\gamma^{n+2,k+2}_{[3.2^n+r]}=\theta^{r}(10)\rho^{n,k}_{[r]}. \slabel{9}
\end{subeqnarray}
Similarly the sequence $\rho^{n+2,k+2}$ is computed by substituting,  in the preceding equations, the $4$-tuple
$(10,11,01,00)$ to $(00,01,11,10)$:
\begin{subeqnarray}
\rho^{n+2,k+2}_{[r]}=\theta^{r}(10)\gamma^{n,k}_{[r]}; \slabel{10}\\
\label{H2} \rho^{n+2,k+2}_{[2^n+r]}=\theta^{r}(11)\rho^{n,k}_{[r]}; \slabel{11}\\
\label{H3} \rho^{n+2,k+2}_{[2.2^n+r]}=\theta^{r}(01)\gamma^{n,k}_{[r]}; \slabel{12}\\
\label{H4} \rho^{n+2,k+2}_{[3.2^n+r]}=\theta^{r}(00)\rho^{n,k}_{[r]}.\slabel{13}
\end{subeqnarray}
\begin{example}
(Example \ref{Ex3} continued)
$\gamma^{5,3}$  is the concatenation,  in this order, of  the $4$  following  subsequences:
$$
{\small
\begin{array} {c}
~~~~~{\scriptstyle\gamma^{3,1}}\\ ~~~~\overbrace{}\\
 00~000\\ 11~100\\ 00~101\\ 11~111\\ 00~110\\ 11~010\\00~011\\ 11~001
\end{array}
~~~~~~~~~~~~~~~~~
\begin{array} {c}
~~~~~~~{\scriptstyle\rho^{3,1}}\\ ~~~~\overbrace{~~~~~ }\\
01~100\\ 10~000\\ 01~001\\ 10~011\\01~010\\ 10~110\\01~111\\ 10~101
\end{array}
~~~~~~~~~~~~~~~~~
\begin{array} {c}
~~~~~~~{\scriptstyle\gamma^{3,1}}\\ ~~~~\overbrace{~~~~~ }\\
11~000\\ 00~100\\ 11~101\\ 00~111\\ 11~110\\ 00~010\\11~011\\ 00~001
\end{array}
~~~~~~~~~~~~~~~~~
\begin{array} {c}
~~~~~~~{\scriptstyle\rho^{3,1}}\\ ~~~~\overbrace{~~~~~ }\\10~100\\ 01~000\\ 10~001\\ 01~011\\10~010\\ 01~110\\10~111\\ 01~101
\end{array}
}
$$
\end{example}
\begin{lemma}
\label{pairwise-different}
$\gamma^{n,k}$ and
$\rho^{n,k}$ satisfy both the conditions \ref{iva} and \ref{ivc}.
\end{lemma}
\begin{proof}
We argue by induction over  $k'\ge 0$, with $k=2k'+1$.
the base case corresponds to  $k'=0$ that is,  $k=1$ and $n=n_0$:
as indicated above, $\gamma^{n_0,1}$ and $\rho^{n_0,1}$ are $\sigma_1$-Gray cycles over $A^{n}$.
In view of  the induction step we assume that, for some $k'\ge 0$, both the sequences
$\gamma^{n,k}$ and $\rho^{n,k}$
are $\sigma_k$-Gray cycles over $A^n$.\\

(i) In order to prove that $\gamma^{n+2,k+2}$ satisfies Condition \ref{ivc},
let $i,i'\in [0,2^{n+2}-1]$ such that
 $\gamma^{n+2,k+2}_{[i]}=\gamma^{n+2,k+2}_{[i']}$, and
$q,q'\in [0,3]$, $r,r'\in [0,2^n-1]$ such that $i=q2^n+r$, $i'=q'2^n+r'$.
According to Eqs. (\ref{6})--(\ref{9}), words $x,x'\in A^2$, $w,w'\in A^n$ exist such that
$\gamma^{n+2,k+2}_{[i]}=\theta^r(x)w$ and $\gamma^{n+2,k+2}_{[i']}=\theta^{r'}(x')w'$ that is,
$\theta^r(x)=\theta^{r'}(x')\in A^2$ and $w=w'$. By the definition of $\theta$, this implies either $x,x'\in\{00,11\}$ or $x,x'\in\{01,10\}$ that is, by construction,
either $q,q'\in\{0,2\}$, $x,x'\in\{00,11\}$, $w=\gamma^{n,k}_{[r]}=\gamma^{n,k}_{[r']}$, or
$q,q'\in\{1,3\}$, $x,x'\in\{01,10\}$, $w=\rho^{n,k}_{[r]}=\rho^{n,k}_{[r']}$.
Since $\gamma^{n,k}$ and $\rho^{n,k}$ satisfies  \ref{ivc}, in any case we have  $r=r'$.
This implies  $\theta^r(x)=\theta^{r}(x')$, thus $x=x'$.
With regard  to  Eqs. (\ref{6})--(\ref{9}), this corresponds to  $q=q'$, thus  $i=q2^n+r=q'2^n+r=i'$, therefore $\gamma^{n+2,k+2}$ satisfies Condition \ref{ivc}.\\
(ii) By substituting  $(10,11,01,00)$ to  $(00,01,11,10)$, according to (\ref{10})--(\ref{13}),
similar arguments prove that $\rho^{n+2,k+2}_{[i]}=\rho^{n+2,k+2}_{[i']}$ implies $i=i'$, thus  $\rho^{n+2,k+2}$ also satisfies \ref{ivc}.\\
 (iii) Since $\gamma^{n+2,k+2}$ satisfies \ref{ivc}, we have
$\bigcup_{0\le i\le 2^{n+2}-1}\{\gamma^{n+2,k+2}_i\}=A^{n+2}$, hence
it satisfies \ref{iva}.
Similarly, since  $\rho^{n+2,k+2}$ satisfies \ref{ivc}
it  satisfies \ref{iva}.
$\square$
\end{proof}
{\flushleft In order to prove that our sequences satisfy \ref{ivb}, we prove the following property:}
\begin{lemma}
\label{For-Gray-connections}
We have $\gamma^{n,k}_{[0]}\in\sigma_{k+1}\left(\rho^{n,k}_{[2^{n}-1]}\right)$ and
$\rho^{n,k}_{[0]}\in\sigma_{k+1}\left(\gamma^{n,k}_{[2^{n}-1]}\right).$
\end{lemma}
\begin{proof}
We argue by induction over the integer $k'\ge 0$.
The case $k'=0$ corresponds to $k=1$ and $n=n_0$: with such a condition, our property  comes from  the identities (\ref{termes-initiaux}) and  (\ref{termes-initiaux1}).
For the induction step, we assume that, for some $k'\ge 0$, we have $\gamma^{n,k}_{[0]}\in\sigma_{k+1}\left(\rho^{n,k}_{[2^{n}-1]}\right)$ and $\rho^{n,k}_{[0]}\in\sigma_{k+1}\left(\gamma^{n,k}_{[2^{n}-1]}\right)$.\\
(i) In  (\ref{6}), by taking $r=0$ we obtain
$\gamma^{n+2,k+2}_{[0]}=00\gamma^{n,k}_{[0]}$, hence by induction:
$\gamma^{n+2,k+2}_{[0]} \in 00\sigma_{k+1}\left(\rho^{n,k}_{[2^{n}-1]}\right)\subseteq \sigma_{k+3}\left(11\rho^{n,k}_{[2^{n}-1]}\right)$.
By setting $r=2^{n}-1$ in  (\ref{13}), we obtain $\rho^{n+2,k+2}_{[2^{n+2}-1]}=11\rho^{n,k}_{[2^{n}-1]}$, thus
$\gamma^{n+2,k+2}_{[0]}\in\sigma_{k+3}\left(\rho^{n+2,k+2}_{[2^{n+2}-1]}\right)$.\\
(ii) Similarly, by setting $r=0$  in  (\ref{10}), and  by induction we have:
$\rho^{n+2,k+2}_{[0]}=10\gamma^{n,k}_{[0]}\in\sigma_{k+3}\left(01\rho^{n,k}_{[2^{n}-1]}\right)$.
By taking $r=2^n-1$ in  (\ref{9}) we obtain $\gamma^{n+2,k+2}_{[2^{n+2}-1]}=01\rho^{n,k}_{[2^n-1]}$, thus  $\rho^{n+2,k+2}_{[0]}\in\sigma_{k+3}\left(\gamma^{n+2,k+2}_{[2^{n+2}-1]} \right)$.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$\square$
\end{proof}
Since Eqs.  (\ref{6})--(\ref{13}) look alike, one may be tempted to compress them thanks to some unique generic formula.
Based on our tests, such a formula needs to introduce at least two additionnal technical parameters, which would make their handling tedious.
In the proof of the following result, we have opted to report some case-by-case basis argumentation:
this has the advantage of making use of arguments which, although being similar, actually are easily readable.
\begin{proposition}
\label{Gamma-n-k-odd}
 Both  the sequences $\gamma^{n,k}$ and $\rho^{n,k}$
are $\sigma_k$-Gray cycles over $A^n$.
\end{proposition}
{\it Proof sketch}
 For the full proof, once more we argue by induction over $k'\ge 0$.
Since $\gamma^{n_0,1}$ and $\rho^{n_0,1}$ are  $\sigma_1$-Gray cycles over $A^n$, the property holds for $k'=0$.
In view of  the induction stage, we assume that, for some $k'\ge 0$ both the sequences $\gamma^{n,k}$ and $\rho^{n,k}$ are  $\sigma_k$-Gray cycles over $A^n$.
According to  Lemma \ref{pairwise-different}, it remains to establish that $\gamma^{n+2,k+2}$ and $\rho^{n+2,k+2}$ satisfy Condition \ref{ivb} that is:
\begin{eqnarray}
\slabel{EQ1}
(\forall q\in \{0,1,2,3\})(\forall r\in [1,2^n-1]) ~\gamma^{n+2,k+2}_{[q2^n+r]}\in\sigma_{k+2}\left(\gamma^{n+2,k+2}_{[q2^n+r-1]}\right);\\
\slabel{EQ2}
(\forall q\in \{1,2,3\})~\gamma^{n+2,k+2}_{[q2^{n}]}\in
\sigma_{k+2}\left(\gamma^{n+2,k+2}_{[q2^{n}-1]}\right);\\
\slabel{EQ3}\gamma^{n+2,k+2}_{[0]}\in\sigma_{k+2}\left(\gamma^{n+2,k+2}_{[2^{n+2}-1]}\right).
\end{eqnarray}
\begin{eqnarray}
\label{EQ4}
(\forall q\in \{0,1,2,3\})(\forall r\in [1,2^n-1]) ~\rho^{n+2,k+2}_{[q2^n+r]}\in\sigma_{k+2}\left(\rho^{n+2,k+2}_{[q2^n+r-1]}\right);\\
\label{EQ5}
(\forall q\in \{1,2,3\})~\rho^{n+2,k+2}_{[q2^{n}]}\in
\sigma_{k+2}\left(\rho^{n+2,k+2}_{[q2^{n}-1]}\right);\\
\label{EQ6}
\rho^{n+2,k+2}_{[0]}\in\sigma_{k+2}\left(\rho^{n+2,k+2}_{[2^{n+2}-1]}\right).
\end{eqnarray}
\begin{itemize}[label=$$, leftmargin =-0.1cm]
\item \underline{{\it Condition} (\ref{EQ1}).}
(i) At first assume $q=0$.
According to (\ref{6}), and since $\gamma^{n,k}$ satisfies \ref{ivb},
we have  $\gamma^{n+2,k+2}_{[r]}= \theta^{r}(00)\gamma^{n,k}_{[r]}\in\theta^{r}(00)\sigma_k\left(\gamma^{n,k}_{[r-1]}\right)$,
thus $\gamma^{n+2,k+2}_{[r]}\in\sigma_{k+2}\left(\theta^{r-1}(00)\gamma^{n,k}_{[r-1]}\right)$.
In  (\ref{6}), substitute $r-1$ to $r$ (we have $0\le r-1\le 2^n-2$):
we obtain  $\gamma^{n+2,k+2}_{[r-1]}=\theta^{r-1}(00)\gamma^{n,k}_{[r-1]}$, thus
$\gamma^{n+2,k+2}_{[r]}\in\sigma_{k+2}\left(\gamma^{n+2,k+2}_{[r-1]}\right)$.\\
(ii)  Now assume   $q=1$.
According to (\ref{7}), and since $\rho^{n,k}$ satisfies \ref{ivb},
we have  $\gamma^{n+2,k+2}_{[2^n+r]}= \theta^{r}(01)\rho^{n,k}_{[r]}\in \sigma_{k+2}\left(\theta^{r-1}(01)\rho^{n,k}_{[r-1]}\right)$.
In (\ref{7}), susbtitute $r-1$ to $r$: we obtain $\gamma^{n+2,k+2}_{[2^n+r-1]}= \theta^{r-1}(01)\rho^{n,k}_{[r-1]}$, thus
$\gamma^{n+2,k+2}_{[2^n+r]}\in\sigma_{k+2}\left(\gamma^{n+2,k+2}_{[2^n+r-1]}\right)$.\\
(iii) For $q=2$, the arguments are similar to those applied in (i) by substituting $\gamma^{n+2,k+2}_{[2\cdot 2^n+r]}$ to $\gamma^{n+2,k+2}_{[r]}$,
 Eqs. (\ref{8}) to  (\ref{6}),
 and $11$ to $00$.\\
(iv)  Similarly, for  $q=3$ the proof is obtained by substituting in (ii)   $\gamma^{n+2,k+2}_{[3\cdot2^{n}+r]}$ to $\gamma^{n+2,k+2}_{[2^n+r]}$,
(\ref{9}) to  (\ref{7}),
and $10$ to $01$.%
\item
\underline{{\it Condition} (\ref{EQ2}).}
(i) Assume $q=1$ and take $r=0$ in  (\ref{7}). According to Lemma \ref{For-Gray-connections},
we obtain $\gamma^{n+2,k+2}_{[2^n]}=01\rho^{n,k}_{[0]}\in 01\sigma_{k+1}\left(\gamma^{n,k}_{[2^n-1]}\right)\subseteq\sigma_{k+2}\left(11\gamma^{n,k}_{[2^n-1]}\right)$.
Take $r=2^n-1$ in  (\ref{6}):
we obtain $\gamma^{n+2,k+2}_{[2^n-1]}=11\gamma^{n,k}_{[2^n-1]}$, thus
$\gamma^{n+2,k+2}_{[2^n]}\in\sigma_{k+2}\left(\gamma^{n+2,k+2}_{[2^n-1]}\right)$.\\
(ii) Now, assume  $q=2$, and
set $r=0$ in Eq. (\ref{8}). According to Lemma \ref{For-Gray-connections}
we have $\gamma^{n+2,k+2}_{[2\cdot2^n]}=11\gamma^{n,k}_{[0]}\in11\sigma_{k+1}\left(\rho^{n,k}_{[2^n-1]}\right)\subseteq \sigma_{k+2}\left(10\rho^{n,k}_{[2^n-1]}\right)$.
By taking $r=2^n-1$ in (\ref{7}), we obtain $\gamma^{n+2,k+2}_{[2\cdot 2^n-1)]}=10\rho^{n,k}_{[2^n-1]}$, thus
$\gamma^{n+2,k+2}_{[2\cdot2^n]}\in\sigma_{k+2}\left(\gamma^{n+2,k+2}_{[2\cdot2^n-1]}\right)$.\\
(iii)  For  $q=3$, substitute  in (i) $\gamma^{n+2,k+2}_{[3\cdot 2^n]}$ to $\gamma^{n+2,k+2}_{[2^n]}$,
Eq. (\ref{9}) to  Eq. (\ref{7}),  (\ref{8}) to  (\ref{6}), $10$ to $01$ and $00$ to $11$: similar arguments  prove that
$\gamma^{n+2,k+2}_{[3\cdot2^n]}\in\sigma_{k+2}\left(\gamma^{n+2,k+2}_{[3\cdot2^n-1]}\right)$. \\
\item
\underline{{\it Condition} (\ref{EQ3}).}
Take $r=0$  in  (\ref{6}). According to Lemma \ref{For-Gray-connections}, we have  $\gamma^{n+2,k+2}_{[0]}=00\gamma^{n,k}_{[0]}\in 00\sigma_{k+1}\left(\rho^{n,k}_{[2^n-1]}\right)\subseteq\sigma_{k+2}\left(01\rho^{n,k}_{[2^n-1]}\right)$.
By taking $r=2^n-1$ in (\ref{9}) we obtain
$\gamma^{n,k}_{[2^{n+2}-1]}=01\rho^{n,k}_{[2^n-1]}$, thus
$\gamma^{n+2,k+2}_{[0]}\in\sigma_{k+2}\left(\gamma^{n,k}_{[2^{n+2}-1]}\right)$.
\end{itemize}
{\flushleft According to the structures of Eqs. (\ref{10})--(\ref{13}), for proving the conditions (\ref{EQ4})--(\ref{EQ6}),}
the method  consists in substituting
the word $\rho^{n+2,k+2}_{[r]}$ to $\gamma^{n+2,k+2}_{[r]}$, the $4$-uple $(10,11,01,00)$ to $(00,01,11,10)$, and
Eq.   (\ref{10}) {\large (}resp.,  (\ref{11}),  (\ref{12}),  (\ref{13}){\large )} to Eq. (\ref{6})  {\large (}resp.,  (\ref{7}),  (\ref{8}),  (\ref{9}){\large )}.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$\Box$
\section{The case where we have $|A|=2$ and  $k$ even}
\label{Cons}
Beforehand,  we remind some classical algebraic interpretation of the substitution $\sigma_k$  in the framework of the binary alphabet $A=\{0,1\}$.
Denote by $\oplus$ the addition in the group ${\mathbb Z}/2{\mathbb Z}$ with identity $0$.
Given a positive integer $n$,
and  $w,w'\in A^n$, define $w\oplus w'$ as the unique word of $A^n$ such that, for each $i\in [1,n]$:
$(w\oplus w')_i=w_i\oplus w'_i$. With this notation the sets $A^n$ and $({\mathbb Z}/2{\mathbb Z})^n$ are in one-to-one correspondence. Moreover we have
$w'\in\sigma_k(w)$ if, and only if, some word $u\in A^n$ exists such that $|u|_1=k$ and $w=w' {\oplus} u$, therefore if $k$ is even  we have $|w|_1=|w'|_1\bmod 2$.
Consequently, given a  $\sigma_k$-Gray cycle $\left(\alpha_{[i]}\right)_{0\le i\le m}$,
for each $i\in [0,m]$ we have $\left|\alpha_{[i]}\right|_1=\left|\alpha_{[0]}\right|_1\bmod 2$.
As a corollary, setting ${\rm Even}_1^n=\{w\in A^*:|w|_1=0 \bmod 2\}$ and ${\rm Odd}_1^n=\{w\in A^*:|w|_1=1\bmod 2\}$:
\begin{lemma}
\label{parity}
With the condition of  Sect. \ref{Cons},  given a  $\sigma_k$-Gray cycle $\alpha$ over $X$, either we have $X\subseteq {\rm Even}_1^n$, or we have $X\subseteq {\rm Odd}_1^n$.
\end{lemma}
Since $k-1$ is an odd integer, according to Proposition \ref{Gamma-n-k-odd}, the sequence $\gamma^{n-1,k-1}$
is a  $\sigma_{k-1}$-Gray cycle over $A^{n-1}$. We set:
\begin{eqnarray}
\label{Construct}
(\forall i\in [0, 2^{n-1}-1])~~\gamma^{n,k}_{[i]}=\theta^i(0)\gamma^{n-1,k-1}_{[i]}~~{\rm and}
~~\underline{\gamma}^{n,k}_{[i]}=\theta^i(1)\gamma^{n-1,k-1}_{[i]}
\end{eqnarray}
For instance, we have  $\gamma^{6,4}_{[0]}=0 00 000$, $\underline\gamma^{6,4}_{[0]}=1 00 000$, $\gamma^{6,4}_{[1]}=111100$..

\begin{proposition}
\label{Gamma-n-k-even}
 $\gamma^{n,k}$  (resp., $\underline{\gamma}^{n,k}$) is a $\sigma_k$-Gray cycle over  ${\rm Even}_1^{n}$ (resp., ${\rm Odd}^{n}_1$).
\end{proposition}
\begin{proof}
(i) According to Eq. (\ref{Construct}),
 since $\gamma^{n-1,k-1}$ satisfies \ref{ivc}, both the sequences $\gamma^{n,k}$ and $\underline{\gamma}^{n,k}$ also satisfy \ref{ivc}.\\
(ii) By Lemma \ref{parity}, we have $\bigcup_{0\le i\le 2^{n}-1}\left\{\gamma^{n,k}\right\}\subseteq{\rm Even}_1^{n}$
and $\bigcup_{0\le i\le 2^{n}-1}\left\{\underline{\gamma}^{n,k}\right\}\subseteq {\rm Odd}_1^{n}$.
In addition, according to (\ref{Construct}), we have  $\left|\gamma^{n,k}\right|=\left|\underline{\gamma}^{n,k}\right|=\left|\gamma^{n-1,k-1}\right|=2^{n-1}$. This implies
 $\bigcup_{0\le i\le 2^{n}-1}\left\{\gamma^{n,k}\right\}= {\rm Even}_1^{n}$
and $\bigcup_{0\le i\le 2^{n}-1}\left\{\underline{\gamma}^{n,k}\right\}= {\rm Odd}_1^{n}$ that is, $\gamma^{n,k}$ and $\underline\gamma^{n,k}$ satisfy \ref{iva}.\\
(iii) Let $i\in [1, 2^{n-1}-1]$. Since $\gamma^{n-1,k-1}$ satisfies \ref{ivb}, we have $\gamma^{n-1,k-1}_{[i]}\in\sigma_{k-1}\left(\gamma^{n-1,k-1}_{[i-1]}\right)$.
According to (\ref{Construct}), the initial characters of $\gamma^{n,k}_{[i]}$
and  $\gamma^{n,k}_{[i-1]}$ (resp.,  $\underline\gamma^{n,k}_{[i]}$
and  $\underline\gamma^{n,k}_{[i-1]}$) are different, hence we have $\gamma^{n,k}_{[i]}\in\sigma_k\left(\gamma^{n,k}_{[i-1]}\right)$ and $\underline\gamma^{n,k}_{[i]}\in\sigma_k\left(\underline\gamma^{n,k}_{[i-1]}\right)$.
In addition, once more according to (\ref{Construct}) it follows from $\gamma^{n-1,k-1}_{[0]}\in\sigma_{k-1}\left(\gamma^{n-1,k-1}_{[2^{n-1}-1]}\right)$
that $\gamma^{n,k}_{[0]}=0\gamma^{n-1,k-1}_{[0]}\in\sigma_{k}\left(1\gamma^{n-1,k-1}_{[2^{n-1}-1]}\right)\subseteq\sigma_k\left(\gamma^{n,k}_{[2^{n-1}-1]}\right)$, hence $\gamma^{n,k}$ satisfies \ref{ivb}.
Similarly,   $\underline\gamma^{n-1,k-1}_{[0]}\in\sigma_{k-1}\left(\underline\gamma^{n-1,k-1}_{[2^{n-1}-1]}\right)$ implies
$\underline\gamma^{n,k}_{[0]}\in\sigma_k\left(\gamma^{n,k}_{[2^{n-1}-1]}\right)$, hence $\underline\gamma^{n,k}$ satisfies \ref{ivb}.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$\square$
\end{proof}
{\flushleft The following statement provides the description of the  complexity $\lambda_{A,\tau}$:}
\begin{theorem}
\label{H-maximal}
Given a finite alphabet $A$ and $n\ge k\ge 1$, exactly one of the four following properties  holds:

{\rm (i)} $|A|\ge 3$, $n\ge k$, and $\lambda_{A,\sigma_k}(n)=|A|^n$;

{\rm (ii)}  $|A|=2$,   $n=k$, and $\lambda_{A,\sigma_k}(n)=2$;

{\rm (iii)}  $|A|=2$,  $n\ge k+1$, $k$ is odd and  $\lambda_{A,\sigma_k}(n)=2^n$;

{\rm (iv)} $|A|=2$, $n\ge k+1$, $k$ is even, and $\lambda_{A,\sigma_k}(n)=2^{n-1}$.\\
In addition, in each case some $\sigma_k$-Gray cycle of maximum length can be explicitly computed.
\end{theorem}
\begin{proof}
Recall that if some  $\sigma_k$-Gray cycle exists over $X\subseteq A^{\le n}$, necessarily $X$ is a uniform set that is, $X\subseteq A^m$ holds for some $m\ge n$;
hence,  in any case we have $\lambda_{A,\sigma_k}(n)\le |A|^n$.
According to Proposition \ref{Cycle-Age3-n-k}, if we have $|A|\ge 3$ and  $n\ge k$, a $\sigma_k$-Gray cycle exists over $A^n$, hence Property (i) holds.
Similarly, (iii) comes from Proposition \ref{Gamma-n-k-odd}.
As indicated in the preamble of  Sect. \ref{A>3}, Property {\rm (ii)} trivially holds. Finally, according to  Lemma \ref{parity},
given a binary alphabet  $A$, if $k$ is  even  we have $\lambda_{A,\sigma_k}(n)\le 2^{n-1}$, hence (iv) comes from
 Proposition \ref{Gamma-n-k-even}.~~~~~~~~~~~~~~~~~~~~~~~~~~~$\square$
\end{proof}
{\bf Further development}
Since our  Gray cycles  were constructed by applying recursive processes,  it is legitimate to ask whether some method could exist for computing $\gamma^{n,k}_{[i]}$ by directly starting with $\gamma^{n,k}_{[i-1]}$,
as in the case of the classical reflected Gray cycles.
In view of some of our more recent studies, we strongly believe that such algorithms can actually be devised: we hope to develop this point  in a further paper.

On the other hand, it could be of interest to study the behaviour of  $\Lambda_{A,\tau}$ in the framework of other word  binary relations $\tau$,
even in restraining to special families of sets $X\subseteq A^*$, such as variable-length codes.
\bibliographystyle{splncs04}