Univ Paris Est Creteil, LACL, F-94010 Creteil,
Franceluc.dartois@lacl.frhttps://orcid.org/0000-0001-9974-1922 Université
Paris-Saclay, ENS Paris-Saclay, CNRS, LMF, 91190, Gif-sur-Yvette,
Francepaul.gastin@lsv.frhttps://orcid.org/0000-0002-1313-7722 IIT Bombay,
India krishnas@cse.iitb.ac.inhttps://orcid.org/0000-0003-0925-398X Luc
Dartois, Paul Gastin and S. Krishna [500]Theory of computation Transducers
Supported by IRL ReLaX

# SD-Regular Transducer Expressions for Aperiodic Transformations

Luc Dartois  Paul Gastin  Shankara Narayanan Krishna

###### Abstract

FO transductions, aperiodic deterministic two-way transducers, as well as
aperiodic streaming string transducers are all equivalent models for first
order definable functions. In this paper, we solve the long standing open
problem of expressions capturing first order definable functions, thereby
generalizing the seminal SF=AP (star free expressions = aperiodic languages)
result of Schützenberger. Our result also generalizes a lesser known
characterization by Schützenberger of aperiodic languages by SD-regular
expressions (SD=AP). We show that every first order definable function over
finite words captured by an aperiodic deterministic two-way transducer can be
described with an SD-regular transducer expression (SDRTE). An SDRTE is a
regular expression where Kleene stars are used in a restricted way: they can
appear only on aperiodic languages which are prefix codes of bounded
synchronization delay. SDRTEs are constructed from simple functions using the
combinators unambiguous sum (deterministic choice), Hadamard product, and
unambiguous versions of the Cauchy product and the $k$-chained Kleene-star,
where the star is restricted as mentioned. In order to construct an SDRTE
associated with an aperiodic deterministic two-way transducer, (i) we
concretize Schützenberger’s SD=AP result, by proving that aperiodic languages
are captured by SD-regular expressions which are unambiguous and stabilising;
(ii) by structural induction on the unambiguous, stabilising SD-regular
expressions describing the domain of the transducer, we construct SDRTEs.
Finally, we also look at various formalisms equivalent to SDRTEs which use the
function composition, allowing to trade the $k$-chained star for a 1-star.

###### keywords:

transducers, aperiodic functions, regular expressions, transition monoids.

###### category:

##  1 Introduction

The seminal result of Kleene, which proves the equivalence of regular
expressions and regular languages, is among the cornerstones of formal
language theory. The Büchi, Elgot, Trakhtenbrot theorem which proved the
equivalence of regular languages with MSO definable languages, and the
equivalence of regular languages with the class of languages having a finite
syntactic monoid, established the synergy between machines, logic and algebra.
The fundamental correspondence between machines and logic at the language
level has been generalized to transformations by Engelfreit and Hoogeboom
[15], where regular transformations are defined by two way transducers (2DFTs)
as well as by the MSO transductions of Courcelle [9]. A generalization of
Kleene’s theorem to transformations can be found in [3], [4] and [11].

In [3], regular transformations were described using additive cost register
automata (ACRA) over finite words. ACRAs are a generalization of streaming
string transducers (SSTs) [1] which make a single left to right pass over the
input and use a finite set of variables over strings from the output alphabet.
ACRAs compute partial functions from finite words over a finite input alphabet
to a monoid $(\mathbb{D},+,0)$. The main contribution of [3] was to provide a
set of combinators, analogous to the operators used in regular expressions,
which help in forming combinator expressions computing the output of the ACRA
over finite words. The result of [3] was generalized to infinite words in
[11]. The proof technique in [11] is completely different from [3], and, being
algebraic, allows a uniform treatment of the result for transductions over
finite and infinite words. Subsequently, an alternative proof for the result
of [3] appeared in [4].

The class of star-free languages form a strict subset of regular languages. In
1965, Schützenberger [21] proved his famous result that star-free languages
(SF) and languages having an aperiodic syntactic monoid (or aperiodic
languages AP) coincide over finite words (SF=AP). This equivalence gives an
effective characterization of star-free languages, since one can decide if a
syntactic monoid is aperiodic. This was followed by a result [18] of
McNaughton and Papert proving the equivalence of star-free languages with
counter-free automata as well as first order logic, thereby completing the
machine-logic-algebra connection once again. The generalization of this result
to transformations has been investigated in [8], [16], proving the equivalence
of aperiodic two way transducers and FO transductions a la Courcelle for
finite and infinite words. The counter part of regular expressions for
aperiodic languages are star-free expressions, which are obtained by using the
complementation operation instead of Kleene-star. The generalization of this
result to transformations has been an open problem, as mentioned in [3], [4]
and [11]. One of the main challenges in generalizing this result to
transformations is the difficulty in finding an analogue for the
complementation operation on sets in the setting of transformations.

Our Contributions. The following central problem remained open till now: Given
an aperiodic 2DFT $\mathcal{A}$, does there exist a class of expressions over
basic functions and regular combinators such that, one can effectively compute
from $\mathcal{A}$, an expression $E$ in this class, and conversely, such that
$[\\![\mathcal{A}]\\!](w)=[\\![E]\\!](w)$ for each
$w\in\mathsf{dom}(\mathcal{A})$? We solve this open problem, by providing a
characterization by means of expressions for aperiodic two way transducers. In
the following, we describe the main steps leading to the solution of the
problem.

Concretizing Schützenberger’s characterization. In 1973, Schützenberger [22]
presented a characterization of aperiodic languages in terms of rational
expressions where the star operation is restricted to prefix codes with
bounded synchronization delay and no complementation is used. This class of
languages is denoted by SD, and this result is known as SD=AP. To circumvent
the difficulty of using complementation in star-free expressions, we use this
SD=AP characterization of aperiodic languages by SD-expressions. An SD-
expression is a regular expression where the Kleene stars are restricted to
appear only on prefix codes of bounded synchronization delay. Our _first_
contribution is to concretize Schützenberger’s result to more specific SD-
expressions. We show that aperiodic languages can be captured by _unambiguous_
, _stabilising_ , SD-expressions. The _unambiguity_ of an expression refers to
the unique way in which it can be parsed, while _stabilising expressions_ is a
new notion introduced in this paper. Our concretization, (Theorem 3.6) shows
that, given a morphism $\varphi$ from the free monoid $\Sigma^{*}$ to a finite
aperiodic monoid $M$, for each $s\in M$, $\varphi^{-1}(s)$ can be expressed by
an unambiguous, stabilising SD-expression. The two notions of _unambiguity_
and _stabilising_ help us to capture the runs of an aperiodic two way
transducer. These two notions will be described in detail in Section 3.

The Combinators. Our _second_ contribution is the definition of SD-regular
transducer expressions (SDRTE). These are built from basic constant functions
using combinators such as unambiguous sum, unambiguous Cauchy product,
Hadamard product. In addition, we use $k$-chained Kleene star $[L,C]^{k\star}$
(and its reverse) when the parsing language $L$ is restricted to be aperiodic
and a prefix code with bounded synchronisation delay. It should be noticed
that, contrary to the case of regular transducer expressions (RTE) which
define all regular functions, the 2-chained Kleene star $[L,C]^{2\star}$ does
not seem sufficient to define all aperiodic functions (see Section 4.7 as well
as Figure 2), and $k$-chained Kleene stars for arbitrary large $k$ seem
necessary to capture all aperiodic functions.

The semantics of an SDRTE $C$ is a partial function
$[\\![C]\\!]\colon\Sigma^{*}\to\Gamma^{*}$ with domain denoted
$\mathsf{dom}(C)$. An SDRTE of the form ${L}\triangleright{v}$ where
$L\subseteq\Sigma^{*}$ is an aperiodic language and $v\in\Gamma^{*}$ is such
that $[\\![{L}\triangleright{v}]\\!]$ is a constant function with value $v$
and domain $L$. The Hadamard product $C_{1}\odot C_{2}$ when applied to
$w\in\mathsf{dom}(C_{1})\cap\mathsf{dom}(C_{2})$ produces
$[\\![C_{1}]\\!](w)\cdot[\\![C_{2}]\\!](w)$. The unambiguous Cauchy product
$C_{1}\cdot C_{2}$ when applied on $w\in\Sigma^{*}$ produces
$[\\![C_{1}]\\!](u)\cdot[\\![C_{2}]\\!](v)$ if $w$ can be unambiguously
decomposed as $u\cdot v$, with $u\in\mathsf{dom}(C_{1})$ and
$v\in\mathsf{dom}(C_{2})$. The Kleene star $C^{*}$ is defined when
$L=\mathsf{dom}(C)$ is an aperiodic language which is a prefix code with
bounded synchronisation delay. Then $\mathsf{dom}(C^{*})=L^{*}$, and, for
$w=u_{1}u_{2}\cdots u_{n}$ with $u_{i}\in L$, we have
$[\\![C^{*}]\\!](w)=[\\![C]\\!](u_{1})[\\![C]\\!](u_{2})\cdots[\\![C]\\!](u_{n})$.

$q_{0}$$q_{1}$$q_{2}$$q_{3}$$q_{4}$$q_{5}$$q_{6}$$\$/\varepsilon,+1$$a/\varepsilon,+1$${\vdash}/\varepsilon,+1$$\\#/\varepsilon,+1$$a/b,+1$$\$/\varepsilon,-1$$a/\varepsilon,-1$$\\#/\varepsilon,-1$$a/\varepsilon,-1$$\$/\varepsilon,+1$$a/a,+1$$\\#/\varepsilon,+1$$a/\varepsilon,+1$$\$/\varepsilon,+1$
Figure 1: An aperiodic 2DFT $\cal{A}$ computing the partial function
$[\\![{\mathcal{A}}]\\!](\$a^{m_{1}}\\#a^{m_{2}}\$a^{m_{3}}\\#a^{m_{4}}\$\cdots
a^{m_{2k}}\$)=b^{m_{2}}a^{m_{1}}b^{m_{4}}a^{m_{3}}\cdots
b^{m_{2k}}a^{m_{2k-1}}$, for $k\geq 0$. The input alphabet is
$\Sigma=\\{a,\\#,\$\\}$ while the output alphabet is $\Gamma=\\{a,b\\}$.

As an example, consider the SDRTEs $C=C_{1}\cdot C_{2}$,
$C^{\prime}=C^{\prime}_{1}\cdot C^{\prime}_{2}$ and $D=C\odot C^{\prime}$ with
$C_{1}={(a^{*}\\#)}\triangleright{\varepsilon}$,
$C_{2}=({a}\triangleright{b})^{*}\cdot({\$}\triangleright{\varepsilon})$, and
$C^{\prime}_{1}=({a}\triangleright{a})^{*}\cdot({\\#}\triangleright{\varepsilon})$,
$C^{\prime}_{2}={(a^{*}\$)}\triangleright{\varepsilon}$. Then
$\mathsf{dom}(C_{1})=a^{*}\\#=\mathsf{dom}(C^{\prime}_{1})$,
$\mathsf{dom}(C_{2})=a^{*}\$=\mathsf{dom}(C^{\prime}_{2})$, and
$\mathsf{dom}(C)=a^{*}\\#a^{*}\$=\mathsf{dom}(C^{\prime})=\mathsf{dom}(D)$.
Further, $[\\![C_{1}]\\!](a^{m}\\#)=\varepsilon$,
$[\\![C_{2}]\\!](a^{n}\$)=b^{n}$, $[\\![C^{\prime}_{1}]\\!](a^{m}\\#)=a^{m}$,
and $[\\![C^{\prime}_{2}]\\!](a^{*}\$)=\varepsilon$. Also,
$[\\![D]\\!](a^{m}\\#a^{n}\$)=b^{n}a^{m}$. Notice that $\mathsf{dom}(D)$ is a
prefix code with synchronisation delay 1. Hence, we can define the SDRTE
$D^{*}$ which has domain the aperiodic language
$\mathsf{dom}(D^{*})=(a^{*}\\#a^{*}\$)^{*}$, and
$[\\![D^{*}]\\!](a^{2}\\#a^{3}\$a^{4}\\#a^{5}\$)=b^{3}a^{2}b^{5}a^{4}$. The
SDRTE $D^{\prime}=({\$}\triangleright{\varepsilon})\cdot D^{*}$ corresponds to
the aperiodic 2DFT $\mathcal{A}$ in Figure 1:
$[\\![\mathcal{A}]\\!]=[\\![D^{\prime}]\\!]$.

$\textsf{SDRTE}\leftrightarrow$ Aperiodic 2DFT. Our _third_ and main
contribution solves the open problem by proving the effective equivalence
between aperiodic two way transducers and $\textsf{SDRTE}s$ over finite words:

######  Theorem 1.1.

(1) Given an SDRTE, we can effectively construct an equivalent aperiodic 2DFT.
(2) Given an aperiodic 2DFT, we can effectively construct an equivalent SDRTE.

The proof of (1) is by structural induction on the SDRTE. All cases except the
$k$-chained Kleene star are reasonably simple, and it is easy to see how to
construct the equivalent 2DFT. The case of the $k$-chained Kleene star is more
involved. We write $[L,C]^{k\star}$ as the composition of 3 aperiodic
functions $f_{1},f_{2},f_{3}$, where, (i) $f_{1}$ takes as input
$u_{1}u_{2}\cdots u_{n}\in L^{*}$ with $u_{i}\in L$ and produces as output
$\\#u_{1}\\#u_{2}\\#\cdots\\#u_{n}\\#$, (ii) $f_{2}$ takes
$\\#v_{1}\\#v_{2}\\#\cdots\\#v_{m}\\#$ with $v_{i}\in\Sigma^{*}$ as input, and
produces $\\#v_{1}\cdots v_{k}\\#v_{2}\cdots
v_{k+1}\\#\cdots\\#v_{m-k+1}\cdots v_{m}\\#$ as output, (iii) finally, $f_{3}$
takes $\\#w_{1}\\#w_{2}\\#\cdots\\#w_{\ell}\\#$ as input with
$w_{i}\in\Sigma^{*}$ and produces as output $f(w_{1})f(w_{2})\cdots
f(w_{\ell})$. We produce aperiodic 2DFTs for $f_{1},f_{2},f_{3}$, and compose
them, obtaining the required aperiodic 2DFT.

The construction of SDRTE from an aperiodic 2DFT $\mathcal{A}$ is much more
involved, and is based on the transition monoid $\mathsf{TrM}$ of the 2DFT
$\mathcal{A}$. The translation of $\mathcal{A}$ to SDRTE is guided by an
unambiguous, stabilising, SD-regular expression induced by $\mathsf{TrM}$.
These expressions are obtained thanks to Theorem 3.6 applied to the canonical
morphism $\varphi\colon\Sigma\rightarrow\mathsf{TrM}$ where the transition
monoid $\mathsf{TrM}$ of $\mathcal{A}$ is aperiodic. This construction is
illustrated in detail via Examples 5.13, 5.18, 5.19 and 5.22.

Related Work. A natural operation on functions is that of composition. The
composition operation can be used in place of the chained-sum operator of [3],
and also in place of the unambiguous 2-chained iteration of [11], preserving
expressiveness. In yet another recent paper, [17] proposes simple functions
like copy, duplicate and reverse along with function composition to capture
regular word transductions.

A closely related paper to our work is [6], where first-order and regular list
functions were introduced. Using the basic functions reverse, append, co-
append, map, block on lists, and combining them with the function combinators
of disjoint union, map, pairing and composition, these were shown to be
equivalent (after a suitable encoding) to FO transductions a la Courcelle
(extendible to MSO transductions by adding to the basic functions, the prefix
multiplication operation on groups). [6] provides an equivalent
characterization (modulo an encoding) for FO transductions with basic list
functions and combinators.

Contrary to [6] where expressions crucially rely on function composition, we
focus on concatenation and iteration as first class combinators, in the spirit
of Kleene’s theorem and of Schützenberger’s characterisation AP=SD. We are
able to characterise 2DFTs with such SD-regular expressions without using
composition. Hence, our result is fully independent and complementary to the
work in [6]: both formalisms, SDRTEs and list functions are natural choices
for describing first order transductions. Our basic functions and combinators
are inspired from the back and forth traversal of a two way automaton, and the
restrictions on the usage of the Kleene star comes from the unambiguous,
stabilising nature of the expressions capturing the aperiodic domain of the
2DFT. We also study in Section 6 how composition may be used to simplify our
SDRTEs (Theorem 6.1). With composition, $k$-chained Kleene star ($k>1$) is no
more necessary, resulting in an equivalent formalism, namely, SDRTE where we
only use $1$-star. Yet another equivalent formalism is obtained by restricting
SDRTE to simple functions, unambiguous sum, Cauchy product and 1-star, but
adding the functions duplicate and reverse along with composition.

Structure of the paper. In Section 2, we introduce preliminary notions used
throughout the paper. In Section 3 we give a procedure to construct
complement-free expressions for aperiodic languages that suits our approach.
This is a generic result on languages, independent of two-way transducers.
Section 4 presents the combinators and the chain-star operators for our
characterization. The main theorem and technical proofs, which is constructing
SD-regular transducer expressions from a two-way aperiodic transducer, are in
Section 5.

12$a,b$$a,b$12$a,c$$b,c$$a$$b$

##  2 Preliminaries

###  2.1 Rational languages and monoids

We call a finite set $\Sigma$ an _alphabet_ and its elements _letters_. A
finite sequence of letters of $\Sigma$ is called a _word_ , and a set of words
is a _language_. The empty word is denoted $\varepsilon$, and we denote by
$\Sigma^{*}$ the set of all words over the alphabet $\Sigma$. More generally,
given any language $L\subseteq\Sigma^{*}$, we write $L^{*}$ for the _Kleene
star_ of $L$, i.e., the set of words which can be written as a (possibly
empty) sequence of words of $L$. Given a word $u$, we write $|u|$ for the
_length_ of $u$, i.e., its number of letters, and we denote by $u_{i}$ its
$i^{th}$ letter.

A _monoid_ $M$ is a set equipped with a binary associative law, usually
denoted $\cdot$ or omitted when clear from context, and a neutral element
$1_{M}$ for this law, meaning that for any $s\in M$, $1_{M}\cdot s=s\cdot
1_{M}=s$. The set of words $\Sigma^{*}$ can be seen as the free monoid
generated by $\Sigma$ using the concatenation of words as binary law. Given a
_morphism_ $\varphi:\Sigma^{*}\to M$, i.e., a function between monoids that
satisfies $\varphi(\varepsilon)=1_{M}$ and $\varphi(xy)=\varphi(x)\varphi(y)$
for any $x,y$, we say that $\varphi$ recognizes a language
$L\subseteq\Sigma^{*}$ if $M$ is finite and $L=\varphi^{-1}(P)$ for some
$P\subseteq M$. A monoid is called _aperiodic_ if there exists an integer $n$
such that for any element $s$ of $M$, $s^{n}=s^{n+1}$.

######  Example 2.1.

We define the monoids $\widetilde{U}_{n}$, for $n\geq 0$, as the set of
elements $\\{1,s_{1},\ldots,s_{n}\\}$, with $1$ being the neutral element, and
for any $1\leq i,j\leq n$, $s_{i}\cdot s_{j}=s_{i}$. Clearly,
$\widetilde{U}_{n}$ is aperiodic, actually idempotent, as $s_{i}\cdot
s_{i}=s_{i}$ for any $1\leq i\leq n$. For instance, the monoid
$\widetilde{U}_{2}$ is the transition monoid (defined below) of the automaton
below with $\varphi(a)=s_{1}$, $\varphi(b)=s_{2}$ and $\varphi(c)=1$.

_Rational_ languages are languages that can be described by rational
expressions, i.e., sets of words constructed from finite sets using the
operations of concatenation, union and Kleene star. It is well-known that
rational languages are equivalent to _regular_ languages, i.e., languages
accepted by finite automata, and to languages recognized by finite monoids
(and Monadic Second-order logic [7]). _Star-free_ rational expressions are
built from finite sets using the operations of concatenation, union and
complement (instead of Kleene star). They have the same expressive power as
finite aperiodic monoids [21] (as well as counter-free automata and first-
order logic [18]).

###  2.2 Two-way transducers

######  Definition 2.2 (Two-way transducer).

A _(deterministic) two-way transducer_ (2DFT) is a tuple
$\mathcal{A}=(Q,\Sigma,\Gamma,\delta,\gamma,q_{0},F)$ defined as follows:

  * •

$Q$ is a finite set of _states_.

  * •

$\Sigma$ and $\Gamma$ are the finite _input_ and _output alphabets_.

  * •

$\delta:Q\times(\Sigma\uplus\\{{\vdash},{\dashv}\\})\to Q\times\\{-1,+1\\}$ is
the partial _transition function_. Contrary to one-way machines, the
transition function also outputs an integer, indicating the move of the
reading head. The alphabet is enriched with two new symbols ${\vdash}$ and
${\dashv}$, which are endmarkers that are added respectively at the beginning
and at the end of the input word, such that for all $q\in Q$, we have
${\delta(q,{\vdash})\in Q\times\\{+1\\}}$ (if defined), $\delta(q,{\dashv})\in
Q\times\\{-1\\}$ (if defined) and $\delta(q,{\dashv})$ is undefined for $q\in
F$.

  * •

$\gamma:Q\times(\Sigma\uplus\\{{\vdash},{\dashv}\\})\to\Gamma^{*}$ is the
partial _production function_ with same domain as $\delta$.

  * •

$q_{0}\in Q$ is the _initial state_.

  * •

$F\subseteq Q$ is the set of final states.

A _configuration_ $c$ of $\mathcal{A}$ over an input word $w=w_{1}\cdots
w_{|w|}$ is simply a pair $(p,i)$ where $p\in Q$ is the current state and
$0\leq i\leq|w|+1$ is the position of the head on the input tape containing
${\vdash}w{\dashv}$. Two configurations $c=(p,i)$ and $c^{\prime}=(q,j)$ are
_successive_ if we have $\delta(p,w_{i})=(q,d)$ and $i+d=j$, with
$w_{0}={\vdash}$ and $w_{|w|+1}={\dashv}$. In this case, they produce an
output $v=\gamma(p,w_{i})$. Abusing notations we will sometime write
$\gamma(c)$ when the input word $w$ is clear. A run $\rho$ is a sequence of
successive configurations $c_{0}\cdots c_{n}$. The run $\rho$ is _initial_ if
$c_{0}=(q_{0},0)$ and is _final_ if $c_{n}=(q,|w|+1)$ for some $q\in F$. It is
_accepting_ if it is both initial and final.

The _output_ of a run $\rho=c_{0}\cdots c_{n}$ is the concatenation of the
output of the configurations, and will be denoted
$[\\![\rho]\\!]=\gamma(c_{0})\cdots\gamma(c_{n-1})$. Given a deterministic
two-way transducer $\mathcal{A}$ and an input word $w$, there is at most one
accepting run of $\mathcal{A}$ over ${\vdash}w{\dashv}$, which we will denote
$\rho(w)$. The output of $\mathcal{A}$ over $w$ is then
$[\\![\mathcal{A}]\\!](w)=[\\![\rho(w)]\\!]$. The _domain_ of $\mathcal{A}$ is
the set $\mathsf{dom}(\mathcal{A})$ of words $w$ such that there exists an
accepting run of $\mathcal{A}$ over $w$. Finally, the semantics of
$\mathcal{A}$ is the partial function
$[\\![\mathcal{A}]\\!]\colon\Sigma^{*}\to\Gamma^{*}$ defined on
$\mathsf{dom}(\mathcal{A})$ by $w\mapsto[\\![\mathcal{A}]\\!](w)$.

Let $\rho=(p_{0},i_{0})\cdots(p_{n},i_{n})$ be a run over a nonempty word
$w\in\Sigma^{+}$ such that $1\leq i_{j}\leq|w|$ for all $0\leq j<n$. It is a
_left-right_ run if $i_{0}=1$ and $i_{n}=|w|+1$. If this is the case, we say
that $\rho$ is a $(\rightarrow,p_{0},p_{n})$-run. Similarly, it is a _left-
left_
$(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},p_{0},p_{n})$-run
if $i_{0}=1$ and $i_{n}=0$. It is a _right-left_
$(\leftarrow,p_{0},p_{n})$-run if $i_{0}=|w|$ and $i_{n}=0$ and it is a
_right-right_
$(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},p_{0},p_{n})$-run
if $i_{0}=|w|$ and $i_{n}=|w|+1$. Notice that if $|w|=1$, then left-right runs
and right-right runs coincide, also right-left runs and left-left runs
coincide.

######  Remark 2.3.

Given our semantics of two-way transducers, a run associates states to each
position, whereas the classical semantics of one-way automata keeps the states
between two positions. Then, if we consider a word $w=uv$ and a left-left run
$(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},p,q)$
on $v$, we begin on the first position of $v$ in state $p$, and the state $q$
is reached at the end of the run on the last position of $u$. This allows for
easy sequential composition of partial runs when concatenating non empty
words, as the end of a partial run is the start of the next one.

However, in order to keep our figures as readable as possible, we will
represent these states between words. A state $q$ between two words $u$ and
$v$ is to be placed on the first position of $v$ if it is the start of a run
going to the right, and on the last position of $u$ otherwise. For instance,
in Figure 4, state $q_{1}$ is on the first position of $u_{i+1}$ and state
$q_{3}$ is on the last position of $u_{i}$.

##### Transition monoid of a two-way automaton

Let $\mathcal{A}$ be a deterministic two-way automaton (2DFA) with set of
states $Q$. When computing the transition monoid of a two-way automaton, we
are interested in the behaviour of the partial runs, i.e., how these partial
runs can be concatenated. Thus we abstract a given $(d,p,q)$-run $\rho$ over a
word $w$ to a _step_
$(d,p,q)\in\\{\rightarrow,\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},\leftarrow\\}\times
Q^{2}$ and we say that $w$ realises the step $(d,p,q)$. The transition monoid
$\mathsf{TrM}$ of $\mathcal{A}$ is a subset of the powerset of steps:
$\mathsf{TrM}\subseteq\mathcal{P}(\\{\rightarrow,\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},\leftarrow\\}\times
Q^{2})$. The canonical surjective morphism
$\varphi\colon(\Sigma\uplus\\{{\vdash},{\dashv}\\})^{*}\to\mathsf{TrM}=\varphi((\Sigma\uplus\\{{\vdash},{\dashv}\\})^{*})$
is defined for a word $w\in(\Sigma\uplus\\{{\vdash},{\dashv}\\})^{*}$ as the
set of steps realised by $w$, i.e., $\varphi(w)=\\{(d,p,q)\mid\text{there is a
}(d,p,q)\text{-run on
}w\\}\subseteq\\{\rightarrow,\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},\leftarrow\\}\times
Q^{2}$. As an example, in Figure 1, we have

$\varphi(a\\#)=\\{(\rightarrow,q_{1},q_{2}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{1},q_{2}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{3},q_{3}),(\leftarrow,q_{3},q_{4}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{4},q_{4}),(\rightarrow,q_{5},q_{6}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{5},q_{6})\\}\,.$

The unit of $\mathsf{TrM}$ is
$\mathbf{1}=\\{(\rightarrow,p,p),(\leftarrow,p,p)\mid p\in Q\\}$ and
$\varphi(\varepsilon)=\mathbf{1}$.

A 2DFA is _aperiodic_ if its transition monoid $\mathsf{TrM}$ is aperiodic.
Also, a 2DFT is aperiodic if its underlying input 2DFA is aperiodic.

When talking about a given step $(d,p,q)$ belonging to an element of
$\mathsf{TrM}$, we will sometimes forget $p$ and $q$ and talk about a
$d$-step, for
$d\in\\{\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},\rightarrow,\leftarrow\\}$
if the states $p,q$ are clear from the context, or are immaterial for the
discussion. In this case we also refer to a step $(d,p,q)$ as a $d$-step
having $p$ as the starting state and $q$ as the final state.

##  3 Complement-free expressions for aperiodic languages

As the aim of the paper is to obtain rational expressions corresponding to
transformations computed by aperiodic two-way transducers, we cannot rely on
extending the classical (SF=AP) star-free characterization of aperiodic
languages, since the complement of a function is not a function. We solve this
problem by considering the SD=AP characterization of aperiodic languages,
namely prefix codes with bounded synchronisation delay, introduced by
Schützenberger [22].

A language $L$ is called a _code_ if for any word $u\in L^{*}$, there is a
unique decomposition $u=v_{1}\cdots v_{n}$ such that $v_{i}\in L$ for $1\leq
i\leq n$. For example, the language $W=\\{a,ab,ba,bba\\}$ is not a code: the
words $abba,aba\in W^{*}$ have decompositions $a\cdot bba=ab\cdot ba$ and
$a\cdot ba=ab\cdot a$ respectively. A _prefix code_ is a language $L$ such
that for any pair of words $u,v$, if $u,uv\in L$, then $v=\varepsilon$. $W$ is
not a prefix code, while $W_{1}=W\setminus\\{ab\\}$ and
$W_{2}=W\setminus\\{a\\}$ are prefix codes. Prefix codes play a particular
role in the sense that the unique decomposition can be obtained on the fly
while reading the word from left to right.

######  Definition 3.1.

Let $d$ be a positive integer. A _prefix_ code $C$ over an alphabet $\Sigma$
has a synchronisation delay $d$ (denoted $d$-SD) if for all
$u,v,w\in\Sigma^{*}$, $uvw\in C^{*}$ and $v\in C^{d}$ implies $uv\in C^{*}$
(hence also $w\in C^{*}$). An SD prefix code is a prefix code with a bounded
synchronisation delay.

As an example, consider the prefix code $C=\\{aa,ba\\}$ and the word
$ba(aa)^{d}\in C^{*}$. We have $ba(aa)^{d}=uvw$ with $u=b$, $v=(aa)^{d}\in
C^{d}$ and $w=a$. Since $uv\notin C^{*}$, the prefix code $C$ is not of
bounded synchronisation delay. Likewise, $C=\\{aa\\}$ is also not of bounded
synchronisation delay. On the other hand, the prefix code $C=\\{ba\\}$ is
1-SD.

The syntax of regular expressions over the alphabet $\Sigma$ is given by the
grammar

$E::=\emptyset\mid\varepsilon\mid a\mid E\cup E\mid E\cdot E\mid E^{*}$

where $a\in\Sigma$. We say that an expression is $\varepsilon$-free (resp.
$\emptyset$-free) if it does not use $\varepsilon$ (resp. $\emptyset$) as
subexpressions. The semantics of a regular expression $E$ is a regular
language over $\Sigma^{*}$ denoted $\mathcal{L}(E)$.

An SD-regular expression is a regular expression where Kleene-stars are
restricted to SD prefix codes: If $E^{*}$ is a sub-expression then
$\mathcal{L}(E)$ is a prefix code with bounded synchronization delay. Thus,
the regular expression $(ba)^{*}$ is a SD-regular expression while $(aa)^{*}$
is not.

The relevance of SD-regular expressions comes from the fact that they are a
complement-free characterization of aperiodic languages.

######  Theorem 3.2.

[22] A language $L$ is recognized by an aperiodic monoid if, and only if,
there exists an SD-regular expression $E$ such that $L=\mathcal{L}(E)$.

Theorem 3.6 concretizes this result, and extends it to get more specific
expressions which are (i) _unambiguous_ , a property required for the regular
combinators expressing functions over words, and (ii) _stabilising_ , which is
a new notion introduced below that suits our need for characterizing runs of
aperiodic two-way transducers. Our proof technique follows the local divisor
technique, which was notably used by Diekert and Kufleitner to lift the result
of Schützenberger to infinite words [12, 13].

A regular expression $E$ is unambiguous, if it satisfies the following:

  1. 1.

for each subexpression $E_{1}\cup E_{2}$ we have
$\mathcal{L}(E_{1})\cap\mathcal{L}(E_{2})=\emptyset$,

  2. 2.

for each subexpression $E_{1}\cdot E_{2}$, each word
$w\in\mathcal{L}(E_{1}\cdot E_{2})$ has a _unique_ factorisation $w=uv$ with
$u\in\mathcal{L}(E_{1})$ and $v\in\mathcal{L}(E_{2})$,

  3. 3.

for each subexpression $E_{1}^{*}$, the language $\mathcal{L}(E_{1})$ is a
_code_ , i.e., each word $w\in\mathcal{L}(E_{1}^{*})$ has a _unique_
factorisation $w=v_{1}\cdots v_{n}$ with $v_{i}\in\mathcal{L}(E_{1})$ for
$1\leq i\leq n$.

######  Definition 3.3.

Given an aperiodic monoid $M$ and $X\subseteq M$, we say that $X$ is
$n$-_stabilising_ if $xy=x$ for all $x\in X^{n}$ and $y\in X$. We say that $X$
is stabilising if it is $n$-stabilising for some $n\geq 1$.

Remark. Stabilisation generalizes aperiodicity in some sense. For
aperiodicity, we require $x^{n}=x^{n+1}$ for each element $x\in M$ and some
$n\in\mathbb{N}$, i.e., all _singleton_ subsets of $M$ should be stabilising.

######  Example 3.4.

Continuing Example 2.1, any subset
$X\subseteq\\{s_{1},\ldots,s_{n}\\}\subseteq\widetilde{U}_{n}$ is
1-stabilising.

As another example, consider the aperiodic 2DFT $\mathcal{A}$ in Figure 1, and
consider its transition monoid $\mathsf{TrM}$. Clearly, $\mathsf{TrM}$ is an
aperiodic monoid. Let $\varphi$ be the morphism from
$(\Sigma\uplus\\{{\vdash},{\dashv}\\})^{*}$ to $\mathsf{TrM}$. Consider the
subset $Z=\\{Y,Y^{2}\\}$ of $\mathsf{TrM}$ where $Y=\varphi(a\\#a\$)$:

$\displaystyle Y$
$\displaystyle=\\{(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{1},q_{4}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{3},q_{3}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{4},q_{4}),(\rightarrow,q_{5},q_{1}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{0},q_{1}),(\leftarrow,q_{2},q_{4}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{4},q_{5}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{6},q_{1})\\}$
$\displaystyle Y^{2}$
$\displaystyle=\\{(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{1},q_{4}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{3},q_{3}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{4},q_{4}),(\rightarrow,q_{5},q_{1}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{0},q_{1}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{2},q_{1}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{4},q_{5}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{6},q_{1})\\}\,.$

It can be seen that $Y^{3}=Y^{2}$, hence $Z$ is 2-stabilising.

Let $\varphi\colon\Sigma^{*}\to M$ be a morphism. We say that a regular
expression $E$ is $\varphi$-_stabilising_ (or simply stabilising when
$\varphi$ is clear from the context) if for each subexpression $F^{*}$ of $E$,
the set $\varphi(\mathcal{L}(F))$ is stabilising.

Continuing Example 3.4, we can easily see that $\varphi(a)$ is idempotent and
we get $\varphi(a^{+}\\#a^{+}\$)=\\{Y\\}$. Since $Y^{3}=Y^{2}$, we deduce that
$(aa^{*}\\#aa^{*}\$)^{*}$ is a stabilising expression. Notice also that, by
definition, expressions without a Kleene-star are stabilising vacuously.

######  Example 3.5.

As a more non trivial example to illustrate stabilising expressions, consider
the 2DFT $\mathcal{A}$ in Figure 2, whose domain is the language
$b(a^{*}b)^{\geq 2}a^{*}$.

$s$$q_{0}$$q_{1}$$q_{2}$$q_{3}$$q_{4}$$q_{5}$$q_{6}$${\vdash}/\varepsilon,+1$$b/\varepsilon,+1$$a/\varepsilon,+1$$b/\varepsilon,+1$$a/\varepsilon,+1$$b/\varepsilon,+1$$a/a,+1$$b/b,-1$$a/\varepsilon,-1$$b/\varepsilon,-1$$a/\varepsilon,-1$$b/\varepsilon,-1$$a/\varepsilon,-1$$b/\varepsilon,+1$$a/a,+1$$b/b,+1$
Figure 2: For $u_{i}\in a^{*}b$, an aperiodic 2DFT $\cal{A}$ computing the
partial function $[\\![{\mathcal{A}}]\\!](bu_{1}u_{2}\cdots
u_{n}a^{k})=u_{3}u_{1}u_{4}u_{2}\cdots u_{n}u_{n-2}a^{k}$ if $n\geq 3$, and
$a^{k}$ if $n=2$. The domain is $b(a^{*}b)^{\geq 2}a^{*}$.

Consider $b(a^{*}b)^{\geq 3}\subseteq\mathsf{dom}(\mathcal{A})$. Note that
$a^{*}b$ is a prefix code with synchronisation delay 1. Let
$X=\varphi(a^{*}b)$, where $\varphi$ is the morphism from
$(\Sigma\uplus\\{{\vdash},{\dashv}\\})^{*}$ to $\mathsf{TrM}$. We will see
that $X$ stabilises.

  * •

First, we have $X=\\{Y_{1},Y_{2}\\}$ where

$Y_{1}=\varphi(b)=\\{\\\
(\rightarrow,s,q_{0}),(\rightarrow,q_{0},q_{1}),(\rightarrow,q_{1},q_{2}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{2},q_{3}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{3},q_{4}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{4},q_{5}),(\rightarrow,q_{5},q_{6}),(\rightarrow,q_{6},q_{0}),\\\
(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},s,q_{0}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{0},q_{1}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{1},q_{2}),(\leftarrow,q_{2},q_{3}),(\leftarrow,q_{3},q_{4}),(\leftarrow,q_{4},q_{5}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{5},q_{6}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{6},q_{0})\\}$

$Y_{2}=\varphi(a^{+}b)=\varphi(ab)=\\{\\\
(\rightarrow,q_{0},q_{1}),(\rightarrow,q_{1},q_{2}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{2},q_{3}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{3},q_{3}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{4},q_{4}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{5},q_{5}),(\rightarrow,q_{6},q_{0}),\\\
(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},s,q_{0}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{0},q_{1}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{1},q_{2}),(\leftarrow,q_{2},q_{3}),(\leftarrow,q_{3},q_{4}),(\leftarrow,q_{4},q_{5}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{5},q_{6}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{6},q_{0})\\}$

  * •

Next, we can check that $X^{2}=\\{Y_{3},Y_{4}\\}$ where

$Y_{3}=Y_{1}Y_{1}=Y_{1}Y_{2}=\\{\\\
(\rightarrow,s,q_{1}),(\rightarrow,q_{0},q_{2}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{1},q_{4}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{2},q_{3}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{3},q_{4}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{4},q_{5}),(\rightarrow,q_{5},q_{0}),(\rightarrow,q_{6},q_{1}),\\\
(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},s,q_{0}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{0},q_{1}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{1},q_{2}),(\leftarrow,q_{2},q_{4}),(\leftarrow,q_{3},q_{5}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{4},q_{0}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{5},q_{6}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{6},q_{0})\\}$

$Y_{4}=Y_{2}Y_{1}=Y_{2}Y_{2}=\\{\\\
(\rightarrow,q_{0},q_{2}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{1},q_{4}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{2},q_{3}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{3},q_{3}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{4},q_{4}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{5},q_{5}),(\rightarrow,q_{6},q_{1}),\\\
(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},s,q_{0}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{0},q_{1}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{1},q_{2}),(\leftarrow,q_{2},q_{4}),(\leftarrow,q_{3},q_{5}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{4},q_{0}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{5},q_{6}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{6},q_{0})\\}$

  * •

Then, we have $X^{4}=\\{Z_{1},Z_{2}\\}$ where

$Z_{1}=Y_{3}Y_{3}=Y_{3}Y_{4}=\\{\\\
(\rightarrow,s,q_{2}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{0},q_{5}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{1},q_{4}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{2},q_{3}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{3},q_{4}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{4},q_{5}),(\rightarrow,q_{5},q_{2}),(\rightarrow,q_{6},q_{2}),\\\
(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},s,q_{0}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{0},q_{1}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{1},q_{2}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{2},q_{2}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{3},q_{1}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{4},q_{0}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{5},q_{6}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{6},q_{0})\\}$

$Z_{2}=Y_{4}Y_{3}=Y_{4}Y_{4}=\\{\\\
(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{0},q_{5}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{1},q_{4}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{2},q_{3}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{3},q_{3}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{4},q_{4}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{5},q_{5}),(\rightarrow,q_{6},q_{2}),\\\
(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},s,q_{0}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{0},q_{1}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{1},q_{2}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{2},q_{2}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{3},q_{1}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{4},q_{0}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{5},q_{6}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{6},q_{0})\\}$

  * •

Finally, we can easily check that $Z_{1}Y_{1}=Z_{1}Y_{2}=Z_{1}$ and
$Z_{2}Y_{1}=Z_{2}Y_{2}=Z_{2}$. Therefore, $X$ is 4-stabilising. Moreover,
${b(a^{*}b)^{\geq 3}}\subseteq\varphi^{-1}(Z_{1})$ and ${a^{+}b(a^{*}b)^{\geq
3}}\subseteq\varphi^{-1}(Z_{2})$.

Given a morphism $\varphi$ from $\Sigma^{*}$ to some aperiodic monoid $M$, our
goal is to build, for each language $\varphi^{-1}(s)$ with $s\in M$, an SD-
regular expression which is both _unambiguous_ and _stabilising_. The proof is
by induction on the monoid $M$ via the local divisor technique, similar to
Diekert and Kufleitner [12, 13, 14], and to Perrin and Pin [20, Chapter VIII,
Section 6.1], with the objective to get stronger forms of SD-regular
expressions.

######  Theorem 3.6.

Given a morphism $\varphi$ from the free monoid $\Sigma^{*}$ to a finite
aperiodic monoid $M$, for each $s\in M$ there exists an unambiguous,
stabilising, SD-regular expression $E_{s}$ such that
$\mathcal{L}(E_{s})=\varphi^{-1}(s)$.

The proof of this theorem makes crucial use of _marked substitutions_ (see
[20]) that we define and study in the next section.

###  3.1 Marked substitutions

Let $A,B$ be finite alphabets. A map $\alpha\colon A\to\mathcal{P}(B^{*})$ is
called a _marked substitution_ if it satisfies the following two properties:

  * •

There exists a partition $B=B_{1}\uplus B_{2}$ such that for all $a$ in $A$,
$\alpha(a)\subseteq B_{1}^{*}B_{2}$,

  * •

For all $a_{1}$ and $a_{2}$ in $A$, $a_{1}\neq a_{2}$ implies
$\alpha(a_{1})\cap\alpha(a_{2})=\emptyset$.

A marked substitution $\alpha\colon A\to\mathcal{P}(B^{*})$ can be naturally
extended to words in $A^{*}$ using concatenation of languages, i.e., to a
morphism from the free monoid $A^{*}$ to
$(\mathcal{P}(B^{*}),\cdot,\\{\varepsilon\\})$. It is then further lifted to
languages $L\subseteq A^{*}$ by union: $\alpha(L)=\bigcup_{w\in L}\alpha(w)$.

######  Lemma 3.7 ([20] Chapter VIII, Proposition 6.2).

Let $\alpha\colon A\to\mathcal{P}(B^{*})$ be a marked substitution, and
$X\subseteq A^{+}$ be a prefix code with synchronisation delay $d$. Then
$Y=\alpha(X)\subseteq(B_{1}^{*}B_{2})^{+}$ is a prefix code with
synchronisation delay $d+1$.

######  Proof 3.8.

First, since $B_{1}$ and $B_{2}$ are disjoint, $B_{1}^{*}B_{2}\subseteq B^{*}$
is a prefix code. Hence, given a word
$w\in\alpha(A^{*})\subseteq(B_{1}^{*}B_{2})^{*}$, there exists a unique
decomposition $w=w_{1}\cdots w_{n}$ such that $w_{i}\in B_{1}^{*}B_{2}$ for
$1\leq i\leq n$. Now since images of different letters from $A$ are disjoint,
there exists at most one $a_{i}$ such that $w_{i}\in\alpha(a_{i})$. We deduce
that there is exactly one word $w^{\prime}\in A^{*}$ such that
$\alpha(w^{\prime})=w$. This word is denoted $\alpha^{-1}(w)$.

Now, we prove that $Y$ is a prefix code. Let
$v,w\in\alpha(A^{*})\subseteq(B_{1}^{*}B_{2})^{*}$ and assume that $v$ is a
prefix of $w$. Write $w=w_{1}\cdots w_{n}$ with $w_{i}\in B_{1}^{*}B_{2}$.
Since $v$ ends with a letter from $B_{2}$ we deduce that $v=w_{1}\cdots w_{i}$
for some $1\leq i\leq n$. Let $w^{\prime}=\alpha^{-1}(w)=a_{1}\cdots a_{n}$.
We have $v^{\prime}=\alpha^{-1}(v)=a_{1}\cdots a_{i}$. Now, if
$v,w\in\alpha(X)$ then we get $v^{\prime},w^{\prime}\in X$. Since $X$ is a
prefix code we get $i=n$. Hence $v=w$, proving that $Y$ is also a prefix code.

Finally, we prove that $Y$ has synchronization delay $d+1$. Let $u,v,w$ in
$B^{*}$ such that $uvw\in Y^{*}$ and $v\in Y^{d+1}$. We need to prove that
$uv\in Y^{*}$. Since $v\in Y^{d+1}$, it can be written $v=v_{0}v_{1}\cdots
v_{d}$ with $v_{i}\in Y$ for $0\leq i\leq d$. Then, let us remark that
$\alpha(A)\subseteq B_{1}^{*}B_{2}$ is a prefix code with synchronisation
delay $1$. Since $uv_{0}\cdots v_{d}w\in Y^{*}\subseteq\alpha(A)^{*}$ and
$v_{0}\in Y\subseteq\alpha(A)^{+}$, we deduce that $uv_{0}$ belongs to
$\alpha(A)^{*}=\alpha(A^{*})$, as well as $v_{1}\cdots v_{d}$ and $w$. Let
$r=\alpha^{-1}(uv_{0})$, $s=\alpha^{-1}(v_{1}\cdots v_{d})$ and
$t=\alpha^{-1}(w)$. We have $rst=\alpha^{-1}(uvw)$ and since $uvw\in
Y^{*}=\alpha(X^{*})$, we deduce that $rst\in X^{*}$. Similarly, from
$v_{1}\cdots v_{d}\in Y^{d}=\alpha(X)^{d}$, we get $s\in X^{d}$. Now, $X$ has
synchronisation delay $d$. Therefore, $rs\in X^{*}$, meaning that
$uv=uv_{0}\cdots v_{d}\in\alpha(rs)\subseteq\alpha(X^{*})=Y^{*}$.

Marked substitutions also preserve unambiguity of union, concatenation and
Kleene star.

######  Lemma 3.9.

Let $\alpha\colon A\to\mathcal{P}(B^{*})$ be a marked substitution and let
$L_{1},L_{2}\subseteq A^{*}$.

  1. 1.

If the union $L_{1}\cup L_{2}$ is unambiguous then so is
$\alpha(L_{1})\cup\alpha(L_{2})$.

  2. 2.

If the concatenation $L_{1}\cdot L_{2}$ is unambiguous then so is
$\alpha(L_{1})\cdot\alpha(L_{2})$.

  3. 3.

If the Kleene star $L_{1}^{*}$ is unambiguous then so is $\alpha(L_{1})^{*}$.

######  Proof 3.10.

As stated in the previous proof, a marked substitution is one-to-one. We
denote by $\alpha^{-1}(w)$ the unique inverse of $w$, for $w$ in
$\alpha(A^{*})$.

If $w\in\alpha(L_{1})\cup\alpha(L_{2})$ then $\alpha^{-1}(w)\in L_{1}\cup
L_{2}$. This shows that unambiguity of union is preserved by $\alpha$.

Assume now that the concatenation $L_{1}\cdot L_{2}$ is unambiguous. Let
$w\in\alpha(L_{1})\cdot\alpha(L_{2})$ and consider its unique factorisation
$w=v_{1}b_{1}\cdots v_{n}b_{n}$ as above and $\alpha^{-1}(w)=a_{1}\cdots
a_{n}$. Since $\alpha(L_{1})\subseteq(B_{1}^{*}B_{2})^{*}$, a factorisation of
$w$ according to $\alpha(L_{1})\cdot\alpha(L_{2})$ must be of the form
$w=(v_{1}b_{1}\cdots v_{i}b_{i})\cdot(v_{i+1}b_{i+1}\cdots v_{n}b_{n})$ with
$a_{1}\cdots a_{i}\in L_{1}$ and $a_{i+1}\cdots a_{n}\in L_{2}$. From
unambiguity of the product $L_{1}\cdot L_{2}$ we deduce that such a
factorisation of $w$ is unique. Hence, the product
$\alpha(L_{1})\cdot\alpha(L_{2})$ is unambiguous.

We can prove similarly that $\alpha$ preserves unambiguity of Kleene stars.

We will be interested in marked substitutions that are defined by regular
expressions. A _regular marked substitution_ (RMS) is a map $\alpha\colon
A\to\mathsf{Reg}(B^{*})$ which assigns a regular expression $\alpha(a)$ over
$B$ to each letter $a\in A$ such that $\tilde{\alpha}\colon
A\to\mathcal{P}(B^{*})$ defined by $\tilde{\alpha}(a)=\mathcal{L}(\alpha(a))$
is a marked substitution.

Let $\alpha\colon A\to\mathsf{Reg}(B^{*})$ be an RMS and let $E$ be a regular
expression over $A$. We define $\alpha(E)=E[\alpha(a)/a,\forall a\in A]$ to be
the regular expression over $B$ obtained from $E$ by substituting each
occurrence of a letter $a\in A$ with the expression $\alpha(a)$. Notice that
$\alpha$ is compositional: $\alpha(E_{1}\cup
E_{2})=\alpha(E_{1})\cup\alpha(E_{2})$, $\alpha(E_{1}\cdot
E_{2})=\alpha(E_{1})\cdot\alpha(E_{2})$ and
$\alpha(E_{1}^{*})=\alpha(E_{1})^{*}$. In particular, we have
$\tilde{\alpha}(\mathcal{L}(E))=\mathcal{L}(\alpha(E))$.

Further, we say that a RMS $\alpha$ is _unambiguous_ (URMS) if $\alpha(a)$ is
unambiguous for each $a\in A$. Similarly, an RMS $\alpha$ is SD-regular
(SDRMS) if $\alpha(a)$ is an SD-regular expression for each $a\in A$. We
obtain:

######  Corollary 3.11.

Let $\alpha\colon A\to\mathsf{Reg}(B^{*})$ be an RMS and $E$ be a regular
expression over $A$.

  1. 1.

If $\alpha$ and $E$ are SD-regular, then $\alpha(E)$ is SD-regular.

  2. 2.

If $\alpha$ and $E$ are unambiguous, then $\alpha(E)$ is unambiguous.

######  Proof 3.12.

1\. Let $F^{*}$ be a subexpression of $\alpha(E)$. If $F^{*}$ is a
subexpression of some $\alpha(a)$ then, $\alpha(a)$ being SD-regular we obtain
than $\mathcal{L}(F)$ is an SD prefix code. Otherwise, $F=\alpha(G)$ where
$G^{*}$ is a subexpression of $E$. Since $E$ is SD-regular, $\mathcal{L}(G)$
is a SD prefix code. By lemma 3.7 we deduce that
$\mathcal{L}(F)=\tilde{\alpha}(\mathcal{L}(G))$ is a SD prefix code.

2\. First, we know that each $\alpha(a)$ is unambiguous. Next, a subexpression
of $\alpha(E)$ which is not a subexpression of some $\alpha(a)$ must be of the
form $\alpha(F)$ where $F$ is a subexpression of $E$. We conclude easily using
unambiguity of $E$ and Lemma 3.9.

###  3.2 Proof of Theorem 3.6

######  Proof 3.13.

We first consider the set of neutral letters, i.e., letters whose image is the
neutral element $1$ of $M$. To ease the proof, we first explain how to handle
them, and in the rest of the proof, focus on the case where we do not have
neutral letters.

Let $\varphi\colon\Sigma^{*}\to M$ be a morphism and
$\Sigma_{0}=\\{a\in\Sigma\mid\varphi(a)=1\\}$ be the set of neutral letters.
Further, let $\Sigma_{1}=\Sigma\setminus\Sigma_{0}$ and let
$\varphi_{1}\colon\Sigma_{1}^{*}\to M$ be the restriction of $\varphi$ to
$\Sigma_{1}^{*}$. Let $\alpha\colon\Sigma_{1}\to\mathsf{Reg}(\Sigma^{*})$ be
the regular marked substitution defined by $\alpha(a)=\Sigma_{0}^{*}a$.
Clearly, $\alpha$ is unambiguous and since $\Sigma_{0}$ is a 1-SD prefix code
we get that $\alpha$ is SD-regular. By Corollary 3.11 we deduce that $\alpha$
preserves unambiguity and also SD-expressions. It also preserves stabilising
expressions, i.e., if $E\in\mathsf{Reg}(\Sigma_{1}^{*})$ is
$\varphi_{1}$-stabilising then $\alpha(E)\in\mathsf{Reg}(\Sigma^{*})$ is
$\varphi$-stabilising. Indeed, $\varphi(\Sigma_{0})$ is 1-stabilising.
Further, if $G^{*}$ is a subexpression of $\alpha(E)$ different from
$\Sigma_{0}^{*}$ then there is a subexpression $F^{*}$ of $E$ such that
$G=\alpha(F)$. Hence, $\mathcal{L}(G)=\tilde{\alpha}(\mathcal{L}(F))$ and
$X=\varphi(\mathcal{L}(G))=\varphi_{1}(\mathcal{L}(F))$ is stabilising.

Now, suppose we have unambiguous, stabilising, SD-expressions $E_{s}$ for
$\varphi_{1}$ and each $s\in M$: $\mathcal{L}(E_{s})=\varphi_{1}^{-1}(s)$. We
deduce that $E^{\prime}_{s}=\alpha(E_{s})\cdot\Sigma_{0}^{*}$ is an
unambiguous, stabilising, SD-expression. Moreover, we have
$\mathcal{L}(E^{\prime}_{s})=\varphi^{-1}(s)$.

In the rest of the proof, we assume that the morphism $\varphi$ has no neutral
letters. The proof is by induction on the size of $M$, using a result from
Perrin and Pin [20, Chapter XI, Proposition 4.14] stating that if $\varphi$ is
a surjective morphism from $\Sigma^{*}$ to a finite aperiodic monoid $M$, then
one of the following cases hold:

  1. 1.

$M$ is a cyclic monoid, meaning that $M$ is generated by a single element.

  2. 2.

$M$ is isomorphic to $\widetilde{U}_{n}$ for some $n\geq 1$

  3. 3.

There is a partition $\Sigma=A\uplus B$ such that $\varphi(A^{*})$ and
$\varphi((A^{*}B)^{*})$ are proper submonoids of $M$.

We now treat the three cases above.

  1. 1.

$M$ is a cyclic monoid. Then $M$ is of the form $\\{1,s,s^{2},\ldots,s^{n}\\}$
with $s^{i}s^{j}=s^{i+j}$ if $i+j\leq n$ and $s^{n}$ otherwise. Notice that
since we have no neutral letters, $\varphi^{-1}(1)=\\{\varepsilon\\}$. For
$1\leq i\leq n$, we denote by $\Sigma_{i}$ the set of letters whose image is
$s^{i}$. Now, we define inductively stabilising, unambiguous, SD-regular
expressions $E_{j}$ such that $\mathcal{L}(E_{j})=\varphi^{-1}(s^{j})$ for
$1\leq j\leq n$. Let $E_{1}=\Sigma_{1}$. Then, for $1<j<n$ we let

$E_{j}=\Sigma_{j}\cup\bigcup_{1\leq i<j}E_{i}\Sigma_{j-i}\,.$

Notice that expressions $E_{j}$ for $1\leq j<n$ are unambiguous and do not use
the Kleene star, hence are stabilising and SD. Finally, let

$E_{n}=\Big{(}\Sigma_{n}\cup\bigcup_{1\leq i,j<n\mid n\leq
i+j}E_{i}\Sigma_{j}\Big{)}\Sigma^{*}\,.$

Notice that the separation between the first part of $E_{n}$ and $\Sigma^{*}$
is done at the letter at which the image of the prefix reaches $s^{n}$. Then
as above, $E_{n}$ is unambiguous, and $\Sigma$ is an $n$-stabilising, 1-SD
prefix code. Moreover, $\mathcal{L}(E_{j})=\varphi^{-1}(s^{j})$ for $1\leq
j\leq n$, which concludes the proof in the case of cyclic monoids.

  2. 2.

$M$ is isomorphic to $\widetilde{U}_{n}$ for some $n$. Then $M$ is of the form
$\\{1,s_{1},\ldots,s_{n}\\}$ where $s_{i}s_{j}=s_{i}$ for all $1\leq i,j\leq
n$. As above, since we have no neutral letters, we deduce that
$\varphi^{-1}(1)=\\{\varepsilon\\}$. We similarly define
$\Sigma_{i}=\varphi^{-1}(s_{i})\cap\Sigma$. Clearly,
$\varphi^{-1}(s_{i})=\mathcal{L}(\Sigma_{i}\Sigma^{*})$, and
$\Sigma_{i}\Sigma^{*}$ is an unambiguous, 1-stabilising, 1-SD regular
expression.

  3. 3.

There is a partition $\Sigma=A\uplus B$ such that $M_{A}=\varphi(A^{*})$ and
$M_{B}=\varphi((A^{*}B)^{*})$ are proper submonoids of $M$. We set
$C=\varphi(A^{*}B)\subseteq M_{B}$ and view $C$ as a new alphabet. Note that
$C$ generates $M_{B}$. Finally, let $f\colon A^{*}\to M_{A}$ be the
restriction of $\varphi$ to $A$ and $g\colon C^{*}\to M_{B}$ be the evaluation
morphism defined by $g(c)=c$ for $c\in C$.

Then $f$ and $g$ are surjective morphisms to monoids $M_{A}$ and $M_{B}$ whose
size are smaller than $M$. We can thus use the induction hypothesis and get
unambiguous, stabilising, SD-expressions for elements of $M_{A}$ and $M_{B}$
with respect to $f$ and $g$ respectively. Given an element $s$ in $M_{A}$, we
get an unambiguous, $f$-stabilising, SD-expression $E_{s}$ over $A$ for
$f^{-1}(s)$. Similarly for an element $t$ in $M_{B}$, we get an unambiguous,
$g$-stabilising, SD-expression $F_{t}$ over the alphabet $C$ for $g^{-1}(t)$.
Notice that we have in particular expressions $E_{1}$ for $f^{-1}(1)$ and
$F_{1}$ for $g^{-1}(1)$.

To go back from expressions over $A,C$ to expressions over $\Sigma^{*}$, we
first define expressions $G_{c}$ for $\varphi^{-1}(c)\cap A^{*}B$, for each
$c\in C$:

$G_{c}=\bigcup\limits_{s\in M_{A},b\in B\mid s\varphi(b)=c}E_{s}\cdot b\,.$

Notice that $\alpha\colon C\to\mathsf{Reg}(\Sigma^{*})$ defined by
$\alpha(c)=G_{c}$ is a regular marked substitution with respect to the
partition $\Sigma=A\uplus B$. Indeed, $\alpha(c)\subseteq A^{*}B$ and
$\varphi(\alpha(c))=c$ which implies that the images are pairwise disjoint.
Moreover, each $G_{c}$ is unambiguous, $\varphi$-stabilising and SD-regular.

Let $t\in M_{B}$. By Corollary 3.11, $\alpha(F_{t})$ is unambiguous and SD-
regular. It is also $\varphi$-stabilising. Indeed, let $G^{*}$ be a
subexpression of $\alpha(F_{t})$. If $G^{*}$ is a subexpression of some
$\alpha(c)$ we get the result since $G_{c}$ is $\varphi$-stabilising.
Otherwise, there is a subexpression $F^{*}$ of $F_{t}$ such that
$G=\alpha(F)$. Hence, $\mathcal{L}(G)=\tilde{\alpha}(\mathcal{L}(F))$ and
$X=\varphi(\mathcal{L}(G))=g(\mathcal{L}(F))$ is stabilising.

For each $t\in M_{B}$, we have
$\mathcal{L}(\alpha(F_{t}))=\varphi^{-1}(t)\cap(A^{*}B)^{*}$. Finally, we need
to combine these elements to get an expression for any word over $\Sigma$.
Noticing that $\Sigma^{*}=(A^{*}B)^{*}A^{*}$, we define for $s\in M$

$E^{\prime}_{s}=\bigcup_{t\in M_{B},r\in M_{A},tr=s}\alpha(F_{t})\cdot
E_{r}\,.$

We can easily show that $E^{\prime}_{s}$ is unambiguous and satisfies
$\mathcal{L}(E_{s})=\varphi^{-1}(s)$. It is also clearly a
$\varphi$-stabilising SD-expressions. Hence, we get the result.

##  4 Combinator expressions

In this section, we present our combinators to compute first order definable
functions from finite words to finite words. The simpler combinators of
unambiguous concatenation and sum are similar to those in [3, 11], but we
differ in the equivalent of the Kleene-Star to match the aperiodicity that we
tackle.

###  4.1 Simple Functions

For each $v\in\Gamma^{*}$ we have a constant function $f_{v}$ defined by
$f_{v}(u)=v$ for all $u\in\Sigma^{*}$. Abusing notations, we simply denote the
constant function $f_{v}$ by $v$. We denote by
$\bot\colon\Sigma^{*}\to\Gamma^{*}$ the function with empty domain. These
atomic functions are the most simple ones.

###  4.2 Unambiguous sums

We will use two equivalent ways of defining a function by cases. First, the
if-then-else construct is given by $h={L}\,?\,{f}:{g}$ where
$f,g\colon\Sigma^{*}\to\Gamma^{*}$ are functions and $L\subseteq\Sigma^{*}$ is
a language. We have $\mathsf{dom}(h)=(\mathsf{dom}(f)\cap
L)\cup(\mathsf{dom}(g)\setminus L)$. Then, for $w\in\mathsf{dom}(h)$ we have

$h(w)=\begin{cases}f(w)&\text{if }w\in L\\\ g(w)&\text{otherwise.}\end{cases}$

We will often use this case definition with $L=\mathsf{dom}(f)$. To simplify
notations we define $f+g={\mathsf{dom}(f)}\,?\,{f}:{g}$. Note that
$\mathsf{dom}(f+g)=\mathsf{dom}(f)\cup\mathsf{dom}(g)$ but the sum is not
commutative and $g+f={\mathsf{dom}(g)}\,?\,{g}:{f}$. For
$w\in\mathsf{dom}(f)\cap\mathsf{dom}(g)$ we have $(f+g)(w)=f(w)$ and
$(g+f)(w)=g(w)$. When the domains of $f$ and $g$ are disjoint then $f+g$ and
$g+f$ are equivalent functions with domain
$\mathsf{dom}(f)\uplus\mathsf{dom}(g)$. In all cases the sum is associative
and the sum notation is particularly useful when applied to a sequence
$f_{1},\ldots,f_{n}$ of functions:

$\sum_{1\leq i\leq
n}f_{i}=f_{1}+\cdots+f_{n}={\mathsf{dom}(f_{1})}\,?\,{f_{1}}:{{\mathsf{dom}(f_{2})}\,?\,{f_{2}}:{\cdots{\mathsf{dom}(f_{n-1})}\,?\,{f_{n-1}}:{f_{n}}}}$

If the domains of the functions are pairwise disjoint then this sum is
associative and commutative.

Further, we let ${L}\triangleright{f}={L}\,?\,{f}:{\bot}$ the function $f$
restricted to $L\cap\mathsf{dom}(f)$. When $L=\\{w\\}$ is a singleton, we
simply write ${w}\triangleright{f}$.

###  4.3 The Hadamard product

The Hadamard product of two functions $f,g\colon\Sigma^{*}\to\Gamma^{*}$ first
applies $f$ and then applies $g$. It is denoted by $f\odot g$. Its domain is
$\mathsf{dom}(f)\cap\mathsf{dom}(g)$ and $(f\odot g)(u)=f(u)g(u)$ for each
input word $u$ in its domain.

###  4.4 The unambiguous Cauchy product

Consider two functions $f,g\colon\Sigma^{*}\to\Gamma^{*}$. The unambiguous
Cauchy product of $f$ and $g$ is the function $f\cdot g$ whose domain is the
set of words $w\in\Sigma^{*}$ which admit a unique factorization $w=uv$ with
$u\in\mathsf{dom}(f)$ and $v\in\mathsf{dom}(g)$, and in this case, the
computed output is $f(u)g(v)$.

Contrary to the Hadamard product which reads its full input word $w$ twice,
first applying $f$ and then applying $g$, the Cauchy product _splits
unamgibuously_ its input word $w$ as $uv$, applies $f$ on $u$ and then $g$ on
$v$.

Sometimes we may want to reverse the output and produce $g(v)f(u)$. This
_reversed_ Cauchy product can be defined using the Hadamard product as

$f\cdot_{r}g=(({\mathsf{dom}(f)}\triangleright{\varepsilon})\cdot
g)\odot(f\cdot({\mathsf{dom}(g)}\triangleright{\varepsilon}))$

###  4.5 The $k$-chained Kleene-star and its reverse

Let $L\subseteq\Sigma^{*}$ be a code, let $k\geq 1$ be a natural number and
let $f\colon\Sigma^{*}\to\Gamma^{*}$ be a partial function. We define the
$k$-chained Kleene-star $[L,f]^{k\star}\colon\Sigma^{*}\to\Gamma^{*}$ and its
reverse $[L,f]_{r}^{k\star}\colon\Sigma^{*}\to\Gamma^{*}$ as follows.

The domain of both these functions is contained in $L^{*}$, the set of words
having a (unique) factorization over the code $L$. Let $w\in L^{*}$ and
consider its unique factorization $w=u_{1}u_{2}\cdots u_{n}$ with $n\geq 0$
and $u_{i}\in L$ for all $1\leq i\leq n$. Then,
$w\in\mathsf{dom}([L,f]^{k\star})=\mathsf{dom}([L,f]_{r}^{k\star})$ if
$u_{i+1}\cdots u_{i+k}\in\mathsf{dom}(f)$ for all $0\leq i\leq n-k$ and in
this case we set

$\displaystyle[L,f]^{k\star}(w)$ $\displaystyle=f(u_{1}\cdots u_{k})\cdot
f(u_{2}\cdots u_{k+1})\cdots f(u_{n-k+1}\cdots u_{n})$
$\displaystyle[L,f]_{r}^{k\star}(w)$ $\displaystyle=f(u_{n-k+1}\cdots
u_{n})\cdots f(u_{2}\cdots u_{k+1})\cdot f(u_{1}\cdots u_{k})\,.$

Notice that when $n<k$, the right-hand side is an empty product and we get
$[L,f]^{k\star}(w)=\varepsilon$ and $[L,f]_{r}^{k\star}(w)=\varepsilon$. When
$k=1$ and $L=\mathsf{dom}(f)$ is a code then we simply write
$f^{\star}=[\mathsf{dom}(f),f]^{1\star}$ and
$f_{r}^{\star}=[\mathsf{dom}(f),f]_{r}^{1\star}$. We have
$\mathsf{dom}(f^{\star})=\mathsf{dom}(f_{r}^{\star})=L^{*}$.

The k-chained Kleene star was also defined in [3, 11]; however as we will see
below, we use it in a restricted way for aperiodic functions.

###  4.6 SD-regular transducer expressions (SDRTE)

SD-regular transducer expressions (SDRTEs) are obtained from classical regular
transducer expressions (RTEs) [3, 11] by restricting the $k$-chained Kleene-
star $[L,f]^{k\star}$ and its reverse $[L,f]_{r}^{k\star}$ to aperiodic
languages $L$ that are prefix codes of bounded synchronisation delay. The if-
then-else choice ${L}\,?\,{f}:{g}$ is also restricted to aperiodic languages
$L$. Hence, the syntax of SDRTEs is given by the grammar:

$C::=\bot\mid v\mid{L}\,?\,{C}:{C}\mid C\odot C\mid C\cdot
C\mid[L,C]^{k\star}\mid[L,C]_{r}^{k\star}$

where $v\in\Gamma^{*}$, and $L\subseteq\Sigma^{*}$ ranges over aperiodic
languages (or equivalently SD-regular expressions), which are also prefix
codes with bounded synchronisation delay for $[L,C]^{k\star}$ and
$[L,C]_{r}^{k\star}$.

The semantics of SDRTEs is defined inductively. $[\\![\bot]\\!]$ is the
function which is nowhere defined, $[\\![v]\\!]$ is the constant function such
as $[\\![v]\\!](u)=v$ for all $u\in\Sigma^{*}$, and the semantics of the other
combinators has been defined in the above sections.

As discussed in Section 4.2, we will use binary sums
$C+C^{\prime}={\mathsf{dom}(C)}\,?\,{C}:{C^{\prime}}$ and generalised sums
$\sum_{i}C_{i}$. Also, we use the abbreviation
${L}\triangleright{C}={L}\,?\,{C}:{\bot}$ and the reversed Cauchy product
$C\cdot_{r}C^{\prime}=(({\mathsf{dom}(C)}\triangleright{\varepsilon})\cdot
C^{\prime})\odot(C\cdot({\mathsf{dom}(C^{\prime})}\triangleright{\varepsilon}))$.

######  Lemma 4.1.

If $C$ is an SDRTE, then $\mathsf{dom}(C)$ is an aperiodic language.

######  Proof 4.2.

We prove the statement by induction on the syntax of SDRTEs. We recall that
aperiodic languages are closed under concatenation, union, intersection and
complement.

  * •

$\mathsf{dom}(\bot)=\emptyset$ and $\mathsf{dom}(v)=\Sigma^{*}$ are aperiodic
languages.

  * •

$C={L}\,?\,{C_{1}}:{C_{2}}$. By induction, $\mathsf{dom}(C_{1})$ and
$\mathsf{dom}(C_{2})$ are aperiodic. We have
$\mathsf{dom}(C)=(L\cap\mathsf{dom}(C_{1}))\cup(\mathsf{dom}(C_{2})\setminus
L)$, which is aperiodic thanks to the closure properties of aperiodic
languages.

  * •

$C=C_{1}\odot C_{2}$. By induction, $\mathsf{dom}(C_{1})$ and
$\mathsf{dom}(C_{2})$ are aperiodic. We deduce that
$\mathsf{dom}(C)=\mathsf{dom}(C_{1})\cap\mathsf{dom}(C_{2})$ is aperiodic.

  * •

$C=C_{1}\cdot C_{2}$. By induction, $L_{1}=\mathsf{dom}(C_{1})$ and
$L_{2}=\mathsf{dom}(C_{2})$ are aperiodic. We have
$\mathsf{dom}(C)\subseteq\mathsf{dom}(C_{1})\cdot\mathsf{dom}(C_{2})$.
However, $C$ is undefined on words having more than one decomposition. A word
which admits at least two decompositions can be written $uvw$ with
$v\neq\varepsilon$, $u,uv\in L_{1}$ and $vw,w\in L_{2}$. Let
$\varphi\colon\Sigma^{*}\to M$ be a morphism to a finite aperiodic monoid
recognising both $L_{1}$ and $L_{2}$. We have $L_{1}=\varphi^{-1}(P_{1})$ and
$L_{2}=\varphi^{-1}(P_{2})$ for some $P_{1},P_{2}\subseteq M$. The set $L_{3}$
of words having at least two decompositions is precisely

$L_{3}=\bigcup_{\begin{subarray}{c}r,s,t\mid r,rs\in P_{1}\wedge st,t\in
P_{2}\end{subarray}}\varphi^{-1}(r)(\varphi^{-1}(s)\setminus\\{\varepsilon\\})\varphi^{-1}(t)$

which is aperiodic. We deduce that $\mathsf{dom}(C)=(L_{1}\cdot
L_{2})\setminus L_{3}$ is aperiodic.

  * •

$C=[L,C^{\prime}]^{k\star}$. By induction, $\mathsf{dom}(C^{\prime})$ is
aperiodic and by definition $L$ is an aperiodic SD prefix code. Hence $L^{*}$
is aperiodic. Notice that $\mathsf{dom}(C)\subseteq L^{*}$ but $C$ is
undefined on words $w=u_{1}\cdots u_{n}$ with $u_{i}\in L$ if there is a
factor $u_{i+1}\cdots u_{i+k}$ which is not in $\mathsf{dom}(C^{\prime})$. We
deduce that
$\mathsf{dom}(C)=L^{*}\setminus(L^{*}(L^{k}\setminus\mathsf{dom}(C^{\prime}))L^{*})$
which is aperiodic thanks to the closure properties given above.

  * •

Notice that
$\mathsf{dom}([L,C^{\prime}]_{r}^{k\star})=\mathsf{dom}([L,C^{\prime}]^{k\star})$,
which is aperiodic as proved above.

######  Proposition 4.3.

Given an SDRTE $C$ and a letter $a\in\Sigma$,

  1. 1.

we can construct an SDRTE ${a}^{-1}{C}$ such that
$\mathsf{dom}({a}^{-1}{C})=a^{-1}\mathsf{dom}(C)$ and
$[\\![{a}^{-1}{C}]\\!](w)=[\\![C]\\!](aw)$ for all $w\in
a^{-1}\mathsf{dom}(C)$,

  2. 2.

we can construct an SDRTE ${C}{a}^{-1}$ such that
$\mathsf{dom}({C}{a}^{-1})=\mathsf{dom}(C)a^{-1}$ and
$[\\![{C}{a}^{-1}]\\!](w)=[\\![C]\\!](wa)$ for all
$w\in\mathsf{dom}(C)a^{-1}$.

######  Proof 4.4.

We recall that aperiodic languages are closed under left and right quotients.
The proof is by structural induction on the given SDRTE $C$ over alphabet
$\Sigma$. We only construct below the SDRTEs for the left quotient. Formulas
for the right quotient can be obtained similarly. A point to note is that,
unlike the left quotient, the right quotient of a language might break its
prefix code property, which could be a problem if applied to a parsing
language $L$ used for $k$-star or its reverse. However, the quotient by a
letter only modifies the first or last copy of $L$, which can be decoupled so
that the remaining iterations are still performed with the same parsing
language $L$.

Basic cases.

We define ${a}^{-1}{\bot}=\bot$ and ${a}^{-1}{v}=v$ for $v\in\Gamma^{*}$.

If-then-else.

Let $C={L}\,?\,{C_{1}}:{C_{2}}$. We define
${a}^{-1}{C}={a^{-1}L}\,?\,{{a}^{-1}{C_{1}}}:{{a}^{-1}{C_{2}}}$.

Recall that $\mathsf{dom}(C)=(\mathsf{dom}(C_{1})\cap
L)\cup(\mathsf{dom}(C_{2})\setminus L)$. We deduce that

$\displaystyle a^{-1}\mathsf{dom}(C)$
$\displaystyle=((a^{-1}\mathsf{dom}(C_{1}))\cap(a^{-1}L))\cup((a^{-1}\mathsf{dom}(C_{2}))\setminus(a^{-1}L))$
$\displaystyle=\mathsf{dom}({a^{-1}L}\,?\,{{a}^{-1}{C_{1}}}:{{a}^{-1}{C_{2}}})$

Moreover, for $w\in a^{-1}\mathsf{dom}(C)$, we have

$\displaystyle[\\![C]\\!](aw)$
$\displaystyle=\begin{cases}[\\![C_{1}]\\!](aw)&\text{if }aw\in L\\\
[\\![C_{2}]\\!](aw)&\text{otherwise.}\end{cases}=\begin{cases}[\\![{a}^{-1}{C_{1}}]\\!](w)&\text{if
}w\in a^{-1}L\\\ [\\![{a}^{-1}{C_{2}}]\\!](w)&\text{otherwise.}\end{cases}$
$\displaystyle=[\\![{a^{-1}L}\,?\,{{a}^{-1}{C_{1}}}:{{a}^{-1}{C_{2}}}]\\!](w)$

Hadamard product.

Let $C=C_{1}\odot C_{2}$. We define
${a}^{-1}{C}={a}^{-1}{C_{1}}\odot{a}^{-1}{C_{2}}$.

Recall that $\mathsf{dom}(C)=\mathsf{dom}(C_{1})\cap\mathsf{dom}(C_{2})$. We
deduce that

$\displaystyle a^{-1}\mathsf{dom}(C)$
$\displaystyle=(a^{-1}\mathsf{dom}(C_{1}))\cap(a^{-1}\mathsf{dom}(C_{2}))=\mathsf{dom}({a}^{-1}{C_{1}}\odot{a}^{-1}{C_{2}})$

Moreover, for $w\in a^{-1}\mathsf{dom}(C)$, we have

$\displaystyle[\\![C]\\!](aw)$
$\displaystyle=[\\![C_{1}]\\!](aw)[\\![C_{2}]\\!](aw)=[\\![{a}^{-1}{C_{1}}]\\!](w)[\\![{a}^{-1}{C_{2}}]\\!](w)=[\\![{a}^{-1}{C_{1}}\odot{a}^{-1}{C_{2}}]\\!](w)$

Cauchy product.

Let $C=C_{1}\cdot C_{2}$. The SDRTE ${a}^{-1}{C}$ is the unambiguous sum of
two expressions depending on whether the letter $a$ is removed from $C_{1}$ or
from $C_{2}$. Hence, we let $C^{\prime}=({a}^{-1}{C_{1}})\cdot{C_{2}}$ and
$C^{\prime\prime}=({\varepsilon}\triangleright{[\\![C_{1}]\\!](\varepsilon)})\cdot({a}^{-1}{C_{2}})$.
Notice that $\mathsf{dom}(C^{\prime\prime})=\emptyset$ when
$\varepsilon\notin\mathsf{dom}(C_{1})$ (i.e.,
$[\\![C_{1}]\\!](\varepsilon)=\bot$). Now, we define
${a}^{-1}{C}={(a^{-1}\mathsf{dom}(C))}\triangleright{(C^{\prime}+C^{\prime\prime})}$.

Let $w\in a^{-1}\mathsf{dom}(C)$. Then $aw$ admits a unique factorization
$aw=uv$ with $u\in\mathsf{dom}(C_{1})$ and $v\in\mathsf{dom}(C_{2})$. There
are two exclusive cases.

If $u\neq\varepsilon$ then $u=au^{\prime}$ with $u^{\prime}\in
a^{-1}\mathsf{dom}(C_{1})$. The word $w$ admits a unique factorization
according to $\mathsf{dom}({a}^{-1}{C_{1}})\mathsf{dom}(C_{2})$ which is
$w=u^{\prime}v$. Hence, $w\in\mathsf{dom}(C^{\prime})$ and

$[\\![C]\\!](aw)=[\\![C_{1}]\\!](u)[\\![C_{2}]\\!](v)=[\\![{a}^{-1}{C_{1}}]\\!](u^{\prime})[\\![C_{2}]\\!](v)=[\\![C^{\prime}]\\!](w)\,.$

If $u=\varepsilon$ then $v=av^{\prime}$ and $v^{\prime}\in
a^{-1}\mathsf{dom}(C_{2})$. The word $w=v^{\prime}$ admits a unique
factorization according to
$\\{\varepsilon\\}\cdot\mathsf{dom}({a}^{-1}{C_{2}})$ which is
$w=\varepsilon\cdot w$. Hence, $w\in\mathsf{dom}(C^{\prime\prime})$ and

$[\\![C]\\!](aw)=[\\![C_{1}]\\!](\varepsilon)[\\![C_{2}]\\!](v)=[\\![C_{1}]\\!](\varepsilon)[\\![{a}^{-1}{C_{2}}]\\!](w)=[\\![C^{\prime\prime}]\\!](w)\,.$

We deduce that
$a^{-1}\mathsf{dom}(C)\subseteq\mathsf{dom}(C^{\prime})\cup\mathsf{dom}(C^{\prime\prime})=\mathsf{dom}(C^{\prime}+C^{\prime\prime})$
and $\mathsf{dom}(a^{-1}C)=a^{-1}\mathsf{dom}(C)$ as desired.

Finally, assume that
$w\in\mathsf{dom}(C^{\prime})\cap\mathsf{dom}(C^{\prime\prime})$. Then, $w$
admits two factorizations $w=u^{\prime}v=\varepsilon v^{\prime}$ with
$u^{\prime}\in\mathsf{dom}({a}^{-1}{C_{1}})$, $v\in\mathsf{dom}(C_{2})$,
$\varepsilon\in\mathsf{dom}(C_{1})$ and
$v^{\prime}\in\mathsf{dom}({a}^{-1}{C_{2}})$. We deduce that $aw$ admits two
distinct factorizations $aw=(au^{\prime})v=\varepsilon(av^{\prime})$ with
$au^{\prime},\varepsilon\in\mathsf{dom}(C_{1})$ and
$v,av^{\prime}\in\mathsf{dom}(C_{2})$. This is a contradiction with
$aw\in\mathsf{dom}(C)$.

We deduce that in both cases above, we have

$[\\![C]\\!](aw)=[\\![{(a^{-1}\mathsf{dom}(C))}\triangleright{(C^{\prime}+C^{\prime\prime})}]\\!](w)\,.$

$k$-star.

Let $L\subseteq\Sigma^{*}$ be an aperiodic prefix code with bounded
synchronisation delay and let $C$ an SDRTE. Notice that, since $L$ is a code,
$\varepsilon\notin L$. Also, $a^{-1}\mathsf{dom}([L,C]^{k\star})\subseteq
a^{-1}L^{*}=(a^{-1}L)L^{*}$. Let $w\in a^{-1}L^{*}$. It admits a unique
factorization $w=u^{\prime}_{1}u_{2}\cdots u_{n}$ with
$u_{1}=au^{\prime}_{1}\in L$ and $u_{2},\ldots,u_{n}\in L$. The unique
factorization of $aw$ according to the code $L$ is $aw=u_{1}u_{2}\cdots
u_{n}$.

Now, by defintion of $k$-star, when $n<k$ we have
$[\\![[L,C]^{k\star}]\\!](aw)=\varepsilon$. Hence, we let
$C^{\prime}={\big{(}(a^{-1}L)\cdot
L^{<k-1}\big{)}}\triangleright{\varepsilon}$ so that in the case $n<k$ we get

$[\\![[L,C]^{k\star}]\\!](aw)=\varepsilon=[\\![C^{\prime}]\\!](w)\,.$

Next we assume that $n\geq k$. We define two SDRTEs:

$\displaystyle C^{\prime\prime}$ $\displaystyle=\big{(}{\big{(}(a^{-1}L)\cdot
L^{k-1}\big{)}}\triangleright{{a}^{-1}{C}}\big{)}\cdot({L^{*}}\triangleright{\varepsilon})$
$\displaystyle C^{\prime\prime\prime}$
$\displaystyle=({a^{-1}L}\triangleright{\varepsilon})\cdot[L,C]^{k\star}$

Notice that $L^{*}$ is aperiodic since $L$ is an aperiodic prefix code with
bounded synchronisation delay. Hence, $C^{\prime\prime}$ is indeed an SDRTE.
We get

$\displaystyle[\\![C^{\prime\prime}]\\!](w)$
$\displaystyle=[\\![{a}^{-1}{C}]\\!](u^{\prime}_{1}u_{2}\cdots
u_{k})=[\\![C]\\!](u_{1}u_{2}\cdots u_{k})$
$\displaystyle[\\![C^{\prime\prime\prime}]\\!](w)$
$\displaystyle=[\\![C]\\!](u_{2}\cdots u_{k+1})[\\![C]\\!](u_{3}\cdots
u_{k+2})\cdots[\\![C]\\!](u_{n-k+1}\cdots u_{n})$
$\displaystyle[\\![C^{\prime\prime}\odot C^{\prime\prime\prime}]\\!](w)$
$\displaystyle=[\\![[L,C]^{k\star}]\\!](aw)\,.$

Therefore, we define the SDRTE

${a}^{-1}{([L,C]^{k\star})}={(a^{-1}L^{*})}\triangleright{\big{(}C^{\prime}+(C^{\prime\prime}\odot
C^{\prime\prime\prime})\big{)}}\,.$

Notice that $\mathsf{dom}(C^{\prime})=a^{-1}L^{<k}$ and
$\mathsf{dom}(C^{\prime\prime}\odot C^{\prime\prime\prime})\subseteq
a^{-1}L^{\geq k}$ are disjoint.

Reverse $k$-star.

This case is similar. Let $L\subseteq\Sigma^{*}$ be an aperiodic prefix code
with bounded synchronisation delay and let $C$ an SDRTE. We define

${a}^{-1}{([L,C]_{r}^{k\star})}={(a^{-1}L^{*})}\triangleright{\big{(}C^{\prime}+(C^{\prime\prime\prime\prime}\odot
C^{\prime\prime})\big{)}}$

where $C^{\prime},C^{\prime\prime}$ are as above and
$C^{\prime\prime\prime\prime}=({a^{-1}L}\triangleright{\varepsilon})\cdot[L,C]_{r}^{k\star}$.

######  Lemma 4.5.

Given an SDRTE $C$ over an alphabet $\Sigma$ and a sub-alphabet
$\Sigma^{\prime}\subseteq\Sigma$, we can construct an SDRTE $C^{\prime}$ _over
alphabet $\Sigma^{\prime}$_ such that
$\mathsf{dom}(C^{\prime})\subseteq\Sigma^{\prime*}$ and for any word $w$ in
$\Sigma^{\prime*}$, $[\\![C]\\!](w)=[\\![C^{\prime}]\\!](w)$.

######  Proof 4.6.

The proof itself is rather straightforward, and simply amounts to get rid of
letters that do not appear in $\Sigma^{\prime}$. We first construct
$C^{\prime}$ by structural induction from $C$, and then prove that it is
indeed an SDRTE. Thus $C^{\prime}$ is defined as follows:

  * •

if $C=\bot$ then $C^{\prime}=\bot$,

  * •

if $C=v$ then $C^{\prime}=v$, with $\mathsf{dom}(v)=\Sigma^{\prime*}$ here
since $C^{\prime}$ is over $\Sigma^{\prime}$,

  * •

if $C={L}\,?\,{C_{1}}:{C_{2}}$ then
$C^{\prime}={(L\cap\Sigma^{\prime*})}\,?\,{C^{\prime}_{1}}:{C^{\prime}_{2}}$,

  * •

if $C=C_{1}\odot C_{2}$ then $C^{\prime}=C^{\prime}_{1}\odot C^{\prime}_{2}$,

  * •

if $C=C_{1}\cdot C_{2}$ then $C^{\prime}=C^{\prime}_{1}\cdot C^{\prime}_{2}$,

  * •

if $C=[L,C_{1}]^{k\star}$ then
$C^{\prime}=[L\cap\Sigma^{\prime*},C^{\prime}_{1}]^{k\star}$,

  * •

if $C=[L,C_{1}]_{r}^{k\star}$ then
$C^{\prime}=[L\cap\Sigma^{\prime*},C^{\prime}_{1}]_{r}^{k\star}$.

To prove that $C^{\prime}$ is SD-regular, we construct, given an SD-expression
$E$ for $L$ over $\Sigma$, an SD-expression $E^{\prime}$ over
$\Sigma^{\prime}$ for $L\cap\Sigma^{\prime*}$. Again, the proof is an easy
structural induction:

  * •

if $E=\emptyset$ then $E^{\prime}=\emptyset$,

  * •

if $E=a\in\Sigma^{\prime}$ then $E^{\prime}=a$,

  * •

if $E=a\in\Sigma\setminus\Sigma^{\prime}$ then $E^{\prime}=\emptyset$,

  * •

if $E=E_{1}+E_{2}$ then $E^{\prime}=E^{\prime}_{1}+E^{\prime}_{2}$,

  * •

if $E=E_{1}\cdot E_{2}$ then $E^{\prime}=E^{\prime}_{1}\cdot E^{\prime}_{2}$,

  * •

if $E=E_{1}^{*}$ then $E^{\prime}=E_{1}^{\prime*}$.

We conclude by stating that being a prefix code with bounded synchronisation
delay is a property preserved by subsets, hence $E^{\prime}$ is an SD-
expression.

$w$$w^{\prime}$$x_{0}$$x_{1}$$x_{2}$$x_{3}$$p_{1}$$q_{1}$$q_{2}$$q_{3}$$p_{2}$$u$$v$$\rho_{0}$$\rho_{1}$$\rho_{2}$$\rho_{3}$$\rho_{4}$$\rho_{5}$$p$$p_{1}$$p_{2}$$p_{3}$$p_{4}$$p_{5}$$q$$u$$v$$\rho_{0}$$\rho_{1}$$\rho_{2}$$\rho_{3}$$\rho_{4}$$p$$p_{1}$$p_{2}$$p_{3}$$p_{4}$$q$$u_{1}$$u_{2}$$u_{i}$$u_{i+1}$$u_{i+k}$$u_{i+k+1}$$u_{n}$$\rho_{1}$$\rho_{2}$$\rho_{3}$$\rho_{4}$$p$$q_{1}$$q_{2}$$q_{3}$$q$$u_{1}$$u_{2}$$u_{i}$$u_{i+1}$$u_{i+k}$$u_{i+k+1}$$u_{n}$$\rho_{1}$$\rho_{2}$$\rho_{3}$$\rho_{4}$$p$$q_{1}$$q_{2}$$q_{3}$$q$$u_{1}$$u_{2}$$u_{i}$$u_{i+1}$$u_{i+k}$$u_{i+k+1}$$u_{n}$$\rho_{1}$$\rho_{2}$$\rho_{3}$$p$$q_{1}$$q_{2}$$q$$u_{1}$$u_{2}$$u_{3}$$u_{4}$$u_{5}$$u_{6}$$u_{7}$$u_{8}$$u_{9}$$u_{10}$$u_{11}$$u_{12}$$\rho_{0}$$\rho_{1}$$\rho_{2}$$\rho_{3}$$\rho_{4}$$\rho_{5}$$\rho_{6}$$\rho_{7}$$\rho_{8}$$\rho_{9}$$\rho_{10}$$p$$q$$q_{1}$$q$$q$$q_{3}$$q$$q_{4}$$q$$q$$q$$q_{7}$$q$$q_{8}$$q$$q$$q_{10}$$q$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}q_{2}}={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}q_{5}}=q_{6}=q_{9}=q$$u_{1}$$u_{2}$$u_{3}$$u_{4}$$u_{5}$$u_{6}$$u_{7}$$u_{8}$$u_{9}$$u_{10}$$u_{11}$$u_{12}$$\rho_{11}$$\rho_{10}$$\rho_{9}$$\rho_{8}$$\rho_{7}$$\rho_{6}$$\rho_{5}$$\rho_{4}$$\rho_{3}$$\rho_{2}$$\rho_{1}$$p$$q_{10}$$q^{\prime}_{10}$$q_{9}$$q_{8}$$q^{\prime}_{8}$$q_{7}$$q^{\prime}_{7}$$q_{6}$$q^{\prime}_{6}$$q_{5}$$q_{4}$$q^{\prime}_{4}$$q_{3}$$q^{\prime}_{3}$$q_{2}$$q^{\prime}_{2}$$q_{1}$$q^{\prime}_{1}$$q$${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}q^{\prime}_{5}=q_{5}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}q^{\prime}_{9}=q_{9}}$$\\#$$u_{1}$$\\#$$u_{2}$$\\#$$u_{3}$$\\#$$u_{4}$$\\#$$u_{5}$$\\#$$\\#$$u_{1}$$\\#$$u_{2}$$\\#$$u_{3}$$\\#$$u_{2}$$u_{3}$$u_{4}$$u_{3}$$u_{4}$$u_{5}$input
:output copy 1:output copy 2:output copy
3:$u_{1}$$u_{2}$$u_{3}$$u_{4}$$u_{5}$input:$X_{1}$:$X_{2}$:$X_{3}$:$O$:.....................$\times$.$\times$...........$u_{1}$$u_{1}$$u_{1}$$u_{2}$$u_{2}$$u_{2}$$u_{3}$$u_{3}$$u_{3}$$u_{4}$$u_{4}$$u_{4}$$u_{5}$$u_{5}$$u_{5}$$\\#$$\\#$$\\#$$\\#$

###  4.7 Can the 2-chained Kleene star suffice for all aperiodic functions?

It is known [11] that the 2-chained Kleene star can simulate the $k$-chained
Kleene-star for regular functions. However, we believe that, contrary to the
case of regular functions, the $k$-chained Kleene-star operator cannot be
simulated by the $2$-chained Kleene-star while preserving the aperiodicity of
the expression. The key idea is that, in order to simulate a $k$-chained
Kleene-star on a SD prefix code $L$ using a $2$-chained Kleene-star, one needs
to use $L^{\lceil k/2\rceil}$ as a parser. However, for any given prefix code
$L$, the language $L^{n}$ for $n>1$, while still a prefix code, is not of
bounded synchronisation delay (for the same reason that $\\{aa\\}$ is not,
i.e., for $v=(aa)^{d}$ that we consider, $ava$ belongs to $(aa)^{*}$ but $av$
does not). Intuitively, parsing $L^{n}$ reduces to _count_ ing factors of $L$
_modulo $n$_, which is a classical example of non-aperiodicity.

As an example, consider the prefix code $L=(a+b)^{*}c$ which has
synchronisation delay $1$. Define a function $f$ with domain $L^{3}$ by
$f(u_{1}u_{2}u_{3})=u_{3}u_{1}$ when $u_{1},u_{2},u_{3}\in L$, which can be
written using combinators as
$\big{(}({L^{2}}\triangleright{\varepsilon})\cdot({L}\triangleright{id})\big{)}\odot\big{(}({L}\triangleright{id})\cdot({L^{2}}\triangleright{\varepsilon})\big{)}$.
The identity function $id$ can itself be written as
$({a}\triangleright{a}+{b}\triangleright{b}+{c}\triangleright{c})^{\star}$
(see also Figure 2, which is a simplification of the same function, but
neverthless has the same inexpressiveness with 2 chained star). Then we
believe that the function $[L,f]^{3\star}$, which associates to a word
$u_{1}\cdots u_{n}\in L^{*}$ the word $u_{3}u_{1}u_{4}u_{2}\cdots
u_{n}u_{n-2}$ is not definable using only $2$-chained Kleene-stars. While not
a proof, the intuition behind this is that, in order to construct
$u_{i+1}u_{i-1}$, we need to highlight words from $L^{3}$. In order to do this
with a $2$-chained Kleene-star, it seems necessary to apply a chained star
with parser $L^{2}$, which is a prefix code but not of bounded synchronisation
delay. A similar argument would hold for any $[L,f]^{k\star}$, $k\geq 3$ with
a function $f(u_{1}u_{2}\cdots u_{k})=u_{k}u_{1}$.

##  5 The Equivalence of SDRTE and Aperiodic 2DFT

In this section, we prove the main result of the paper, namely the equivalence
between SDRTE and aperiodic 2DFT stated in Theorem 1.1. The first direction,
given an SDRTE $C$, constructing an equivalent aperiodic 2DFT $\mathcal{A}$ is
given by Theorem 5.1, while Theorem 5.14 handles the converse.

###  5.1 Aperiodic 2DFTs for SD-regular transducer expressions

######  Theorem 5.1.

Given an SDRTE $C$, we can construct an equivalent aperiodic 2DFT
$\mathcal{A}$ with $[\\![C]\\!]=[\\![\mathcal{A}]\\!]$.

######  Proof 5.2.

We construct $\mathcal{A}$ by induction on the structure of the SDRTE $C$. In
the suitable cases, we will suppose thanks to induction that we have aperiodic
transducers $\mathcal{A}_{i}$ for expressions $C_{i}$, $i\leq 2$. We also have
a deterministic and complete aperiodic automaton $A_{L}$ for any aperiodic
language $L$.

  * •

$C=\bot$. Then $\mathcal{A}$ is a single state transducer with no final state
so that its domain is empty.

  * •

$C=v$. Then $\mathcal{A}$ is a single state transducer which produces $v$ and
accepts any input word. Clearly, $\mathcal{A}$ is aperiodic.

  * •

$C={L}\,?\,{C_{1}}:{C_{2}}$. The transducer $\mathcal{A}$ first reads its
input, simulating $A_{L}$. Upon reaching the end of the input word, it goes
back to the beginning of the word, and either executes $\mathcal{A}_{1}$ if
the word was accepted by $A_{L}$, or executes $\mathcal{A}_{2}$ otherwise.
Since every machine was aperiodic, so is $\mathcal{A}$.

  * •

$C=C_{1}\odot C_{2}$. The transducer $\mathcal{A}$ does a first pass executing
$\mathcal{A}_{1}$, then resets to the beginning of the word and simulates
$\mathcal{A}_{2}$. Since both transducers are aperiodic, so is $\mathcal{A}$.

  * •

$C=C_{1}\cdot C_{2}$. We express $\mathcal{A}$ as the composition of three
functions $f_{1},f_{2},f_{3}$, each aperiodic. Since aperiodic functions are
closed under composition, we get the result. The first function $f_{1}$
associates to each word $w\in\Sigma^{*}$ the word
$u_{1}\\#u_{2}\\#\cdots\\#u_{n}$, such that $w=u_{1}u_{2}\cdots u_{n}$ and for
any prefix $u$ of $w$, $u$ belongs to the domain of $C_{1}$ if, and only if,
$u=u_{1}\cdots u_{i}$ for some $1\leq i<n$. Notice that $u_{1}=\varepsilon$
iff $\varepsilon\in\mathsf{dom}(C_{1})$ and $u_{n}=\varepsilon$ iff
$w\in\mathsf{dom}(C_{1})$. The other $u_{i}$’s must be nonempty. The second
function $f_{2}$ takes as input a word in $(\Sigma\cup\\{\\#\\})^{*}$, reads
it from right to left, and suppresses all $\\#$ symbols except for the ones
whose corresponding suffix belongs to the domain of $C_{2}$. Then,
$f_{2}(f_{1}(w))$ contains exactly one $\\#$ symbol if and only if $w$ has a
unique factorisation $w=uv$ with $u\in\mathsf{dom}(C_{1})$ and
$v\in\mathsf{dom}(C_{2})$. In this case, $f_{2}(f_{1}(w))=u\\#v$.

Finally, the function $f_{3}$ has domain $\Sigma^{*}\\#\Sigma^{*}$ and first
executes $\mathcal{A}_{1}$ on the prefix of its input upto the $\\#$ symbol,
treating it as the right endmarker ${\dashv}$, and then executes
$\mathcal{A}_{2}$ on the second part, treating $\\#$ as the left endmarker
${\vdash}$.

The functions $f_{1}$ and $f_{2}$ can be realised by aperiodic transducers as
they only simulate automata for the aperiodic domains of $C_{1}$ and the
reverse of $C_{2}$ respectively, and the function $f_{3}$ executes
$\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ one after the other, and hence is also
aperiodic.

  * •

$C=[L,C_{1}]^{k\star}$ or $C=[L,C_{1}]_{r}^{k\star}$. Here
$L\subseteq\Sigma^{*}$ is an aperiodic language which is also a prefix code
with bounded synchronisation delay, and $k\geq 1$ is a natural number. Let
$f=[\\![C_{1}]\\!]\colon\Sigma^{*}\to\Gamma^{*}$ be the aperiodic function
defined by $C_{1}$. We write
$[L,f]^{k\star}={L^{<k}}\,?\,{({\Sigma^{*}}\triangleright{\varepsilon})}:{(f_{3}\circ
f_{2}\circ f_{1})}$, where $\varepsilon$ is the output produced when the input
has less than $k$ $L$ factors; otherwise the output is produced by the
composition of 3 aperiodic functions. As aperiodic functions are closed under
composition, this gives the result. The first one,
$f_{1}\colon\Sigma^{*}\to(\Sigma\cup\\{\\#\\})^{*}$ splits an input word $w\in
L^{*}$ according to the unique factorization $w=u_{1}u_{2}\cdots u_{n}$ with
$n\geq 0$ and $u_{i}\in L$ for all $1\leq i\leq n$ and inserts $\\#$ symbols:
$f_{1}(w)=\\#u_{1}\\#u_{2}\\#\cdots\\#u_{n}\\#$. The domain of $f_{1}$ is
$L^{*}$.

The second function $f_{2}$ constructs the sequence of $k$ factors. Its domain
is $\\#(\Sigma^{*}\\#)^{\geq k}$ and it is defined as follows, with
$u_{i}\in\Sigma^{*}$:

$f_{2}(\\#u_{1}\\#u_{2}\\#\cdots\\#u_{n}\\#)=\\#u_{1}u_{2}\cdots
u_{k}\\#u_{2}\cdots u_{k+1}\\#\cdots\\#u_{n-k+1}\cdots u_{n}\\#\,.$

Finally, the third function simply applies $f$ and erases the $\\#$ symbols:

$f_{3}(\\#v_{1}\\#v_{2}\\#\cdots\\#v_{m}\\#)=f(v_{1})f(v_{2})\cdots
f(v_{m})\,.$

In particular, $f_{3}(\\#)=\varepsilon$. We have
$\mathsf{dom}(f_{3})=\\#(\mathsf{dom}(f)\\#)^{*}$.

For the reverse iteration, we simply change the last function and use instead

$f_{4}(\\#v_{1}\\#v_{2}\\#\cdots\\#v_{m}\\#)=f(v_{m})\cdots
f(v_{2})f(v_{1})\,.$

Lemma 5.3 below proves that the functions $f_{i}$ for $i\leq 4$ are aperiodic.

$0$$1$$2$$3$$-3$$end$$-1$$-2$${\vdash}/\varepsilon,+1$$a/a,+1$$a/a,+1$$a/a,+1$$a/\varepsilon,-1$$a/\varepsilon,-1$$\\#/\\#,+1$$\\#/\varepsilon,+1$$\\#/\varepsilon,+1$$\\#/\\#,+1$$\\#,a/\varepsilon,-1$$\\#/\varepsilon,-1$$\\#/\varepsilon,-1$$\\#/\varepsilon,+1$
Figure 3: The transducer $T_{2}$ for $k=3$.

######  Lemma 5.3.

The functions $f_{1},f_{2},f_{3},f_{4}$ are realised by aperiodic 2DFTs.

######  Proof 5.4.

The function $f_{1}$. First, since $L$ is an aperiodic language which is a
prefix code with bounded synchronisation delay, $L^{*}$ is aperiodic. Let
$\mathcal{A}_{1}$ be an aperiodic deterministic automaton that recognizes
$L^{*}$. Let $w$ be a word in $L^{*}$ and $w=u_{1}\cdots u_{n}$ with $u_{i}\in
L$. Since $L$ is a code, this decomposition is unique. Notice that
$\varepsilon\notin L$. We claim that the run of $\mathcal{A}_{1}$ over $w$
reaches final states exactly at the end of each $u_{i}$. Should this hold,
then we can easily construct a (one-way) aperiodic transducer $T_{1}$
realising $f_{1}$ by simply simulating $\mathcal{A}_{1}$ and copying its
input, adding $\\#$ symbols each time $\mathcal{A}_{1}$ reaches a final state.

It remains to prove the claim. First, since for any $1\leq i\leq n$,
$u_{1}\cdots u_{i}$ belongs to $L^{*}$, $\mathcal{A}_{1}$ reaches a final
state after reading $u_{i}$. Conversely, suppose $\mathcal{A}_{1}$ reaches a
final state after reading some nonempty prefix $v$ of $w$. Then $v$ can be
written $u_{1}\cdots u_{i}u^{\prime}$ for some index $0\leq i<n$ and some
nonempty prefix $u^{\prime}$ of $u_{i+1}$. But since $\mathcal{A}_{1}$ reaches
a final state on $v$, we have $v\in L^{*}$. Hence, there is a unique
decomposition $v=v_{1}\cdots v_{m}$ with $v_{j}\in L$. Since $v=u_{1}\cdots
u_{i}u^{\prime}=v_{1}\cdots v_{m}$, either $u_{1}$ is a prefix of $v_{1}$ or
conversely. Since $L$ is a prefix code, and both $u_{1}$ and $v_{1}$ belong to
$L$, we obtain $u_{1}=v_{1}$. By induction, we get that $u_{j}=v_{j}$ for
$j\leq i$. Now, $u^{\prime}=v_{i+1}\cdots v_{m}$ is a nonempty prefix of
$u_{i+1}$. Using again that $L$ is a prefix code, we get $m=i+1$ and
$u^{\prime}=v_{i+1}=u_{i+1}$, which concludes the proof of the claim.

The function $f_{2}$. The domain of $f_{2}$ is the language
$K=\\#(\Sigma^{*}\\#)^{\geq k}$. We construct an aperiodic 2DFT $T_{2}$ for
$f_{2}$ (see Figure 3 for $T_{2}$ where $k=3$). Let
$T_{2}=(\\{-k,-k+1,\ldots,0,\ldots,k-1,k\\}\cup\\{end\\},\Sigma\cup\\{\\#\\},\Sigma\cup\\{\\#\\},\delta_{2},\gamma_{2},0,\\{end\\})$
be the 2DFT realising $f_{2}$. The transition function $\delta_{2}$ is defined
as:

  * •

$\delta_{2}(0,{\vdash})=(0,+1)$,

  * •

$\delta_{2}(i,a)=(i,+1)$ for $0<i\leq k$ and $a\in\Sigma$,

  * •

$\delta_{2}(i,a)=(i,-1)$ for $-k<i<0$ and $a\in\Sigma$,

  * •

$\delta_{2}(end,a)=\delta_{2}(end,\\#)=(-k,-1)$,

  * •

$\delta_{2}(i,\\#)=(i+1,+1)$ for $0\leq i<k$,

  * •

$\delta_{2}(k,\\#)=(end,+1)$,

  * •

$\delta_{2}(i,\\#)=(i+1,-1)$ for $-k\leq i<-1$,

  * •

$\delta_{2}(-1,\\#)=(1,+1)$.

The production function $\gamma_{2}$ is then simply $\gamma_{2}(i,a)=a$ for
$i>0$, $\gamma_{2}(i,\\#)=\\#$ for $i=0$ and $i=k$, and is set to
$\varepsilon$ for all other transitions.

The way the transducer $T_{2}$ works is that it reads forward, in the strictly
positive states, a factor of the input containing $k$ $\\#$ symbols, copying
it to the output. Upon reaching the $k^{th}$ $\\#$ symbol, it goes to state
$end$ to check if it was the last $\\#$ symbol, and otherwise reads back the
last $k-1$ $\\#$ symbols and starts again.

Let us prove the aperiodicity of $T_{2}$. First, notice that the
$\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}}$ and
$\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}}$ are
always aperiodic relations, for any finite 2DFT. This is due to the fact that
if a
$\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}}$
step exists in some $u\neq\varepsilon$, it also appears in $uv$. So for
$(v^{n})_{n>0}$, the
$\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}}$ and
$\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}}$
relations are monotone, and since we consider finite state machines, they
eventually stabilize. So we turn to traversal steps. These traversal steps
only depend on the number of $\\#$ symbols in the word, as well as the
starting and ending symbols. In particular, if a word $v$ has $k+1$ or more
$\\#$ symbols, the only traversals it realises are in
$\\{(\rightarrow,0,k),(\rightarrow,0,end),(\rightarrow,1,k),(\rightarrow,1,end)\\}$,
starting from $0$ is possible only if $v$ starts with $\\#$, the target state
is $end$ if the last letter of $v$ is $\\#$, otherwise it is $k$. Notice that
both $(\rightarrow,0,end)$ and $(\rightarrow,1,end)$ are possible if
$v\in\\#(\Sigma^{*}\\#)^{\geq k}$. Similarly, both $(\rightarrow,0,k)$ and
$(\rightarrow,1,k)$ are possible if $v\in\\#(\Sigma^{*}\\#)^{\geq
k}\Sigma^{+}$. Then given any word $v\in(\Sigma\cup\\{\\#\\})^{+}$, both
$v^{k+1}$ and $v^{k+2}$ have either no $\\#$ symbol, or at least $k+1$ $\\#$
symbols; further they have the same starting and ending letters. Thus they
realise the same steps.

The function $f_{3}$. The goal of $f_{3}$ is to iteratively simulate $f$ on
each factor appearing between $\\#$ symbols. To this end, $T_{3}$ is defined
as the transducer $T$ realising $f$, with the exception that it reads the
$\\#$ symbols as endmarkers, and upon reaching a final state while reading a
$\\#$ symbol, it first checks if the next symbol is ${\dashv}$, and in this
case ends the run, or simulates the move of $T$ reading ${\vdash}$ from the
initial state. Note that $\\#$ being used for both endmarkers could generate
some non-determinism, however this can be avoided as the left endmarker can
only be reached while moving to the left, and symmetrically for the right
endmarker. Then we solve non-determinism by duplicating the problematic states
$q$ to states $q_{\ell}$ (where $\\#$ is seen as the left endmarker) and
$q_{r}$ (where $\\#$ is seen a right endmarker), which can only be reached
while moving to the left or the right respectively.

We now turn to the aperiodicity of $T_{3}$. If the input word $v$ does not
contain any $\\#$ symbol, then the
$(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},\rightarrow,\leftarrow)$-runs
of $v^{n}$ are the same as the ones in $T$, and since $T$ is aperiodic then we
get $\varphi(v^{n})=\varphi(v^{n+1})$ for some $n$, where $\varphi$ is the
syntactic morphism of $T$.

Otherwise, let us remark that by design, once the reading head has gone right
of a given $\\#$ symbol, it never goes back to its left, and secondly the
behavior of $T_{3}$ when going from left to right of a $\\#$ symbol is always
the same since it simulates the initial transition of $T$. So given a word $v$
with at least one $\\#$ symbol, let $u_{1}$ and $u_{2}$ be the prefix and
suffix of $v$ upto the first and from the last $\\#$ respectively, i.e.,
$v=u_{1}\\#w_{1}\\#\cdots w_{m}\\#u_{2}$ with $m\geq 0$ and
$u_{1},u_{2},w_{1},\ldots,w_{m}\in\Sigma^{*}$. Then there exists no
$\leftarrow$ traversal of $v^{n}$ for $n\geq 2$ since the reading head cannot
move from right to left of a $\\#$ symbol. The $\rightarrow$ traversals of
$v^{n}$, for $n\geq 2$, exist if and only if $u_{2}u_{1},w_{1},\ldots,w_{m}$
belong to the domain of $T$, and consist of all $(\rightarrow,p,q)$, where
$\varphi(u_{1})$ contains $(\rightarrow,p,f)$ for some final state $f$, and
$\varphi(u_{2})$ contains $(\rightarrow,\iota,q)$ where $\iota$ is the initial
state. These traversals are then the same for $v^{2}$ and $v^{3}$, which
concludes the proof of aperiodicity of $T_{3}$.

The function $f_{4}$. The transducer $T_{4}$ realising $f_{4}$ is similar to
$T_{3}$. The main difference is that it starts by reaching the end of the
word, then goes back to the previous $\\#$ symbol to simulate $T$. On reaching
the end of the run in $T$ (in a final state of $T$ when reading $\\#$) it
treats $\\#$ as ${\dashv}$ and then enters into a special state which moves
the reading head to the left, till the time it has finished reading two $\\#$
symbols, while outputting $\varepsilon$ all along. When it reads the second
$\\#$, it moves right entering the state $T$ would, on reading ${\vdash}$ from
its initial state, and continues simulating $T$. This goes on until it reaches
the start symbol ${\vdash}$, and then it goes to the final state of $T_{4}$
that only moves to the right outputting $\varepsilon$ all along until the end
of the input to ${\dashv}$.

The arguments for the aperiodicity of $T_{4}$ are similar to the ones for
$T_{3}$.

###  5.2 SD-regular transducer expressions for aperiodic 2DFTs

In this section, we show that the runs of an aperiodic 2DFT have a
“stabilising” property. This property crucially distinguishes aperiodic 2DFTs
from non aperiodic ones, and we use this in our proof to obtain SDRTEs from
aperiodic 2DFTs. In the remainder of this section, we fix an aperiodic 2DFT
$\mathcal{A}=(Q,\Sigma,\Gamma,\delta,\gamma,q_{0},F)$. Let
$\varphi\colon(\Sigma\uplus\\{{\vdash},{\dashv}\\})^{*}\to\mathsf{TrM}$ be the
canonical surjective morphism to the transition monoid of $\mathcal{A}$.

####  5.2.1 Stabilising runs in two-way automata

Consider a _code_ $L\subseteq\Sigma^{*}$ such that $X=\varphi(L)$ is
$k$-stabilizing for some $k>0$. We will see that a run of $\mathcal{A}$ over a
word $w\in L^{*}$ has some nice properties. Intuitively, if it moves forward
through $k$ factors from $L$ then it never moves backward through more than
$k$ factors.

More precisely, let $w=u_{1}u_{2}\cdots u_{n}$ be the unique factorisation of
$w\in L^{*}$ with $u_{i}\in L$ for $1\leq i\leq n$. We assume that $n\geq k$.
We start with the easiest fact.

######  Lemma 5.5.

If
$(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},p,q)\in\varphi(w)$
then the run of $\mathcal{A}$ over $w$ starting on the left in state $p$ only
visits the first $k$ factors $u_{1}\cdots u_{k}$ of $w$.

######  Proof 5.6.

Since $X$ is $k$-stabilising, we have $\varphi(w)=\varphi(u_{1}\cdots u_{k})$.
Hence,
$(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},p,q)\in\varphi(u_{1}\cdots
u_{k})$ and the result follows since $\mathcal{A}$ is deterministic.

Notice that the right-right
($\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}}$)
runs of $\mathcal{A}$ over $w$ need not visit the last $k$ factors only (see
Lemma 5.11 below). This is due to the fact that _stabilising_ is not a
symmetric notion.

Next, we consider the left-right runs of $\mathcal{A}$ over $w$.

######  Lemma 5.7.

Assume that $(\rightarrow,p,q)\in\varphi(w)$. Then the run $\rho$ of
$\mathcal{A}$ over $w$ starting on the left in state $p$ has the following
property, that we call $k$-forward-progressing: for each $1\leq i<n-k$, after
reaching the suffix $u_{i+k+1}\cdots u_{n}$ of $w$, the run $\rho$ will never
visit again the prefix $u_{1}\cdots u_{i}$. See Figure 4 for a non-example and
Figure 10 for an example.

######  Proof 5.8.

Towards a contradiction, assume that for some $1\leq i<n-k$, the run $\rho$
visits $u_{1}\cdots u_{i}$ after visiting $u_{i+k+1}\cdots u_{n}$ (See Figure
4). Then, there exists a subrun $\rho^{\prime}$ of $\rho$ making some
$(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{1},q_{3})$-step
on $u_{i+1}\cdots u_{n}$ and visiting $u_{i+k+1}$ (on Figure 4 we have
$\rho^{\prime}=\rho_{2}\rho_{3}$). Hence
$(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{1},q_{3})\in\varphi(u_{i+1}\cdots
u_{n})$ and by Lemma 5.5 we deduce that $\rho^{\prime}$ visits $u_{i+1}\cdots
u_{i+k}$ only, a contradiction.

Figure 4: A left-right run which is not $k$-forward-progressing

######  Lemma 5.9.

Assume that $(\leftarrow,p,q)\in\varphi(w)$. Then the run $\rho$ of
$\mathcal{A}$ over $w$ starting on the right in state $p$ has the following
property, that we call $k$-backward-progressing: for each $1\leq i<n-k$, after
reaching the prefix $u_{1}\cdots u_{i}$ of $w$, the run $\rho$ will never
visit again the suffix $u_{i+k+1}\cdots u_{n}$.

######  Proof 5.10.

This Lemma is a consequence of Lemma 5.5. Indeed, consider any part of $\rho$
that visits $u_{i+1}$ again (in some state $q_{1}$) after visiting $u_{i}$,
for some $1\leq i<n-k$. As $\rho$ is a $\leftarrow$ run, it will later cross
from $u_{i+1}$ to $u_{i}$ (reaching some state $q_{3}$). Then
$(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{1},q_{3})$
is a run on $u_{i+1}\cdots u_{n}$. By Lemma 5.5, it does not visit
$u_{i+k+1}\cdots u_{n}$, which concludes the proof (See Figure 5 for a non-
example).

Figure 5: A right-left run which is not $k$-backward-progressing

######  Lemma 5.11.

Assume that
$(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},p,q)\in\varphi(w)$
and let $\rho$ be the run of $\mathcal{A}$ over $w$ starting on the right in
state $p$. Then, either $\rho$ visits only the last $k$ factors
$u_{n-k+1}\cdots u_{n}$, or for some $1\leq i\leq n-k$ the run $\rho$ is the
concatenation $\rho_{1}\rho_{2}\rho_{3}$ of a $k$-backward-progressing run
$\rho_{1}$ over $u_{i+1}\cdots u_{n}$ followed by a run $\rho_{2}$ staying
inside some $u_{i}\cdots u_{i+k}$, followed by some $k$-forward-progressing
run $\rho_{3}$ over $u_{i+1}\cdots u_{n}$. See Figure 6.

######  Proof 5.12.

Assume that $\rho$ visits $u_{1}\cdots u_{n-k}$ and let $u_{i}$ ($1\leq i\leq
n-k$) be the left-most factor visited by $\rho$. We split $\rho$ in
$\rho_{1}\rho_{2}\rho_{3}$ (see Figure 6) where

Figure 6: A right-right run $\rho_{1}\rho_{2}\rho_{3}$ where $\rho_{1}$ is
$k$-backward-progressing, $\rho_{2}$ is local to $u_{i}\cdots u_{i+k}$ and
$\rho_{3}$ is $k$-forward-progressing.

  * •

$\rho_{1}$ is the prefix of $\rho$, starting on the right of $w$ in state $p$
and going until the first time $\rho$ crosses from $u_{i+1}$ to $u_{i}$.
Hence, $\rho_{1}$ is a run over $u_{i+1}\cdots u_{n}$ starting on the right in
state $p$ and exiting on the left in some state $q_{1}$. We have
$(\leftarrow,p,q_{1})\in\varphi(u_{i+1}\cdots u_{n})$. By Lemma 5.9 we deduce
that $\rho_{1}$ is $k$-backward-progressing.

  * •

Then, $\rho_{2}$ goes until the last crossing from $u_{i}$ to $u_{i+1}$.

  * •

Finally, $\rho_{3}$ is the remaining suffix of $\rho$. Hence, $\rho_{3}$ is a
run over $u_{i+1}\cdots u_{n}$ starting on the left in some state $q_{2}$ and
exiting on the right in state $q$. We have
$(\rightarrow,q_{2},q)\in\varphi(u_{i+1}\cdots u_{n})$. By Lemma 5.7 we deduce
that $\rho_{3}$ is $k$-forward-progressing.

It remains to show that $\rho_{2}$ stays inside $u_{i}\cdots u_{i+k}$. Since
$u_{i}$ is the left-most factor visited by $\rho$, we already know that
$\rho_{2}$ does not visit $u_{1}\cdots u_{i-1}$. Similarly to Lemma 5.9, any
maximal subrun $\rho_{2}^{\prime}$ of $\rho_{2}$ that does not visit $u_{i}$
is a
$\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}}$ run
on $u_{i+1}\cdots u_{n}$ since $\rho_{2}$ starts and ends at the frontier
between $u_{i}$ and $u_{i+1}$. By Lemma 5.5, the subrun $\rho_{2}^{\prime}$
does not visit $u_{i+k+1}\cdots u_{n}$ and thus $\rho_{2}$ stays inside
$u_{i}\cdots u_{i+k}$.

######  Example 5.13.

We illustrate the stabilising runs of an aperiodic 2DFT using the aperiodic
2DFT $\mathcal{A}$ in Figure 2. Figure 7 depicts the run of $\mathcal{A}$ on
words in $b(a^{*}b)^{\geq 3}$. We use the set $Z_{1}$ computed in Example 3.5.
Notice that a run of $\mathcal{A}$ on such words is 4-forward-progressing, as
seen below. For each $w=u_{1}u_{2}\cdots u_{n}$ with $n>3$, $u_{1}=b$ and
$u_{i}\in a^{*}b$ for $2\leq i\leq n$, we have $\varphi(w)=Z_{1}$ and one can
see that

  * •

each
$(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},p,q)\in
Z_{1}$, is such that, whenever the run of $\mathcal{A}$ starts at the left of
$w$ in state $p$, it stays within $u_{1}\cdots u_{4}$ and never visits
$u_{5}\cdots u_{n}$ (as in Lemma 5.5).

  * •

each $(\rightarrow,p,q)\in Z_{1}$, is such that, whenever the run of
$\mathcal{A}$ starts at the left of $w$ in state $p$ and reaches $u_{i+5}$,
for $i\geq 1$, it no longer visits any of $u_{1}\cdots u_{i}$ (4-forward-
progressing as in Lemma 5.7).

  * •

each
$(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},p,q)\in
Z_{1}$, is such that, whenever the run of $\mathcal{A}$ starts at the right of
$w$ in state $p$, it never visits $u_{1}\cdots u_{n-4}$ (the easy case of
Lemma 5.11).

Figure 7: An accepting run on words in $b(a^{*}b)^{\geq 3}$. Bottom left:
$(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{2},q_{2})$.

####  5.2.2 Computing SDRTE

In this section, we show how to construct SDRTEs which are equivalent to
aperiodic 2DFTs. Recall that
$\varphi\colon(\Sigma\uplus\\{{\vdash},{\dashv}\\})^{*}\to\mathsf{TrM}$ is the
canonical surjective morphism to the transition monoid of the 2DFT
$\mathcal{A}=(Q,\Sigma,\Gamma,\delta,\gamma,q_{0},F)$. Given a regular
expression $E$ and a monoid element $s\in\mathsf{TrM}$, we let
$\mathcal{L}(E,s)=\mathcal{L}(E)\cap\varphi^{-1}(s)$. The main construction of
this section is given by Theorem 5.14.

Recall that $\mathsf{TrM}$ represents the transition monoid of a 2DFT, and
consists of elements $\varphi(w)$ for all $w\in\Sigma^{*}$, where each
$\varphi(w)=\\{(d,p,q)\mid\text{there is a }(d,p,q)\text{-run on
}w\\}\subseteq\\{\rightarrow,\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},\leftarrow\\}\times
Q^{2}$. The elements of $\varphi(w)$ are called _steps_ , since any run of $w$
is obtained by a sequence of such steps. If the states $p,q$ in a step
$(d,p,q)$ are clear from the context, or is immaterial for the discussion we
also refer to a step as a $d$ step,
$d\in\\{\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},\rightarrow,\leftarrow\\}$.
In this case we also refer to a step $(d,p,q)$ as a $d$ step having $p$ as the
starting state and $q$ as the final state.

######  Theorem 5.14.

Let $E$ be an unambiguous, stabilising, SD-regular expression over
$\Sigma\uplus\\{{\vdash},{\dashv}\\}$ and let $s\in\mathsf{TrM}$. For each
step
$x\in\\{\rightarrow,\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},\leftarrow\\}\times
Q^{2}$, we can construct an SDRTE $\mathsf{C}_{E,s}(x)$ such that:

  1. 1.

$\mathsf{C}_{E,s}(x)=\bot$ when $x\notin s$, and otherwise

  2. 2.

$\mathsf{dom}([\\![\mathsf{C}_{E,s}(x)]\\!])=\mathcal{L}(E,s)$ and for all
words $w\in\mathcal{L}(E,s)$, $[\\![\mathsf{C}_{E,s}(x)]\\!](w)$ is the output
produced by $\mathcal{A}$ running over $w$ according to step $x$.

When $w=\varepsilon$ and $s=\mathbf{1}=\varphi(\varepsilon)$ with
$x\in\mathbf{1}$, this means
$[\\![\mathsf{C}_{E,s}(x)]\\!](\varepsilon)=\varepsilon$.

######  Proof 5.15.

The construction is by structural induction on $E$.

##### Atomic expressions

We first define $\mathsf{C}_{E,s}(x)$ when $E$ is an atomic expression, i.e.,
$\emptyset$, $\varepsilon$ or $a$ for $a\in\Sigma$.

  * •

$E=\emptyset$: we simply set $\mathsf{C}_{\emptyset,s}(x)=\bot$, which is the
nowhere defined function.

  * •

$E=\varepsilon$: when $s=\mathbf{1}$ and $x\in s$ then we set
$\mathsf{C}_{\varepsilon,s}(x)={\varepsilon}\triangleright{\varepsilon}$ and
otherwise we set $\mathsf{C}_{\varepsilon,s}(x)=\bot$.

  * •

$E=a\in\Sigma\uplus\\{{\vdash},{\dashv}\\}$: again, we set
$\mathsf{C}_{a,s}(x)=\bot$ if $s\neq\varphi(a)$ or $x\notin s$. Otherwise,
there are two cases. Either
$x\in\\{(\rightarrow,p,q),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},p,q)\\}$
for some states $p,q$ such that $\delta(p,a)=(q,+1)$, or
$x\in\\{(\leftarrow,p,q),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},p,q)\\}$
for some states $p,q$ with $\delta(p,a)=(q,-1)$. In both cases the output
produced is $\gamma(p,a)$ and we set
$\mathsf{C}_{a,s}(x)={a}\triangleright{\gamma(p,a)}$.

##### Disjoint union

If the expression is $E\cup F$ with $\mathcal{L}(E)$ and $\mathcal{L}(F)$
disjoint, then we simply set $\mathsf{C}_{E\cup
F,s}(x)=\mathsf{C}_{E,s}(x)+\mathsf{C}_{F,s}(x)$.

##### Unambiguous concatenation $E\cdot F$

Here, we suppose that we have SDRTEs for $\mathsf{C}_{E,s}(x)$ and
$\mathsf{C}_{F,s}(x)$ for all $s$ in $\mathsf{TrM}$ and all steps
$x\in\\{\rightarrow,\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},\leftarrow\\}\times
Q^{2}$. We show how to construct SDRTEs for $\mathsf{C}_{E\cdot F,s}(x)$,
assuming that the concatenation $\mathcal{L}(E)\cdot\mathcal{L}(F)$ is
unambiguous.

A word $w\in\mathcal{L}(E\cdot F)$ has a unique factorization $w=uv$ with
$u\in\mathcal{L}(E)$ and $v\in\mathcal{L}(F)$. Let $s=\varphi(u)$ and
$t=\varphi(v)$. A run $\rho$ over $w$ is obtained by stitching together runs
over $u$ and runs over $v$ as shown in Figure 8. In the left figure, the run
over $w$ follows step $x=(\rightarrow,p,q)$ starting on the left in state $p$
and exiting on the right in state $q$. The run $\rho$ splits as
$\rho_{0}\rho_{1}\rho_{2}\rho_{3}\rho_{4}\rho_{5}$ as shown in the figure. The
output of the initial part $\rho_{0}$ is computed by
$\mathsf{C}_{E,s}((\rightarrow,p,p_{1}))$ over $u$ and the output of the final
part $\rho_{5}$ is computed by $\mathsf{C}_{F,t}((\rightarrow,p_{5},q))$ over
$v$. We focus now on the internal part $\rho_{1}\rho_{2}\rho_{3}\rho_{4}$
which consists of an alternate sequence of left-left runs over $v$ and right-
right runs over $u$. The corresponding sequence of steps
$x_{1}=(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},p_{1},p_{2})\in
t$,
$x_{2}=(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},p_{2},p_{3})\in
s$,
$x_{3}=(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},p_{3},p_{4})\in
t$ and
$x_{4}=(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},p_{4},p_{5})\in
s$ depends only on $s=\varphi(u)$ and $t=\varphi(v)$.

Figure 8: Decomposition of a $(\rightarrow,p,q)$-run and a
$(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},p,q)$-run
over the product $w=uv$.

These internal zigzag runs will be frequently used when dealing with
concatenation or Kleene star. They alternate left-left
($\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}}$)
steps on the right word $v$ and right-right
($\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}}$)
steps on the left word $u$. They may start with a
$\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}}$-step
or a
$\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}}$-step.
The sequence of steps in a _maximal_ zigzag run is entirely determined by the
monoid elements $s=\varphi(u)$, $t=\varphi(v)$, the starting step
$d\in\\{\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}}\\}$
and the starting state $p^{\prime}$ of step $d$. The final step of this
_maximal_ sequence is some
$d^{\prime}\in\\{\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}}\\}$
and reaches some state $q^{\prime}$. We write
$Z_{s,t}(p^{\prime},d)=(d^{\prime},q^{\prime})$. For instance, on the left of
Figure 8 we get
$Z_{s,t}(p_{1},\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}})=(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},p_{5})$
whereas on the right of Figure 8 we get
$Z_{s,t}(p_{1},\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}})=(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},p_{4})$.
By convention, if the sequence of zigzag steps is empty then we define
$Z_{s,t}(p,\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}})=(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},p)$
and
$Z_{s,t}(p,\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}})=(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},p)$.

######  Lemma 5.16.

We use the above notation. We can construct SDRTEs
$\mathsf{ZC}_{E,s}^{F,t}(p,d)$ for $p\in Q$ and
$d\in\\{\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}}\\}$
such that
$\mathsf{dom}([\\![\mathsf{ZC}_{E,s}^{F,t}(p,d)]\\!])=\mathcal{L}(E,s)\mathcal{L}(F,t)$
and for all $u\in\mathcal{L}(E,s)$ and $v\in\mathcal{L}(F,t)$ the value
$[\\![\mathsf{ZC}_{E,s}^{F,t}(p,d)]\\!](uv)$ is the output produced by the
_internal_ zigzag run of $\mathcal{A}$ over $(u,v)$ following the maximal
sequence of steps starting in state $p$ with a $d$-step.

######  Proof 5.17.

We first consider the case
$d={\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}}}$
and
$Z_{s,t}(p,\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}})=(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q)$
for some $q\in Q$ which is illustrated on the left of Figure 8. Since
$\mathcal{A}$ is deterministic, there is a unique maximal sequence of steps
(with $n\geq 0$, $p_{1}=p$ and $p_{2n+1}=q$):
$x_{1}=(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},p_{1},p_{2})\in
t$,
$x_{2}=(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},p_{2},p_{3})\in
s$, …,
$x_{2n-1}=(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},p_{2n-1},p_{2n})\in
t$,
$x_{2n}=(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},p_{2n},p_{2n+1})\in
s$. The zigzag run $\rho$ following this sequence of steps over $uv$ splits as
$\rho_{1}\rho_{2}\cdots\rho_{2n}$ where $\rho_{2i}$ is the unique run on $u$
following step $x_{2i}$ and $\rho_{2i+1}$ is the unique run on $v$ following
step $x_{2i+1}$. The output of these runs are given by
$[\\![\mathsf{C}_{E,s}(x_{2i})]\\!](u)$ and
$[\\![\mathsf{C}_{F,t}(x_{2i+1})]\\!](v)$. When $n=0$ the zigzag run $\rho$ is
empty and we simply set
$\mathsf{ZC}_{E,s}^{F,t}(p,\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}})={(\mathcal{L}(E,s)\mathcal{L}(F,t))}\triangleright{\varepsilon}$.
Assume now that $n>0$. The required SDRTE computing the output of $\rho$ can
be defined as

$\displaystyle\mathsf{ZC}_{E,s}^{F,t}(p,\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}})={}$
$\displaystyle\big{(}({\mathcal{L}(E,s)}\triangleright{\varepsilon})\cdot\mathsf{C}_{F,t}(x_{1})\big{)}\odot\big{(}\mathsf{C}_{E,s}(x_{2})\cdot\mathsf{C}_{F,t}(x_{3})\big{)}\odot\cdots\odot$
$\displaystyle\big{(}\mathsf{C}_{E,s}(x_{2n-2})\cdot\mathsf{C}_{F,t}(x_{2n-1})\big{)}\odot\big{(}\mathsf{C}_{E,s}(x_{2n})\cdot({\mathcal{L}(F,t)}\triangleright{\varepsilon})\Big{)}\,.$

Notice that each Cauchy product in this expression is unambiguous since the
product $\mathcal{L}(E)\cdot\mathcal{L}(F)$ is unambiguous.

The other cases can be handled similarly. For instance, when
$Z_{s,t}(p,\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}})=(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q)$
as on the right of Figure 8, the sequence of steps ends with
$x_{2n-1}=(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},p_{2n-1},p_{2n})\in
t$ with $n>0$ and $p_{2n}=q$ and the zigzag run $\rho$ is
$\rho_{1}\rho_{2}\cdots\rho_{2n-1}$. The SDRTE
$\mathsf{ZC}_{E,s}^{F,t}(p,\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}})$
is given by

$\big{(}({\mathcal{L}(E,s)}\triangleright{\varepsilon})\cdot\mathsf{C}_{F,t}(x_{1})\big{)}\odot\big{(}\mathsf{C}_{E,s}(x_{2})\cdot\mathsf{C}_{F,t}(x_{3})\big{)}\odot\cdots\odot\big{(}\mathsf{C}_{E,s}(x_{2n-2})\cdot\mathsf{C}_{F,t}(x_{2n-1})\big{)}\,.$

The situation is symmetric for
$\mathsf{ZC}_{E,s}^{F,t}(p,\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}})$:
the sequence starts with a right-right step
$x_{2}=(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},p_{2},p_{3})\in
s$ with $p=p_{2}$ and we obtain the SDRTE simply by removing the first factor
$\big{(}({\mathcal{L}(E,s)}\triangleright{\varepsilon})\cdot\mathsf{C}_{F,t}(x_{1})\big{)}$
in the Hadamard products above.

We come back to the definition of the SDRTEs for $\mathsf{C}_{E\cdot F,r}(x)$
with $r\in\mathsf{TrM}$ and $x\in r$. As explained above, the output produced
by a run $\rho$ following step $x$ over a word $w=uv$ with
$u\in\mathcal{L}(E,s)$, $v\in\mathcal{L}(F,t)$ and $r=st$ consists of an
initial part, a zigzag internal part, and a final part. There are four cases
depending on the step $x$.

  * •

$x=(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},p,q)$.
Either the run $\rho$ stays inside $u$ (zigzag part empty) or there is a
zigzag internal part starting with
$(p^{\prime},\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}})$
such that $(\rightarrow,p,p^{\prime})\in\varphi(u)$ and ending with
$(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q^{\prime})$
such that $(\leftarrow,q^{\prime},q)\in\varphi(u)$. Thus we define the SDRTE
$\mathsf{C}_{E\cdot F,r}(x)$ as

$\displaystyle\sum_{st=r\mid x\in s}$
$\displaystyle\mathsf{C}_{E,s}(x)\cdot\big{(}{\mathcal{L}(F,t)}\triangleright{\varepsilon}\big{)}+{}$
$\displaystyle\sum_{\begin{subarray}{c}st=r,\,(p^{\prime},q^{\prime})\,\mid\\\
Z_{s,t}(p^{\prime},\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}})=(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q^{\prime})\end{subarray}}\big{(}\mathsf{C}_{E,s}((\rightarrow,p,p^{\prime}))\cdot({\mathcal{L}(F,t)}\triangleright{\varepsilon})\big{)}\odot\mathsf{ZC}_{E,s}^{F,t}(p^{\prime},\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}})\odot\big{(}\mathsf{C}_{E,s}((\leftarrow,q^{\prime},q))\cdot({\mathcal{L}(F,t)}\triangleright{\varepsilon})\big{)}$

Notice that all Cauchy products are unambiguous since the concatenation
$\mathcal{L}(E)\cdot\mathcal{L}(F)$ is unambiguous. The sums are also
unambiguous. Indeed, a word $w\in\mathcal{L}(E\cdot F,r)$ has a unique
factorization $w=uv$ with $u\in\mathcal{L}(E)$ and $v\in\mathcal{L}(F)$. Hence
$s=\varphi(u)$ and $t=\varphi(v)$ are uniquely determined and satisfy $st=r$.
Then, either $x\in s$ and $w$ is only in the domain of
$\mathsf{C}_{E,s}(x)\cdot\big{(}{\mathcal{L}(F,t)}\triangleright{\varepsilon}\big{)}$.
Or there is a unique $p^{\prime}$ with $(\rightarrow,p,p^{\prime})\in s$ and a
unique $q^{\prime}$ with
$Z_{s,t}(p^{\prime},\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}})=(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q^{\prime})$
and $(\leftarrow,q^{\prime},q)\in s$. Notice that if
$(\rightarrow,p,p^{\prime})\notin s$ then
$\mathsf{C}_{E,s}((\rightarrow,p,p^{\prime}))=\bot$ and similarly if
$(\leftarrow,q^{\prime},q)\notin s$. Hence we could have added the condition
$(\rightarrow,p,p^{\prime}),(\leftarrow,q^{\prime},q)\in s$ to the second sum,
but do not, to reduce clutter.

  * •

$x=(\rightarrow,p,q)$. Here the run must cross from left to right. Thus we
define the SDRTE $\mathsf{C}_{E\cdot F,r}(x)$ as

$\sum_{\begin{subarray}{c}st=r,\,(p^{\prime},q^{\prime})\,\mid\\\
Z_{s,t}(p^{\prime},\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}})=(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q^{\prime})\end{subarray}}\big{(}\mathsf{C}_{E,s}((\rightarrow,p,p^{\prime}))\cdot({\mathcal{L}(F,t)}\triangleright{\varepsilon})\big{)}\odot\mathsf{ZC}_{E,s}^{F,t}(p^{\prime},\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}})\odot\big{(}({\mathcal{L}(E,s)}\triangleright{\varepsilon})\cdot\mathsf{C}_{F,t}((\rightarrow,q^{\prime},q))\big{)}$

  * •

$x=(\leftarrow,p,q)$. This case is similar. The SDRTE $\mathsf{C}_{E\cdot
F,r}(x)$ is

$\sum_{\begin{subarray}{c}st=r,\,(p^{\prime},q^{\prime})\,\mid\\\
Z_{s,t}(p^{\prime},\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}})=(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q^{\prime})\end{subarray}}\big{(}({\mathcal{L}(E,s)}\triangleright{\varepsilon})\cdot\mathsf{C}_{F,t}((\leftarrow,p,p^{\prime}))\big{)}\odot\mathsf{ZC}_{E,s}^{F,t}(p^{\prime},\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}})\odot\big{(}\mathsf{C}_{E,s}((\leftarrow,q^{\prime},q))\cdot({\mathcal{L}(F,t)}\triangleright{\varepsilon})\big{)}$

  * •

$x=(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},p,q)$.
Finally, for right-right runs, the SDRTE $\mathsf{C}_{E\cdot F,r}(x)$ is

$\displaystyle\sum_{st=r\mid x\in t}$
$\displaystyle({\mathcal{L}(E,s)}\triangleright{\varepsilon})\cdot\mathsf{C}_{F,t}(x)+{}$
$\displaystyle\sum_{\begin{subarray}{c}st=r,\,(p^{\prime},q^{\prime})\,\mid\\\
Z_{s,t}(p^{\prime},\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}})=(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q^{\prime})\end{subarray}}\big{(}({\mathcal{L}(E,s)}\triangleright{\varepsilon})\cdot\mathsf{C}_{F,t}((\leftarrow,p,p^{\prime}))\big{)}\odot\mathsf{ZC}_{E,s}^{F,t}(p^{\prime},\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}})\odot\big{(}({\mathcal{L}(E,s)}\triangleright{\varepsilon})\cdot\mathsf{C}_{F,t}((\rightarrow,q^{\prime},q))\big{)}$

######  Example 5.18.

We go back to our running example of the aperiodic 2DFT $\mathcal{A}$ in
Figure 2 and illustrate the unambiguous concatenation. Consider $F=a^{+}b$,
$G=F^{2}$ and $E=F^{4}=G^{2}$. We know from Example 3.5 that
$\varphi(F)=Y_{2}$, $\varphi(G)=Y_{4}$ and $\varphi(E)=Z_{2}$. We compute
below some steps of $Y_{2}$, $Y_{4}$ and $Z_{2}$.

First, we look at some steps in $F$ for which the SDRTE are obtained directly
by looking at the automaton $\mathcal{A}$ in Figure 2 (we cannot give more
details here since we have not explained yet how to deal with Kleene-plus,
hence we rely on intuition for these steps).

$\displaystyle\mathsf{C}_{F,Y_{2}}((\rightarrow,q_{0},q_{1}))$
$\displaystyle=({a^{+}b}\triangleright{\varepsilon})$
$\displaystyle\mathsf{C}_{F,Y_{2}}((\rightarrow,q_{1},q_{2}))$
$\displaystyle=({a^{+}b}\triangleright{\varepsilon})$
$\displaystyle\mathsf{C}_{F,Y_{2}}((\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{2},q_{3}))$
$\displaystyle=({a}\triangleright{a})^{+}\cdot({b}\triangleright{b})$
$\displaystyle\mathsf{C}_{F,Y_{2}}((\rightarrow,q_{6},q_{0}))$
$\displaystyle=({a}\triangleright{a})^{+}\cdot({b}\triangleright{b})$
$\displaystyle\mathsf{C}_{F,Y_{2}}((\leftarrow,q_{3},q_{4}))$
$\displaystyle=({a^{+}b}\triangleright{\varepsilon})$
$\displaystyle\mathsf{C}_{F,Y_{2}}((\leftarrow,q_{4},q_{5}))$
$\displaystyle=({a^{+}b}\triangleright{\varepsilon})$
$\displaystyle\mathsf{C}_{F,Y_{2}}((\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{5},q_{6}))$
$\displaystyle=({a^{+}b}\triangleright{\varepsilon})\,.$

Next, we compute some steps using the unambiguous concatenation $G=F\cdot F$.
We start with step $(\rightarrow,q_{0},q_{2})$ for which the zigzag part is
empty:
$\mathsf{ZC}_{F,Y_{2}}^{F,Y_{2}}(q_{1},\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}})={F^{2}}\triangleright{\varepsilon}$.
Hence, we get using the formula in the proof above

$\displaystyle\mathsf{C}_{G,Y_{4}}((\rightarrow,q_{0},q_{2}))$
$\displaystyle=\big{(}\mathsf{C}_{F,Y_{2}}((\rightarrow,q_{0},q_{1}))\cdot({F}\triangleright{\varepsilon})\big{)}\odot({F^{2}}\triangleright{\varepsilon})\odot\big{(}({F}\triangleright{\varepsilon})\cdot\mathsf{C}_{F,Y_{2}}((\rightarrow,q_{1},q_{2}))\big{)}$
and after some simplifications
$\displaystyle\mathsf{C}_{G,Y_{4}}((\rightarrow,q_{0},q_{2}))$
$\displaystyle=\mathsf{C}_{F,Y_{2}}((\rightarrow,q_{0},q_{1}))\cdot\mathsf{C}_{F,Y_{2}}((\rightarrow,q_{1},q_{2}))=({(a^{+}b)^{2}}\triangleright{\varepsilon})\,.$

Similarly, we can compute the following steps

$\displaystyle\mathsf{C}_{G,Y_{4}}((\rightarrow,q_{6},q_{1}))$
$\displaystyle=\mathsf{C}_{F,Y_{2}}((\rightarrow,q_{6},q_{0}))\cdot\mathsf{C}_{F,Y_{2}}((\rightarrow,q_{0},q_{1}))=({a}\triangleright{a})^{+}\cdot({b}\triangleright{b})\cdot({a^{+}b}\triangleright{\varepsilon})\,.$

For step
$(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{2},q_{3})$,
the run only visits the first factor since
$(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{2},q_{3})\in
Y_{2}$:

$\displaystyle\mathsf{C}_{G,Y_{4}}((\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{2},q_{3}))$
$\displaystyle=\mathsf{C}_{F,Y_{2}}((\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{2},q_{3}))\cdot({F}\triangleright{\varepsilon})=({a}\triangleright{a})^{+}\cdot({b}\triangleright{b})\cdot({a^{+}b}\triangleright{\varepsilon})\,.$

Now, for step
$(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{1},q_{4})$,
the zigzag part is reduced to step
$(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{2},q_{3})$
and we get:

$\displaystyle\mathsf{C}_{G,Y_{4}}((\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{1},q_{4}))$
$\displaystyle=\big{(}\mathsf{C}_{F,Y_{2}}((\rightarrow,q_{1},q_{2}))\cdot({F}\triangleright{\varepsilon})\big{)}\odot\big{(}({F}\triangleright{\varepsilon})\cdot\mathsf{C}_{F,Y_{2}}((\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{2},q_{3}))\big{)}$
$\displaystyle\hskip
56.9055pt{}\odot\big{(}\mathsf{C}_{F,Y_{2}}((\leftarrow,q_{3},q_{4}))\cdot({F}\triangleright{\varepsilon})\big{)}$
$\displaystyle=({a^{+}b}\triangleright{\varepsilon})\cdot({a}\triangleright{a})^{+}\cdot({b}\triangleright{b})\,.$

Similarly, we compute

$\displaystyle\mathsf{C}_{G,Y_{4}}((\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{4},q_{0}))$
$\displaystyle=\big{(}({F}\triangleright{\varepsilon})\cdot\mathsf{C}_{F,Y_{2}}((\leftarrow,q_{4},q_{5}))\big{)}\odot\big{(}\mathsf{C}_{F,Y_{2}}((\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{5},q_{6}))\cdot({F}\triangleright{\varepsilon})\big{)}$
$\displaystyle\hskip
56.9055pt{}\odot\big{(}({F}\triangleright{\varepsilon})\cdot\mathsf{C}_{F,Y_{2}}((\rightarrow,q_{6},q_{0}))\big{)}$
$\displaystyle=({a^{+}b}\triangleright{\varepsilon})\cdot({a}\triangleright{a})^{+}\cdot({b}\triangleright{b})\,.$

Figure 9: Illustration for Example 5.18.

Finally, we consider the unambiguous decomposition $E=G\cdot G$ in order to
compute $\mathsf{C}_{E,Z_{2}}(x)$ where $x=(\rightarrow,q_{6},q_{2})$. Notice
that
$(\rightarrow,q_{6},q_{1}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{1},q_{4}),(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{4},q_{0}),(\rightarrow,q_{0},q_{2})\in
Y_{4}=\varphi(G)$. Hence,
$Z_{Y_{4},Y_{4}}(q_{1},\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}})=(\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{0})$
and applying the formulas in the proof above we obtain

$\displaystyle\mathsf{C}_{E,Z_{2}}(x)$
$\displaystyle=\big{(}\mathsf{C}_{G,Y_{4}}((\rightarrow,q_{6},q_{1}))\cdot({G}\triangleright{\varepsilon})\big{)}\odot\mathsf{ZC}_{G,Y_{4}}^{G,Y_{4}}(q_{1},\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}})\odot\big{(}({G}\triangleright{\varepsilon})\cdot\mathsf{C}_{G,Y_{4}}((\rightarrow,q_{0},q_{2}))\big{)}$
$\displaystyle\mathsf{ZC}_{G,Y_{4}}^{G,Y_{4}}(q_{1},\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}})$
$\displaystyle=\big{(}({G}\triangleright{\varepsilon})\cdot\mathsf{C}_{G,Y_{4}}((\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},q_{1},q_{4}))\big{)}\odot\big{(}\mathsf{C}_{G,Y_{4}}((\mathrel{\leavevmode{\rotatebox[origin={c}]{90.0}{$\curvearrowleft$}}},q_{4},q_{0}))\cdot({G}\triangleright{\varepsilon})\big{)}\,.$

Putting everything together and still after some simplifications, we get

$\displaystyle\mathsf{C}_{E,Z_{2}}(x)$
$\displaystyle=\big{(}({a}\triangleright{a})^{+}\cdot({b}\triangleright{b})\cdot({(a^{+}b)^{3}}\triangleright{\varepsilon})\big{)}\odot\big{(}({(a^{+}b)^{3}}\triangleright{\varepsilon})\cdot({a}\triangleright{a})^{+}\cdot({b}\triangleright{b})\big{)}$
$\displaystyle\hskip
56.9055pt{}\odot\big{(}({a^{+}b}\triangleright{\varepsilon})\cdot({a}\triangleright{a})^{+}\cdot({b}\triangleright{b})\cdot({(a^{+}b)^{2}}\triangleright{\varepsilon})\big{)}\,.$

For instance, applying $\mathsf{C}_{E,Z_{2}}(x)$ to $w=aba^{2}ba^{3}ba^{4}b$
we obtain $aba^{4}ba^{2}b$.

##### SD-Kleene Star

The most interesting case is when $E=F^{*}$. Let
$L=\mathcal{L}(F)\subseteq\Sigma^{*}$. Since $E$ is a stabilising SD-regular
expression, $L$ is an aperiodic prefix code of bounded synchronisation delay,
and $X=\varphi(L)$ is $k$-stabilising for some $k>0$. Hence, we may apply the
results of Section 5.2.1.

By induction, we suppose that we have SDRTEs $\mathsf{C}_{F,s}(x)$ for all $s$
in $\mathsf{TrM}$ and steps $x$. Since $L=\mathcal{L}(F)$ is a code, for each
fixed $\ell>0$, the expression $F^{\ell}=F\cdot F\cdots F$ is an unambiguous
concatenation. Hence, from the proof above for the unambiguous concatenation,
we may also assume that we have SDRTEs $\mathsf{C}_{F^{\ell},s}(x)$ for all
$s\in\mathsf{TrM}$ and steps $x$. Similarly, we have SDRTEs for
$\mathsf{ZC}_{F^{k},s}^{F,t}(-)$ and $\mathsf{ZC}_{F,s}^{F^{k},t}(-)$. Notice
that $F^{0}$ is equivalent to $\varepsilon$ hence we have
$\mathsf{C}_{F^{0},s}(x)=\mathsf{C}_{\varepsilon,s}(x)$.

We show how to construct SDRTEs $\mathsf{C}_{E,s}(x)$ for $E=F^{*}$. There are
four cases, which are dealt with below, depending on the step $x$.

We fix some notation common to all four cases. Fix some
$w\in\mathcal{L}(E,s)=L^{*}\cap\varphi^{-1}(s)$ and let $w=u_{1}\cdots u_{n}$
be the unique factorization of $w$ with $n\geq 0$ and $u_{i}\in L$ for $1\leq
i\leq n$. For a step $x\in s$, we denote by $\rho$ the unique run of
$\mathcal{A}$ over $w$ following step $x$.

  * •

$x=(\mathrel{\leavevmode{\rotatebox[origin={c}]{-90.0}{$\curvearrowright$}}},p,q)\in
s$

The easiest case is for left-left steps. If $n<k$ then the output of $\rho$ is
$[\\![\mathsf{C}_{F^{n},s}(x)]\\!](w)$. Notice that here,
$\mathsf{C}_{F^{0},s}(x)=\bot$ since $x\notin\mathbf{1}=\varphi(\varepsilon)$.
Now, if $n\geq k$ then, by Lemma 5.5, the run $\rho$ stays inside $u_{1}\cdots
u_{k}$. We deduce that the output of $\rho$ is
$[\\![\mathsf{C}_{F^{k},s}(x)]\\!](u_{1}\cdots u_{k})$. Therefore, we define

$\displaystyle\mathsf{C}_{E,s}(x)$