Intuitively, the regular transductions above simulate the steps used in the standard ODD minimization algorithm. By using Proposition 5.(2), we have that the transduction \(\mathfrak {can}[{\Sigma },{w}]\) is \(2^{O(|{\Sigma }|\cdot {w} \cdot 2^{{w}})}\)-regular. The fact that each of the five transductions above is functional implies that \(\mathfrak {can}[{\Sigma },{w}]\) is also functional. Additionally, it is straightforward to note that \(\mathsf {Dom}(\widehat {\mathfrak {can}}[{\Sigma },{w}]) = {{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circledast }}\). Finally, a pair of ODDs \(({{D}},{{D}}^{\prime })\) belongs to \(\widehat {\mathfrak {can}}[{\Sigma },{w}]\) if and only if \({{D}}^{\prime }\) is deterministic, complete, minimized, normalized and \({{\mathscr{L}}({{D}})} = {{\mathscr{L}}({{D}}^{\prime })}\). In other words, if and only if \({{D}}^{\prime }\) is the canonical form \(\mathcal {C}({{D}})\) of Theorem 4.
6.2 Determinization Transduction
In this subsection, we define the determinization transduction \(\mathfrak {det}[{\Sigma },{w}]\), which intuitively simulates the application of the well known power-set construction to the layers of a (Σ,w)-ODD.
For each \({w}\in {{\mathbb {N}}_+}\), we let \({\Omega } \colon {\mathcal {P}(\llbracket {{w}}\rrbracket ))} \rightarrow \llbracket {2^{{w}}}\rrbracket \) be the bijection that sends each subset \({X} \subseteq \llbracket {{w}}\rrbracket \) to the natural number \({\Omega }({X}) \doteq {\sum }_{i \in {X}} 2^{i}\). In particular, we remark that Ω(∅) = 0 and Ω({i}) = 2i for each i ∈ X.
Let Σ be an alphabet,
\({w}\in {{\mathbb {N}}_+}\),
\({B}\in {{\mathscr{B}}({\Sigma }, {w})}\),
\({X} \subseteq {\ell }({B})\) and
\({\Sigma }^{\prime } \subseteq {\Sigma }\). We let
\(\mathrm {\textbf {N}}({B},{X}, {\Sigma }^{\prime })\) be the set of all right states of
B that are reachable from some left state in
X by reading some symbol in
\({\Sigma }^{\prime }\). More formally,
$$\mathrm{\textbf{N}}({B},{X}, {\Sigma}^{\prime})\doteq\lbrace{{\mathfrak{q}} \in {r}({B}) \colon\exists {\mathfrak{p}}\in {X}, \exists {\sigma} \in {\Sigma}^{\prime},({{\mathfrak{p}},{\sigma},{\mathfrak{q}}}) \in {T}({B})}\rbrace\text{.}$$
For each alphabet Σ and each
\({w}\in {{\mathbb {N}}_+}\), we let
\({\mathsf {pw}}[{\Sigma },{w}]\colon {{\mathscr{B}}({\Sigma }, {w})}\rightarrow {\widehat {{\mathscr{B}}}({\Sigma }, 2^{{w}})}\) be the map that sends each layer
\({B} \in {{\mathscr{B}}({\Sigma }, {w})}\) to the deterministic, complete layer
\({\mathsf {pw}}({B})\in {\widehat {{\mathscr{B}}}({\Sigma }, 2^{{w}})}\) defined as follows:
-
\({\ell }({{\mathsf {pw}}({B})}) \doteq \begin {cases} \lbrace {{\Omega }({I}({B}))}\rbrace & \text { if } {\iota }({B}) = 1\\ \lbrace {{\Omega }({X}) \colon {X} \subseteq {\ell }({B})}\rbrace & \text { otherwise;} \end {cases}\)
-
\({r}({{\mathsf {pw}}({B})}) \doteq \lbrace {{\Omega }({X}) \colon {X} \subseteq {r}({B})}\rbrace \);
-
\({T}({{\mathsf {pw}}({B})}) \doteq \begin {cases} \{({{\Omega }({I}({B})), {\sigma }, {\Omega }(\mathrm {\textbf {N}}({B},{I}({B}), \lbrace {{\sigma }}\rbrace ))}, {\sigma } \in {\Sigma }\} & \text { if } {\iota }({B}) = 1 \\ \{({\Omega }({X}), {\sigma }, {\Omega } (\mathrm {\textbf {N}}({B},{X}, \lbrace {{\sigma }}\rbrace ) \colon {X} \subseteq {\ell }({B}), {\sigma }\in {\Sigma }\} & \text { otherwise; } \end {cases}\)
-
\({I}({{\mathsf {pw}}({B})}) \doteq \begin {cases} \lbrace {{\Omega }({I}({B}))}\rbrace & \text {if } {\iota }({B}) = 1\\ \emptyset & \text {otherwise;} \end {cases}\)
-
\({F}({{\mathsf {pw}}({B})}) \doteq \lbrace {{\Omega }({X}) \colon {X} \subseteq {r}({B}), {X} \cap {F}({B}) \neq \emptyset }\rbrace \);
-
\({\iota }({{\mathsf {pw}}({B})}) \doteq {\iota }({B})\);
-
\({\phi }({{\mathsf {pw}}({B})}) \doteq {\phi }({B})\).
Let Σ be an alphabet, \({w}\in {{\mathbb {N}}_+}\), and let \({B} \in {{\mathscr{B}}({\Sigma }, {w})}\). Since Ω is a bijection, there exists precisely one right state \({\mathfrak {q}} \in {r}({{\mathsf {pw}}({B})})\), namely \({\mathfrak {q}}={\Omega } (\mathrm {\textbf {N}}({B},{X}, \lbrace {{\sigma }}\rbrace ))\), such that \(({{\Omega }({X}), {\sigma }, {\mathfrak {q}}}) \in {T}({{\mathsf {pw}}({B})})\) for each subset \({X} \subseteq \llbracket {{w}}\rrbracket \) with Ω(X) ∈ ℓ(pw(B)) and each symbol σ ∈Σ. Furthermore, note that ι(pw(B)) = 1 implies ι(B) = 1. Thus, if ι(pw(B)) = 1, then I(pw(B)) = ℓ(pw(B)) = {Ω(I(B))}. As a result, pw(B) is indeed a deterministic, complete layer in \({\widehat {{\mathscr{B}}}({\Sigma }, 2^{{w}})}\).
Now, for each alphabet Σ and each positive integer \({w}\in {{\mathbb {N}}_+}\), we define the \(({{\mathscr{B}}({\Sigma }, {w})},{\widehat {{\mathscr{B}}}({\Sigma }, {w})})\)-transduction \(\mathfrak {det}[{\Sigma },{w}] \doteq \mathfrak {mm}[{\mathsf {pw}}[{\Sigma },{w}]]\). The next lemma states that \(\mathfrak {det}[{\Sigma },{w}]\) sends each ODD \({{D}}\in {{{\mathscr{B}}({\Sigma }, {w})}^{\protect \circledast }}\) to a deterministic, complete ODD \(D^{\prime }\in \widehat {{\mathscr{B}}}({\Sigma },{w})^{\protect \circledast }\) that has the same language as D.
Proof
First, we note that \(\mathsf {Dom}(\mathfrak {det}[{\Sigma },{w}]) = {{\mathscr{B}}({\Sigma }, {w})}^{+}\). This follows from the fact that pw is a map from the alphabet \({{\mathscr{B}}({\Sigma }, {w})}\) to the alphabet \({\widehat {{\mathscr{B}}}({\Sigma }, 2^{{w}})}\). Thus, for each \({k}\in {{\mathbb {N}}_+}\) and each string \({{D}}={B}_{1}\cdots {B}_{{k}}\in {{\mathscr{B}}({\Sigma }, {w})}^{{k}}\), there exists exactly one string \({{D}^{\prime }}\) over \({\widehat {{\mathscr{B}}}({\Sigma }, 2^{{w}})}\) such that \(({{{D}},{{D}^{\prime }}})\in \mathfrak {det}[{\Sigma },{w}]\), namely the string \({{D}^{\prime }}={{\mathsf {pw}}({{D}})}={{\mathsf {pw}}({B}_{1})}\cdots {{\mathsf {pw}}({B}_{{k}})}\). Consequently, \(\mathsf {Dom}(\mathfrak {det}[{\Sigma },{w}]) \supseteq {{{\mathscr{B}}({\Sigma }, {w})}^{\protect \circledast }}\). Moreover, by the uniqueness of the string \({{D}^{\prime }}={{\mathsf {pw}}({{D}})}\) with \(({{{D}},{{D}^{\prime }}})\in \mathfrak {det}[{\Sigma },{w}]\) for each \({{D}}\in {{\mathscr{B}}({\Sigma }, {w})}^{+}\), we obtain that \(\mathfrak {det}[{\Sigma },{w}]\) is a functional transduction.
Now, let \({{D}} = {B}_{1}\cdots {B}_{{k}}\in {{{\mathscr{B}}({\Sigma }, {w})}^{\protect \circ {{k}}}}\) for some \({k} \in {{\mathbb {N}}_+}\). Since Ω is a bijection, for each i ∈ [k − 1], ℓ(pw(Bi+ 1)) = r(pw(Bi)) if and only if ℓ(Bi+ 1) = r(Bi). Furthermore, ι(pw(Bi)) = ι(Bi) and ϕ(pw(Bi)) = ϕ(Bi) for each i ∈ [k]. Thus, owing to fact that \({{D}}\in {{{\mathscr{B}}({\Sigma }, {w})}^{\protect \circ {{k}}}}\), \({{\mathsf {pw}}({{D}})}={{\mathsf {pw}}({B}_{1})}\cdots {{\mathsf {pw}}({B}_{{k}})}\in {{{\mathscr{B}}({\Sigma }, 2^{{w}})}^{\protect \circ {{k}}}}\). More specifically, pw(D) is a deterministic, complete ODD in \({{\widehat {{\mathscr{B}}}({\Sigma }, 2^{{w}})}^{\protect \circ {{k}}}}\). Indeed, this follows from the fact that pw(Bi) is a deterministic, complete (Σ,w)-layer for each i ∈ [k]. Thus, it just remains to prove that \({{\mathscr{L}}({{\mathsf {pw}}({{D}})})} = {{\mathscr{L}}({{D}})}\). Let s = σ1⋯σk be a string in Σk.
First, suppose that
\({s} \in {{\mathscr{L}}({{D}})}\). Then, there exists an accepting sequence
$$ \langle{({{\mathfrak{p}}_{1}, {\sigma}_{1}, {\mathfrak{q}}_{1}}), \ldots, ({{\mathfrak{p}}_{{k}}, {\sigma}_{{k}}, {\mathfrak{q}}_{{k}}})}\rangle $$
for
s in
D. Let
X0 =
I(
B1) and, for each
i ∈
⟦k⟧, let
Xi+ 1 =
N(
Bi+ 1Xi{
σi+ 1}). Note that
\(X_{i} \subseteq \ell (B_{i+1})\) for each
i ∈
⟦k⟧. Furthermore, for each
i ∈ [
k], we have that
\(\mathfrak {q}_{i} \in X_{i}\), i.e.
\(\mathfrak {q}_{i} \in \mathrm {\textbf {N}}({B_{i}}{X_{i-1}}{\lbrace {\sigma _{i}}\rbrace })\), otherwise
\(({\mathfrak {p}_{i}, \sigma _{i}, \mathfrak {q}_{i}}) \not \in T(B_{i})\). Therefore,
$$ \langle{({{\Omega}({X}_{0}), {\sigma}_{1}, {\Omega}({X}_{1})}), \ldots, ({{\Omega}({X}_{{k}-1}), {\sigma}_{{k}}, {\Omega}({X}_{{k}})})}\rangle $$
is an accepting sequence for
s in
pw(
D), and we obtain that
\(s \in {\mathscr{L}}({{\mathsf {pw}(D)}})\).
Conversely, suppose that
\({s} \in {{\mathscr{L}}({{\mathsf {pw}}({{D}})})}\). Then, there exists an accepting sequence
$$\langle{({{\Omega}({X}_{0}), {\sigma}_{1}, {\Omega}({X}_{1})}), \ldots,({{\Omega}({X}_{{k}-1}), {\sigma}_{{k}}, {\Omega}({X}_{{k}})})}\rangle$$
for
s in
pw(
D), where
X0 =
I(
B1) and
Xi+ 1 =
N(
Bi+ 1,
Xi,{
σi+ 1}) for each
i ∈
⟦k⟧. Thus, let
\({\mathfrak {p}}_{{k}} \in {X}_{{k}-1}\) and
\({\mathfrak {q}}_{{k}} \in {X}_{{k}}\) such that
\(({{\mathfrak {p}}_{{k}}, {\sigma }_{{k}}, {\mathfrak {q}}_{{k}}}) \in {T}({B}_{{k}})\). Moreover, for each
i ∈ [
k − 1], let
\({\mathfrak {p}}_{i} \in {X}_{i-1}\) and
\({\mathfrak {q}}_{i} \in {X}_{i}\) such that
\({\mathfrak {q}}_{i} = {\mathfrak {p}}_{i+1}\) and
\(({{\mathfrak {p}}_{i}, {\sigma }_{i}, {\mathfrak {q}}_{i}}) \in {T}({B}_{i})\). We note that for each
i ∈
⟦k⟧, there exist left states and right states
\({\mathfrak {p}}_{i+1}\) and
\({\mathfrak {q}}_{i+1}\) as described above, otherwise (Ω(
Xi),
σi+ 1,Ω(
Xi+ 1)) would not be a transition in
T(
pw(
Bi+ 1)). Therefore,
$$ \langle{({{\mathfrak{p}}_{1}, {\sigma}_{1}, {\mathfrak{q}}_{1}}), \ldots, ({{\mathfrak{p}}_{{k}}, {\sigma}_{{k}}, {\mathfrak{q}}_{{k}}})}\rangle $$
is an accepting sequence for
s in
D, and
\(s \in {\mathscr{L}}({D})\). Finally, the fact that
\(\mathfrak {det}[{\Sigma },{w}]\) is 2-regular follows from the fact that
\(\mathfrak {det}[{\Sigma },{w}] \doteq \mathfrak {mm}[{\mathsf {pw}}[{\Sigma },{w}]]\) is an instantiation of a multimap transduction and that multimap transductions are 2-regular (Proposition 25.(1)). □
6.3 Reachability Transduction
In this subsection, we define the reachability transduction, which intuitively simulates the process of eliminating unreachable states from the frontiers of each layer of an ODD. It is worth noting that unlike the determinization transduction, that can be defined using a map that acts layerwisely, the reachability transduction will require the use of a compatibility transduction. The issue is that reachability of a given state q in a given B belonging to a given ODD D is a property that depends on which layers have been read before B. To circumvent this issue, the action of the reachability transduction on a ODD D can be described in three intuitive steps. First, we use a multimap transduction to expand each layer of the ODD into a set of annotated layers. Each annotation splits states of a layer into two classes: those that are deemed to be useful, and those that should be deleted. Subsequently, we use a compatibility transduction to ensure that only sequences of annotated layers with compatible annotations are considered to be legal. The crucial observation is that each ODD D has a unique annotated version where each two adjacent annotated layers are compatible with each other. Finally, we apply a mapping that sends each annotated layer to the layer obtained by deleting the states that have been marked for deletion. The resulting ODD is then the unique ODD obtained from D by eliminating unreachable states.
Let Σ be an alphabet,
\({w} \in {{\mathbb {N}}_+}\) and
\({B}\in {\widehat {{\mathscr{B}}}({\Sigma }, {w})}\). A
reachability annotation for
B is a pair (
𝜗,
η) of functions
\(\vartheta \colon {\ell }({B})\rightarrow \lbrace {0,1}\rbrace \) and
\(\eta \colon {r}({B})\rightarrow \lbrace {0,1}\rbrace \) that satisfies the following conditions:
1.
if ι(B) = 1, then, for each left state \({\mathfrak {p}}\in {\ell }({B})\), \(\vartheta _{}({\mathfrak {p}})=1\) if and only if \(\mathfrak {p}\in I(B)\);
2.
for each right state \({\mathfrak {q}}\in {r}({B})\), \(\eta _{}({\mathfrak {q}})=1\) if and only if there exists \({\mathfrak {p}}\in {\ell }(B)\) and σ ∈Σ such that \(\vartheta ({\mathfrak {p}})=1\) and \(({\mathfrak {p},\sigma ,\mathfrak {q}})\in T(B)\).
Let Σ be an alphabet,
\({w},{k}\in {{\mathbb {N}}_+}\), and let
\({{D}} = {B}_{1}\cdots {B}_{{k}}\in {{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circ {{k}}}}\). A
reachability annotation for
D is a sequence 〈(
𝜗1,
η1),…,(
𝜗k,
ηk)〉 that satisfies the following conditions:
1.
for each i ∈ [k], (𝜗i,ηi) is a reachability annotation for Bi;
2.
for each i ∈ [k − 1], ηi = 𝜗i+ 1.
Let Σ be an alphabet and
\({w}\in {{\mathbb {N}}_+}\). We denote by
\(\mathcal {R}({\Sigma },{w})\) the set consisting of all triples (
B,
𝜗,
η) such that
B is a layer in
\({\widehat {{\mathscr{B}}}({\Sigma }, {w})}\) and (
𝜗,
η) is a reachability annotation for
B. Additionally, we denote by
\(\xi [{\Sigma },{w}]\colon \mathcal {R}({\Sigma },{w})\rightarrow {\widehat {{\mathscr{B}}}({\Sigma }, {w})}\) the map that sends each triple
\(({{B},\vartheta ,\eta })\in \mathcal {R}({\Sigma },{w})\) to the layer
\(\xi [{\Sigma },{w}]({B},\vartheta ,\eta )\in {\widehat {{\mathscr{B}}}({\Sigma }, {w})}\) obtained from
B by removing the left states
\({\mathfrak {p}}\in {\ell }({B})\) with
\(\vartheta _{}({\mathfrak {p}})=0\), the right states
\({\mathfrak {q}}\in {r}({B})\) with
\(\eta _{}({\mathfrak {q}})=0\), and the transitions incident with such left and right states. More formally, for each triple
\(({{B},\vartheta ,\eta })\in \mathcal {R}({\Sigma },{w})\), we let
\(\xi [{\Sigma },{w}]({B},\vartheta ,\eta ) = {{B}^{\prime }}\), where
\({{B}^{\prime }}\) is the layer belonging to
\({\widehat {{\mathscr{B}}}({\Sigma }, {w})}\) defined as follows:
-
\({\ell }({{B}^{\prime }}) \doteq {\ell }({B})\setminus \lbrace {{\mathfrak {p}} \colon \vartheta _{}({\mathfrak {p}})=0}\rbrace \);
-
\({r}({{B}^{\prime }}) \doteq {r}({B})\setminus \lbrace {{\mathfrak {q}} \colon \eta _{}({\mathfrak {q}})=0}\rbrace \);
-
\({T}({{B}^{\prime }}) \doteq {T}({B})\setminus \lbrace {({{\mathfrak {p}},{\sigma },{\mathfrak {q}}}) \colon \vartheta _{}({\mathfrak {p}})=0}\rbrace \);
-
\({\iota }({{B}^{\prime }}) \doteq {\iota }({B})\); \({\phi }({{B}^{\prime }}) \doteq {\phi }({B})\);
-
\({I}({{B}^{\prime }}) \doteq {I}({B})\); \({F}({{B}^{\prime }}) \doteq {r}({{B}^{\prime }}) \cap {F}({B})\).
We let
\( {\xi }[{\Sigma },{w}]\colon {{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circledast }}\rightarrow {{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circledast }}\) be the map that for each
\({k}\in {{\mathbb {N}}_+}\), sends each ODD
\({D} = {B}_{1}\cdots {B}_{{k}}\in {{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circ {{k}}}}\) to the ODD
$$ {\xi}[{\Sigma},{w}]({D}) \doteq \xi[{\Sigma},{w}]({B}_{1},\vartheta_{1},\eta_{1})\cdots\xi[{\Sigma},{w}]({B}_{{k}},\vartheta_{{k}},\eta_{{k}})\in{{\widehat{\mathcal{B}}({\Sigma}, {w})}^{\protect\circ{{k}}}}\text{,} $$
where 〈(
𝜗1,
η1),…,(
𝜗k,
ηk)〉 denotes the unique reachability annotation for
D (see Proposition 28).
For each alphabet Σ and each positive integer
\({w}\in {{\mathbb {N}}_+}\), we let
\(\text {RR}[{\Sigma },{w}] \subseteq {\widehat {{\mathscr{B}}}({\Sigma }, {w})} \times \mathcal {R}({\Sigma },{w})\) and
\(\text {RC}[{\Sigma },{w}] \subseteq \mathcal {R}({\Sigma },{w})\times \mathcal {R}({\Sigma },{w})\) be the relations defined as follows.
$$ \text{RR}[{\Sigma},{w}] \doteq \lbrace{({{B}, ({B},\vartheta,\eta)}) \colon ({B,\vartheta,\eta})\in\mathcal{R}({\Sigma},{w})}\rbrace. $$
$$ \begin{array}{@{}rcl@{}} \text{RC}[{\Sigma},{w}] &\doteq& \{ ({({B},\vartheta,\eta), ({B}^{\prime},\vartheta^{\prime},\eta^{\prime})}) \colon ({{B},\vartheta,\eta}), ({{B}^{\prime},\vartheta^{\prime},\eta^{\prime}}) \in \mathcal{R}({\Sigma},{w}), {r}({B}) \\&=& {\ell}({B}^{\prime}), \eta = \vartheta^{\prime}\}\text{.} \end{array} $$
Now, for each alphabet Σ and each positive integer
\({w} \in {{\mathbb {N}}_+}\), we define
\(\mathfrak {rea}[{\Sigma },{w}]\) as the
\((\widehat {{\mathscr{B}}}({\Sigma },{w}),\widehat {{\mathscr{B}}}({\Sigma },{w}))\)-transduction
$$ \mathfrak{rea}[{\Sigma},{w}] \doteq \mathfrak{mm}[\text{RR}[{\Sigma},{w}]]\circ\mathfrak{cp}[\text{RC}[{\Sigma},{w}]] \circ \mathfrak{mm}[\xi[{{\Sigma}}{{w}}]]. $$
The next lemma states that
\(\mathfrak {rea}[{\Sigma },{w}]\) is a transduction that sends each ODD
\({{D}}\in {{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circledast }}\) to a
reachable ODD
\(D^{\prime }\in \widehat {{\mathscr{B}}}({\Sigma },{w})^{\protect \circledast }\) that has the same language as
D, and that preserves the determinism and completeness properties.
Proof
We note that \(\mathfrak {rea}[{\Sigma },{w}]\) consists of all pairs \(({{{D}},{{D}^{\prime }}})\) of non-empty strings over the alphabet \({\widehat {{\mathscr{B}}}({\Sigma }, {w})}\) satisfying the conditions that \(\lvert {{{D}}}\rvert =\lvert {{{D}^{\prime }}}\rvert \) and that, if D = B1⋯Bk and \({D^{\prime }}={B^{\prime }}_{1}\cdots {B^{\prime }}_{{k}}\) for some \({k}\in {{\mathbb {N}}_+}\), then there exists a reachability annotation (𝜗i,ηi) for the layer Bi such that \({{B}^{\prime }}_{i}=\xi [{\Sigma },{w}]({B}_{i},\vartheta _{i},\eta _{i})\) for each i ∈ [k], and r(Bj) = ℓ(Bj+ 1) and ηj = 𝜗j+ 1 for each j ∈ [k − 1]. Additionally, based on Proposition 28, each (Σ,w)-ODD admits a unique reachability annotation. As a result, we obtain that \(\mathsf {Dom}(\mathfrak {rea}[{\Sigma },{w}]) \supseteq {{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circledast }}\). Moreover, \({{D}^{\prime }} = {\xi }[{\Sigma },{w}]({{D}})\); thus, by the uniqueness of ξ[Σ,w](D), the transduction \(\mathfrak {rea}[{\Sigma },{w}]\) is functional. Finally, it follows from Proposition 29 that for each pair \(({{{D}},{{D}^{\prime }}})\in \mathfrak {rea}[{\Sigma },{w}]\), \({{D}^{\prime }} = {\xi }[{\Sigma },{w}]({{D}})\) is a reachable ODD in \({{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circledast }}\) that has the same language as D.
The fact that \(\mathfrak {rea}[{\Sigma },{w}]\) is \(2^{O(|{\Sigma }|\cdot {w} \cdot \log {w})}\)-regular follows from Proposition 5.(2) together with the fact that the multimap transductions \(\mathfrak {mm}[\text {RR}[{\Sigma },{w}]]\) and \(\mathfrak {mm}[\xi [{\Sigma },\) w]] are 2-regular (Proposition 25.(1)), and that the transduction \(\mathfrak {cp}[\text {RC}[{\Sigma },{w}]]\) is \(2^{O(|{\Sigma }|\cdot {w} \cdot \log {w})}\)-regular (Proposition 25.(2)), given that \(\text {RC}[{\Sigma },{w}]\subseteq \mathcal {R}({\Sigma },{w})\times \mathcal {R}({\Sigma },{w})\) and that \(|\mathcal {R}({\Sigma },{w})| = 2^{O(|{\Sigma }|\cdot {w}\cdot \log {w})}\). □
6.4 Merging Transduction
In this subsection, we define the merging transduction, which intuitively simulates the process of merging equivalent states in the frontiers of each layer of an ODD D. As in the case of the reachability transduction, the merging transduction will be defined as the composition of three elementary transductions. First, we use a multimap transduction to expand each layer of the ODD into a set of annotated layers. Each annotation partitions each frontier of the layer into cells containing states that are deemed to be equivalent. Subsequently, we use a compatibility transduction to ensure that only sequences of annotated layers with compatible annotations are considered to be legal. As in the case of the reachability transduction, it is possible to show that each ODD D has a unique annotated version where each two adjacent annotated layers are compatible with each other. Finally, we apply a mapping that sends each annotated layer to the layer obtained by merging all states in each cell of each partition to the smallest state in the cell. The result is a minimized ODD with same language as D.
Let Σ be an alphabet, \({w} \in {{\mathbb {N}}_+}\), \({B}\in {\widehat {{\mathscr{B}}}({\Sigma }, {w})}\) and ν be a partition of r(B). Two (not necessarily distinct) left states \({\mathfrak {p}},{\mathfrak {p}}^{\prime }\in {\ell }({B})\) are said to be ν-equivalent if, for each symbol σ ∈Σ, there exists a right state \({\mathfrak {q}}\in r({B})\) such that \(({{\mathfrak {p}},{\sigma },{\mathfrak {q}}})\) is a transition in T(B) if and only if there exists a right state \({\mathfrak {q}}^{\prime }\in {r}({B})\) such that \(({{\mathfrak {p}}^{\prime },{\sigma },{\mathfrak {q}}^{\prime }})\) is a transition in T(B), and \({\mathfrak {q}}\) and \({\mathfrak {q}}^{\prime }\) belong to the same cell of ν. We remark that each left state \({\mathfrak {p}}\) is trivially ν-equivalent to itself.
A
merging annotation for
B is a pair (
μ,
ν), where
μ is a partition of
ℓ(
B) and
ν is a partition of
r(
B), that satisfies the following two conditions:
1.
if ϕ(B) = 1, then ν = {r(B) ∖ F(B),F(B)} whenever r(B) ∖ F(B)≠∅ and F(B)≠∅, and ν = {r(B)} whenever r(B) ∖ F(B) = ∅ or F(B) = ∅;
2.
for each two left states \({\mathfrak {p}},{\mathfrak {p}}^{\prime }\in {\ell }({B})\), \({\mathfrak {p}}\) and \({\mathfrak {p}}^{\prime }\) belong to the same cell of μ if and only if \(\mathfrak {p}\) and \(\mathfrak {p}^{\prime }\) are ν-equivalent.
Let Σ be an alphabet,
\({w},{k}\in {{\mathbb {N}}_+}\), and let
\({{D}} = {B}_{1}\cdots {B}_{{k}}\in {{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circ {{k}}}}\). A
merging annotation for
D is a sequence 〈(
μ1,
ν1)⋯(
μk,
νk)〉 that satisfies the following conditions:
1.
for each i ∈ [k], (μi,νi) is a merging annotation for Bi;
2.
for each i ∈ [k − 1], νi = μi+ 1.
Let Σ be an alphabet,
\({w},{k}\in {{\mathbb {N}}_+}\) and
\({D}={B}_{1}\cdots {B}_{{k}}\in {{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circ {{k}}}}\). For each
i ∈ [
k], we say that a string
s =
σ1…
σk is
accepted by D from a left state \({\mathfrak {p}}\in {\ell }({B}_{i})\) if there exists a sequence
\(\langle {({{\mathfrak {p}}_{i},{\sigma }_{i},{\mathfrak {q}}_{i}}),\ldots ,({{\mathfrak {p}}_{{k}},{\sigma }_{{k}},{\mathfrak {q}}_{{k}}})}\rangle \) of transitions such that
\({\mathfrak {p}}_{i}={\mathfrak {p}}\),
\({\mathfrak {q}}_{{k}}\in {F}({B}_{{k}})\) and, for each
j ∈{
i,…,
k},
\(({{\mathfrak {p}}_{j},{\sigma }_{j},{\mathfrak {q}}_{j}})\in {T}({B}_{j})\). For each
i ∈ [
k] and each left state
\({\mathfrak {p}}\in {\ell }({B}_{i})\), we let
$$ {\mathcal{L}({D},i,{\mathfrak{p}})}\doteq \lbrace{{s}\in{\Sigma}^{{k}-i+1}\colon {s} \text{ is accepted by } {D} \text{ from } {\mathfrak{p}}}\rbrace\text{.} $$
Proof
The proof is by induction on k − i. Base case. Consider k − i = 0. Then i = k. By definition, two left states \({\mathfrak {p}},{\mathfrak {p}}^{\prime }\in {\ell }({B}_{{k}})\) belong to the same cell of μk if and only if \({\mathfrak {p}}\) and \({\mathfrak {p}}^{\prime }\) are νk-equivalent. In other words, \({\mathfrak {p}}\) and \({\mathfrak {p}}^{\prime }\) belong to the same cell of μk if and only if, for each symbol σ ∈Σ, there exists a final state \({\mathfrak {q}}\in {F}({B}_{{k}})\) such that \(({{\mathfrak {p}},{\sigma },{\mathfrak {q}}})\in {T}({B}_{{k}})\) if and only if there exists a final state \({\mathfrak {q}}^{\prime }\in {F}({B}_{{k}})\) (possibly \({\mathfrak {q}}^{\prime }={\mathfrak {q}}\)) such that \(({{\mathfrak {p}}^{\prime },{\sigma },{\mathfrak {q}}^{\prime }})\in {T}({B}_{{k}})\). Consequently, \({\mathfrak {p}}\) and \({\mathfrak {p}}^{\prime }\) belong to the same cell of μk if and only if \({{\mathscr{L}}({D},i,{\mathfrak {p}})}={{\mathscr{L}}({D},i,{\mathfrak {p}}^{\prime })}\).
Inductive step. Consider
k −
i > 0. Since
r(
Bi) =
ℓ(
Bi+ 1) and
νi =
μi+ 1, it follows from the inductive hypothesis that any two right states
\({\mathfrak {q}},{\mathfrak {q}}^{\prime }\in {r}({B}_{i})\) belong to the same cell of
νi if and only if
\({{\mathscr{L}}({D},i+1,{\mathfrak {q}})}={{\mathscr{L}}({D},i+1,{\mathfrak {q}}^{\prime })}\). Moreover, note that for each left state
\({\mathfrak {p}}\in {\ell }({B}_{i})\),
$$ {\mathcal{L}({D},i,{\mathfrak{p}})}=\bigcup_{{\mathfrak{q}}\in{r}({B}_{i})}\lbrace{{\sigma}{u}\in{\Sigma}^{{k}-i+1} \colon ({{\mathfrak{p}},{\sigma},{\mathfrak{q}}})\in{T}({B}_{i}), {u}\in{\mathcal{L}({D},i+1,{\mathfrak{q}})}}\rbrace\text{.} $$
(3)
Let
\({\mathfrak {p}},{\mathfrak {p}}^{\prime }\in {\ell }({B}_{i})\). We will prove that
\({\mathfrak {p}},{\mathfrak {p}}^{\prime }\) belong to the same cell of
μi if and only if
\({{\mathscr{L}}({D},i,{\mathfrak {p}})}={{\mathscr{L}}({D},i,{\mathfrak {p}}^{\prime })}\). The proof is split in two parts.
First, suppose that
\({\mathfrak {p}}\) and
\({\mathfrak {p}}^{\prime }\) belong to the same cell of
μi. Then
\({\mathfrak {p}}\) and
\({\mathfrak {p}}^{\prime }\) are
νi equivalent. In other words, for each symbol
σ ∈Σ, there exists
\({\mathfrak {q}}\in r({B}_{i})\) such that
\(({{\mathfrak {p}},{\sigma },{\mathfrak {q}}})\in {T}({B}_{i})\) if and only if there exists
\({\mathfrak {q}}^{\prime }\in {r}({B}_{i})\) such that
\(({{\mathfrak {p}}^{\prime },{\sigma },{\mathfrak {q}}^{\prime }})\in {T}({B}_{i})\) and
\({\mathfrak {q}}_{i}\) and
\({\mathfrak {q}}_{i}^{\prime }\) belong to the same cell of
νi. Using the induction hypothesis, we have that for each pair
\({\mathfrak {q}},{\mathfrak {q}}^{\prime }\) belonging to the same cell of
νi,
\({{\mathscr{L}}({D},i+1,{\mathfrak {q}})}={{\mathscr{L}}({D},i+1,{\mathfrak {q}}^{\prime })}\). Therefore, using (
3), that
\({{\mathscr{L}}({D},i,{\mathfrak {p}})}={{\mathscr{L}}({D},i,{\mathfrak {p}}^{\prime })}\).
Now, in order to prove the converse, suppose for contradiction that
\({\mathfrak {p}}\) and
\({\mathfrak {p}}^{\prime }\) do not belong to the same cell of
μi and that
\({{\mathscr{L}}({D},i,{\mathfrak {p}})}={{\mathscr{L}}({D},i,{\mathfrak {p}}^{\prime })}\). Since
Bi is a deterministic, complete layer, for each symbol
σ ∈Σ, there exists exactly one right state
\({\mathfrak {q}}\in {r}({B}_{i})\) such that
\(({{\mathfrak {p}},{\sigma },{\mathfrak {q}}})\in {T}({B}_{i})\). Similarly, for each symbol
σ ∈Σ, there exists exactly one right state
\({\mathfrak {q}}^{\prime }\in {r}({B}_{i})\) such that
\(({{\mathfrak {p}}^{\prime },{\sigma },{\mathfrak {q}}^{\prime }})\in {T}({B}_{i})\). Consequently, for some symbol
σ ∈Σ, the right states
\({\mathfrak {q}}\) and
\({\mathfrak {q}}^{\prime }\) associated with
σ, and
\({\mathfrak {p}}\) and
\({\mathfrak {p}}^{\prime }\), respectively, belong to distinct cells of
νi. Then, it follows from the induction hypothesis that
\({{\mathscr{L}}({D},i+1,{\mathfrak {q}})}\neq {{\mathscr{L}}({D},i+1,{\mathfrak {q}}^{\prime })}\). Assume without loss of generality that
\({{\mathscr{L}}({D},i+1,{\mathfrak {q}})}\setminus {{\mathscr{L}}({D},i+1,{\mathfrak {q}}^{\prime })}\neq \emptyset \), and let
\({u}\in {{\mathscr{L}}({D},i+1,{\mathfrak {q}})}\setminus {{\mathscr{L}}({D},i+1,{\mathfrak {q}}^{\prime })}\). Based on (
3), we have that
\({\sigma }{u}\in {{\mathscr{L}}({D},i,{\mathfrak {p}})}\) but
\({\sigma }{u}\not \in {{\mathscr{L}}({D},i,{\mathfrak {p}}^{\prime })}\). This implies that
\({{\mathscr{L}}({D},i,{\mathfrak {p}})}\neq {{\mathscr{L}}({D},i,{\mathfrak {p}}^{\prime })}\), contradicting our initial supposition. □
Let Σ be an alphabet and
\({w}\in {{\mathbb {N}}_+}\). We denote by
\({\mathscr{M}}({\Sigma },{w})\) the set consisting of all triples (
B,
μ,
ν) such that
B is a deterministic, complete layer in
\({\widehat {{\mathscr{B}}}({\Sigma }, {w})}\), and (
μ,
ν) is a merging annotation for
B. Additionally, we denote by
\(\zeta [{\Sigma },{w}]\colon {\mathscr{M}}({\Sigma },{w})\rightarrow {\widehat {{\mathscr{B}}}({\Sigma }, {w})}\) the map that sends each triple
\(({{B},\mu ,\nu })\in {\mathscr{M}}({\Sigma },{w})\) to the layer
\(\zeta [{\Sigma },{w}]({B},\mu ,\nu )\in {\widehat {{\mathscr{B}}}({\Sigma }, {w})}\) obtained from
B by identifying, for each
X ∈
μ ∪
ν, all states belonging to
X with the smallest state that belongs to
X. More formally, for each triple
\(({{B},\mu ,\nu })\in {\mathscr{M}}({\Sigma },{w})\), we let
\(\zeta [{\Sigma },{w}]({B},\mu ,\nu ) = {{B}^{\prime }}\), where
\({{B}^{\prime }}\) is the deterministic, complete layer belonging to
\({\widehat {{\mathscr{B}}}({\Sigma }, {w})}\) defined as follows:
-
\({\ell }({{B}^{\prime }}) \doteq \bigcup _{{X} \in \mu }\lbrace {\min \limits {X}}\rbrace \); \({r}({{B}^{\prime }}) \doteq \bigcup _{{X}^{\prime } \in \nu }\lbrace {\min \limits {X}^{\prime }}\rbrace \);
-
\({T}({{B}^{\prime }}) \doteq \bigcup _{{X}\in \mu ,{X}^{\prime }\in \nu }\lbrace {({\min \limits {X},{\sigma },\min \limits {X}^{\prime }}) \colon \exists {\mathfrak {p}}\in {X}, \exists \mathfrak {q}\in X^{\prime }, ({\mathfrak {p},\sigma ,\mathfrak {q}})\in T(B)}\rbrace \);
-
\({\iota }({{B}^{\prime }}) \doteq {\iota }({B})\); \({\phi }({{B}^{\prime }}) \doteq {\phi }({B})\);
-
\({I}({{B}^{\prime }}) \doteq {I}({B})\); \({F}({{B}^{\prime }}) \doteq {r}({{B}^{\prime }}) \cap {F}({B})\).
Let
\( {\zeta }[{\Sigma },{w}]\colon {{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circledast }}\rightarrow {{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circledast }}\) be the map that for each
\(k\in \mathbb {N}_{+}\), sends each deterministic, complete ODD
\(D = B_{1}{\cdots } B_{k}\in \widehat {{\mathscr{B}}}({\Sigma },{w})^{\protect \circ {{k}}}\) to the deterministic, complete ODD
$$ {\zeta}[{\Sigma},{w}]({D}) \doteq \zeta[{\Sigma}, {w}](B_{1},\mu_{1},\nu_{1})\cdots\zeta[{\Sigma},{w}](B_{k},\mu_{k},\nu_{k})\in\widehat{\mathcal{B}}({\Sigma},{w})^{\protect\circ{{k}}}\text{,} $$
where 〈(
μ1,
ν1),…,(
μk,
νk)〉 denotes the unique merging annotation for
D (see Proposition 31).
Let Σ be an alphabet,
\({w},{k}\in {{\mathbb {N}}_+}\) and
\({D}\in {{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circ {{k}}}}\). We recall that since
D is a deterministic, complete ODD, we have that for each string
\({s}={\sigma }_{1}\cdots {\sigma }_{{k}}\in {\Sigma }^{{k}}\), there is a unique valid sequence
\(\langle {({{\mathfrak {p}}_{1},{\sigma }_{1},{\mathfrak {q}}_{1}}),\ldots ,({{\mathfrak {p}}_{{k}},{\sigma }_{{k}},{\mathfrak {q}}_{{k}}})}\rangle \) for
s in
D. Thus, for each string
s ∈Σ
k and each
i ∈ [
k], we let
\({\mathfrak {q}}_{[{D},{s},i]}\doteq {\mathfrak {q}}_{i}\) denote the unique right state
\({\mathfrak {q}}_{i}\in {r}({B}_{i})\) that belongs to the valid sequence for
s in
D. Moreover, we let
$$ [{D},{s},i]\doteq\lbrace{{s}^{\prime}\in{\Sigma}^{{k}}\colon {\mathfrak{q}}_{[{D},{s}^{\prime},i]}={\mathfrak{q}}_{[{D},{s},i]}}\rbrace\ $$
denote the equivalence class of
s with respect to
D and
i.
Proof
Assume that
D =
B1⋯
Bk, for some
\({k} \in {{\mathbb {N}}_+}\), and let 〈(
μ1,
ν1)⋯(
μk,
νk)〉 be the unique merging annotation for
D. First, we prove that
\({{\mathscr{L}}( {\zeta }[{\Sigma },{w}]({D}))} = {{\mathscr{L}}({D})}\). Let
\({s} = {\sigma }_{1}\cdots {\sigma }_{{k}} \in {\Sigma }^{{k}}\). Suppose that
\({s} \in {{\mathscr{L}}({D})}\). Then, there exists an accepting sequence
\(\langle {({{\mathfrak {p}}_{1},{\sigma }_{1},{\mathfrak {q}}_{1}}),\ldots ,({{\mathfrak {p}}_{{k}},{\sigma }_{{k}},{\mathfrak {q}}_{{k}}})}\rangle \) for
s in
D. For each
i ∈ [
k], let
Xi be the unique cell of
νi that contains
\({\mathfrak {q}}_{i}\). Then, we have that
$$ \langle{({{\mathfrak{p}}_{1},{\sigma}_{1},\min {X}_{1}}),({\min {X}_{1},{\sigma}_{{k}},\min {X}_{2}}),\ldots,({\min {X}_{{k}-1},{\sigma}_{{k}},\min {X}_{{k}}})}\rangle $$
is an accepting sequence for
s in
ζ[Σ,
w](
D). As a result, we obtain that
\({{\mathscr{L}}( {\zeta }[{\Sigma },{w}]({D}))} \subseteq {{\mathscr{L}}({D})}\). Now, suppose that
\({s} \in {{\mathscr{L}}( {\zeta }[{\Sigma },{w}]({D}))}\). Then, there exists an accepting sequence
\(\langle {({{\mathfrak {p}}^{\prime }_{1},{\sigma }_{1},{\mathfrak {q}}^{\prime }_{1}}),\ldots ,({{\mathfrak {p}}^{\prime }_{{k}},{\sigma }_{{k}},{\mathfrak {q}}^{\prime }_{{k}}})}\rangle \) for
s in
ζ[Σ,
w](
D). We note that for each
i ∈ [
k], there exists a right state
\({\mathfrak {q}}_{i}\in {r}({B}_{i})\) such that
\({\mathfrak {q}}_{i}\) and
\({\mathfrak {q}}^{\prime }_{i}\) belong to a same cell of
νi and
\(({{\mathfrak {p}}_{i},{\sigma }_{i},{\mathfrak {q}}_{i}})\in {T}({B}_{i})\), where
\({\mathfrak {p}}_{1} = {\mathfrak {p}}^{\prime }_{1}\) and
\({\mathfrak {p}}_{j}={\mathfrak {q}}_{j-1}\) for each
j ∈{2,…,
k}. Thus, there exists an accepting sequence
\(\langle {({{\mathfrak {p}}_{1},{\sigma }_{1},{\mathfrak {q}}_{1}}),\ldots ,({{\mathfrak {p}}_{{k}},{\sigma }_{{k}},{\mathfrak {q}}_{{k}}})}\rangle \) for
s in
D. Therefore,
\({{\mathscr{L}}( {\zeta }[{\Sigma },{w}]({D}))} \supseteq {{\mathscr{L}}({D})}\).
Now, we prove that ζ[Σ,w](D) is minimized if D is reachable. Thus, assume that D is reachable. This implies that ζ[Σ,w](D) is also reachable and thus, for each i ∈ [k] and each \({\mathfrak {q}} \in {r}(\zeta [{\Sigma },{w}]({B}_{i},\mu _{i},\nu _{i}))\), \({\mathfrak {q}} = {\mathfrak {q}}_{[ {\zeta }[{\Sigma },{w}]({D}),{s},i]}\) for some s ∈Σk. Then, for each i ∈ [k], let \({w}_{i} = \lvert {{r}(\zeta [{\Sigma },{w}]({B}_{i},\mu _{i},\nu _{i}))}\rvert \) and let \({{s}_{1}^{i}},\ldots ,{s}_{{w}_{i}}^{i}\) be strings such that \([ {\zeta }[{\Sigma },{w}]({D}),{{s}_{j}^{i}},i] \neq [ {\zeta }[{\Sigma },{w}]({D}),{s}_{j^{\prime }}^{i},i]\) for each j ∈ [wi] and each \(j^{\prime } \in {[{{w}_{i}}]}\) with \(j \neq j^{\prime }\). Also, let \({{D}^{\prime }}={{B}^{\prime }}_{1}\cdots {{B}^{\prime }}_{{k}}\in {{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circ {{k}}}}\) be a minimized ODD such that \({{\mathscr{L}}({D^{\prime }})} = {{\mathscr{L}}({D})}\). We note that \({D^{\prime }}\) is reachable. Thus, for each i ∈ [k] and each \({\mathfrak {q}}^{\prime } \in {r}({{B}^{\prime }}_{i})\), \({\mathfrak {q}}^{\prime } = {\mathfrak {q}}_{[{{D}^{\prime }},{s}^{\prime },i]}\) for some \({s}^{\prime } \in {\Sigma }^{{k}}\). Moreover, we have that \( {\zeta }[{{\Sigma }}{{w}}]({D^{\prime }})={D^{\prime }}\), otherwise \({{D}^{\prime }}\) would not be minimized. Then, for each i ∈ [k], we let \(\pi _{i} \colon {r}(\zeta [{\Sigma },{w}]({B}_{i},\mu _{i},\nu _{i})) \rightarrow {r}({{B}^{\prime }}_{i})\) be the mapping such that for each j ∈ [wi], \(\pi _{i}({\mathfrak {q}}_{[ {\zeta }[{\Sigma },{w}]({D}),{{s}_{j}^{i}},i]}) = {\mathfrak {q}}_{[{{D}^{\prime }},{{s}_{j}^{i}},i]}\). It follows from Proposition 34 that πi is a bijection. Consequently, we obtain that 〈π0,…,πk〉 is a isomorphism between ζ[Σ,w](D) and \({{D}^{\prime }}\), where \(\pi _{0} \colon {\ell }(\zeta [{\Sigma },{w}]({B}_{1},\mu _{1},\nu _{1})) \rightarrow {\ell }({{B}^{\prime }}_{1})\) is the trivial bijection that sends the unique left state in ℓ(ζ[Σ,w](B1,μ1,ν1)) to the unique left state in \({\ell }({B^{\prime }}_{1})\). Therefore, ζ[Σ,w](D) is minimized. □
For each alphabet Σ and each positive integer
\({w}\in {{\mathbb {N}}_+}\), we let
\(\text {MR}[{\Sigma },{w}]\subseteq {\widehat {{\mathscr{B}}}({\Sigma }, {w})} \times {\mathscr{M}}({\Sigma },{w})\) and
\(\text {MC}[{\Sigma },{w}]\subseteq {\mathscr{M}}({\Sigma },{w})\times {\mathscr{M}}({\Sigma },{w})\) be the following relations.
$$ \text{MR}[{\Sigma},{w}] \doteq \lbrace{({{B}, ({{B},\mu,\nu})}) \colon ({{B},\mu,\nu})\in\mathcal{M}({\Sigma},{w})}\rbrace \text{ and } $$
$$ \begin{array}{@{}rcl@{}} \text{MC}[{\Sigma},{w}] &\doteq& \{ ({({{B},\mu,\nu}),({{B}^{\prime},\mu^{\prime},\nu^{\prime}})}) \colon ({{B},\mu,\nu}), ({{B}^{\prime},\mu^{\prime},\nu^{\prime}}) \in \mathcal{M}({\Sigma},{w}), {r}({B}) \\&=& {\ell}({B}^{\prime}), \nu = \mu^{\prime}\}\text{.} \end{array} $$
For each alphabet Σ and each positive integer
\({w} \in {{\mathbb {N}}_+}\), we define the
\(({\widehat {{\mathscr{B}}}({\Sigma }, {w})},\) \(\widehat {{\mathscr{B}}}({\Sigma }, {w}))\)-transduction
\(\mathfrak {mer}[{\Sigma },{w}]\) as
$$ \mathfrak{mer}[{\Sigma},{w}] \doteq \mathfrak{mm}[\text{MR}[{\Sigma},{w}]]\circ\mathfrak{cp}[\text{MC}[{\Sigma},{w}]]\circ \mathfrak{mm}[\zeta[{{\Sigma}},{{w}}]]. $$
The next lemma states that
\(\mathfrak {mer}[{\Sigma },{w}]\) is a transduction that sends each deterministic, complete ODD
\({D}\in {\widehat {{\mathscr{B}}}({{\Sigma }},{{w}})^{\protect \circledast }}\) to a
minimized deterministic, complete ODD
\({{D}^{\prime }}\in {{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circledast }}\) that has the same language as
D.
Proof
We note that \(\mathfrak {mer}[{\Sigma },{w}]\) consists of all pairs \(({{{D}},{{D}^{\prime }}})\) of non-empty strings over the alphabet \({\widehat {{\mathscr{B}}}({\Sigma }, {w})}\) satisfying the conditions that \(\lvert {{{D}}}\rvert =\lvert {{{D}^{\prime }}}\rvert \) and that, if D = B1⋯Bk and \({D^{\prime }}={B^{\prime }}_{1}\cdots {B^{\prime }}_{{k}}\) for some \({k}\in {{\mathbb {N}}_+}\), then there exists a merging annotation (μi,νi) for the layer Bi such that \({{B}^{\prime }}_{i}=\zeta [{\Sigma },{w}]({B}_{i},\mu _{i},\nu _{i})\) for each i ∈ [k], and r(Bj) = ℓ(Bj+ 1) and νj = μj+ 1 for each j ∈ [k − 1]. Additionally, based on Proposition 31, each (Σ,w)-ODD admits a unique merging annotation. As a result, we obtain that \(\mathsf {Dom}(\mathfrak {mer}[{\Sigma },{w}]) \supseteq {{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circledast }}\). Moreover, if \(({{{D}},{{D}^{\prime }}})\in \mathfrak {mer}[{\Sigma },{w}]\), then \({{D}^{\prime }} = {\zeta }[{\Sigma },{w}]({{D}})\); thus, by the uniqueness of ζ[Σ,w](D), the transduction \(\mathfrak {mer}[{\Sigma },{w}]\) is functional. Finally, it follows from Proposition 35 that for each pair \(({{{D}},{{D}^{\prime }}})\in \mathfrak {mer}[{\Sigma },{w}]\) such that D is a reachable ODD in \({{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circledast }}\), we have that \({{D}^{\prime }} = {\zeta }[{\Sigma },{w}]({{D}})\) is a minimized ODD in \({{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circledast }}\) that has the same language as D.
The fact that \(\mathfrak {mer}[{\Sigma },{w}]\) is \(2^{O(|{\Sigma }|\cdot {w}\cdot \log {w})}\)-regular follows from Proposition 5.(2) together with the fact that the multimap transductions \(\mathfrak {mm}[\text {MR}[{\Sigma },{w}]]\) and \(\mathfrak {mm}[\zeta [{\Sigma },\) w]] are 2-regular (Proposition 25.(1)), and that the transduction \(\mathfrak {cp}[\text {MC}[{\Sigma },{w}]]\) is \(2^{O(|{\Sigma }|\cdot {w}\cdot \log {w})}\)-regular (Proposition 25.(2)), given that \(\text {MC}[{\Sigma },{w}] \subseteq {\mathscr{M}}({\Sigma },{w})\times {\mathscr{M}}({\Sigma },{w})\), and that \(|{\mathscr{M}}({\Sigma },{w})|=2^{O(|{\Sigma }|\cdot {w}\cdot \log {w})}\). □
6.5 Normalization Transduction.
In this subsection, we define the normalization transduction, which intuitively simulates the process of numbering the states in each frontier of each layer of an ODD D according to their lexicographical order. This transduction can be defined as the composition of three elementary transductions. First, we use a multimap transduction to expand each layer of the ODD into a set of annotated layers. Each annotation relabels the left and right frontier vertices of the layer in such a way that the layer itself is normalized. Subsequently, we use a compatibility transduction that defines two consecutive annotated layers to be compatible if and only if the relabeling of the right-frontier of the first is equal to the relabeling of the left frontier of the second. It is possible to show that each reachable ODD D gives rise to a unique sequence of annotated layers where each two consecutive layers are compatible. Finally, we apply a mapping that sends each annotated layer to the layer obtained sending the numbers in the frontiers to their relabeled versions. The resulting ODD is isomorphic to the original one, and therefore besides preserving the language, it also preserves reachability and minimality.
Let Σ be an alphabet,
\({w} \in {{\mathbb {N}}_+}\), and let
\({B}\in {\widehat {{\mathscr{B}}}({\Sigma }, {w})}\). For each two bijections
\(\pi \colon {\ell }({B})\rightarrow \llbracket {\lvert {{\ell }({B})}\rvert }\rrbracket \) and
\(\pi ^{\prime }\colon {r}({B})\rightarrow \llbracket {\lvert {{r}({B})}\rvert }\rrbracket \), we denote by
\({\langle {\pi {B}\pi ^{\prime }}\rangle }\) the (Σ,
w)-layer obtained from
B by applying the bijection
π to the left frontier of
B and by applying the bijection
\(\pi ^{\prime }\) to the right frontier of
B. More formally,
\({\langle {\pi {B}\pi ^{\prime }}\rangle }={{B}^{\prime }}\) is the (Σ,
w)-layer defined as follows:
-
\({\ell }({{B}^{\prime }}) \doteq \lbrace {\pi ({\mathfrak {p}}) \colon {\mathfrak {p}} \in {\ell }({B})}\rbrace \); \({r}({{B}^{\prime }}) \doteq \lbrace {\pi ^{\prime }(\mathfrak {q}) \colon \mathfrak {q} \in r(B)}\rbrace \);
-
\({I}({{B}^{\prime }}) \doteq \lbrace {\pi ({\mathfrak {p}}) \colon {\mathfrak {p}} \in {I}({B})}\rbrace \); \({F}({{B}^{\prime }}) \doteq \lbrace {\pi ^{\prime }(\mathfrak {q}) \colon \mathfrak {q} \in F(B)}\rbrace \);
-
\({T}({{B}^{\prime }}) \doteq \lbrace {({\pi ({\mathfrak {p}}), {\sigma }, \pi ^{\prime }({\mathfrak {q}})}) \colon ({{\mathfrak {p}}, {\sigma }, {\mathfrak {q}}}) \in {T}(B)}\rbrace \);
-
\({\iota }({{B}^{\prime }}) \doteq {\iota }({B})\); \({\phi }({{B}^{\prime }}) \doteq {\phi }({B})\).
We note that since \({B}\in {\widehat {{\mathscr{B}}}({\Sigma }, {w})}\), \({\langle {\pi {B}\pi ^{\prime }}\rangle }\) also belongs to \({\widehat {{\mathscr{B}}}({\Sigma }, {w})}\).
Let Σ be an alphabet, \({w} \in {{\mathbb {N}}_+}\). A normalizing isomorphism for a reachable layer \({B}\in {\widehat {{\mathscr{B}}}({\Sigma }, {w})}\) is a pair \(({\pi ,\pi ^{\prime }})\) of bijections \(\pi \colon {\ell }({B})\rightarrow \llbracket {\lvert {{\ell }({B})}\rvert }\rrbracket \) and \(\pi ^{\prime }\colon {r}({B})\rightarrow \llbracket {\lvert {{r}({B})}\rvert }\rrbracket \) such that the layer \({\langle {\pi {B}\pi ^{\prime }}\rangle }\) is normalized. Let \({k}\in {{\mathbb {N}}_+}\) and D = B1⋯Bk be a reachable ODD in \({{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circ {{k}}}}\). A normalizing isomorphism for D is a sequence \(\overline {\pi } = \langle {\pi _{0},\pi _{1},\ldots ,\pi _{{k}}}\rangle \) such that for each i ∈ [k], (πi− 1,πi) is a normalizing isomorphism for Bi.
For each finite set
X, we denote by
\(\mathbb {S}_{X} \doteq \lbrace {\pi \colon X\rightarrow \llbracket {\lvert {X}\rvert }\rrbracket \colon \pi \text { is a bijection}}\rbrace \) the set of all bijections from
X to
\(\llbracket {\lvert {X}\rvert }\rrbracket \). For each alphabet Σ and each
\({w} \in {{\mathbb {N}}_+}\) we define the following set.
$$ \mathcal{S}[{\Sigma},{w}] = \lbrace{({\pi,{B},\pi^{\prime}}) \colon {B}\!\in\! {\widehat{\mathcal{B}}({\Sigma}, {w})}, \pi\!\in\!\mathbb{S}_{{\ell}({B})}, \pi^{\prime}\!\in\! \mathbb{S}_{{r}({B})}, {\langle{\pi{B}\pi^{\prime}}\rangle} \text{ is normalized}}\rbrace. $$
We let
\(\eta [{\Sigma },{w}]:\mathcal {S}[{\Sigma },{w}] \rightarrow {\widehat {{\mathscr{B}}}({\Sigma }, {w})}\) be the map that sends each triple
\(({\pi ,{B},\pi ^{\prime }}) \in \mathcal {S}[{\Sigma },{w}]\) to the layer
\({\langle {\pi {B}\pi ^{\prime }}\rangle }\). Moreover, we let
\(\text {NR}[{\Sigma },{w}]\subseteq {\widehat {{\mathscr{B}}}({\Sigma }, {w})}\times \mathcal {S}[{\Sigma },{w}]\) and
\(\text {NC}[{\Sigma },{w}]\subseteq \mathcal {S}[{\Sigma },{w}]\times \mathcal {S}[{\Sigma },{w}]\) be the following relations.
$$ \text{NR}[{\Sigma},{w}] \doteq \{({{B},({\pi,{B},\pi^{\prime}})}) \colon ({\pi,{B},\pi^{\prime}})\in \mathcal{S}[{\Sigma},{w}]\}. $$
$$ \text{NC}[{\Sigma},{w}] \doteq \{ ({({\pi,{B},\pi^{\prime}}),({\pi^{\prime},{{B}^{\prime}},\pi^{\prime\prime}})})\in \mathcal{S}[{\Sigma},{w}]\times \mathcal{S}[{\Sigma},{w}] \colon {r}({B}) = {\ell}({{B}^{\prime}}), \}\text{.} $$
Finally, for each alphabet Σ, and each positive integer
\({w} \in {{\mathbb {N}}_+}\), we let
\(\mathfrak {nor}[{\Sigma },{w}]\) be the
\(({\widehat {{\mathscr{B}}}({\Sigma }, {w})},{\widehat {{\mathscr{B}}}({\Sigma }, {w})})\)-transduction
$$ \mathfrak{nor}[{\Sigma},{w}] \doteq \mathfrak{mm}[\text{NR}[{\Sigma},{w}]] \circ \mathfrak{cp}[\text{NC}[{\Sigma},{w}]]\circ \mathfrak{mm}[\eta[{\Sigma},{w}]]. $$
The next lemma states that
\(\mathfrak {nor}\) is a transduction that sends each reachable, deterministic, complete ODD
\({D}\in {\widehat {{\mathscr{B}}}({{\Sigma }},{{w}})^{\protect \circledast }}\) to as
normalized, deterministic, complete ODD
\({{D}^{\prime }}\in {{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circledast }}\) that has the same language as
D.
Proof
We note that \(\mathfrak {nor}[{\Sigma },{w}]\) consists of all pairs \(({{{D}},{{D}^{\prime }}})\) of non-empty strings over the alphabet \({\widehat {{\mathscr{B}}}({\Sigma }, {w})}\) satisfying the conditions that \(\lvert {{{D}}}\rvert =\lvert {{{D}^{\prime }}}\rvert \) and that, if D = B1⋯Bk and \({D^{\prime }}={B^{\prime }}_{1}\cdots {B^{\prime }}_{{k}}\) for some \({k}\in {{\mathbb {N}}_+}\), then there exists a sequence of permutations \(\overline {\pi } = \langle {\pi _{0},\pi _{1},\ldots ,\pi _{{k}}}\rangle \) such that for each i ∈ [k], \((\pi _{i-1},{B}_{i},\pi _{i})\in \mathcal {S}[{\Sigma },{w}]\) and \({B}_{i}^{\prime } = {\langle {\pi _{i-1}{B}_{i}\pi _{i}}\rangle }\). Additionally, based on Proposition 37, each reachable, deterministic (Σ,w)-ODD admits a unique normalizing isomorphism. As a result, we obtain that \(\mathsf {Dom}(\mathfrak {nor}[{\Sigma },{w}]) \supseteq \lbrace {{D} \in {{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circledast }} \colon {D} \text { is reachable}}\rbrace \). Moreover, if \(({{{D}},{{D}^{\prime }}})\in \mathfrak {d}({{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circledast }})\circ \mathfrak {nor}[{\Sigma },{w}]\), then \({{D}^{\prime }} = {\langle {\pi _{0}{B}_{1}\pi _{1}}\rangle }\cdots {\langle {\pi _{{k}-1}{B}_{{k}}\pi _{{k}}}\rangle }\), where \(\overline {\pi } = \langle {\pi _{0},\pi _{1},\ldots ,\pi _{{k}}}\rangle \) denotes the unique normalizing isomorphism of D; thus, by the uniqueness of \(\overline {\pi }\), the transduction \(\mathfrak {d}({{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circledast }})\circ \mathfrak {nor}[{\Sigma },{w}]\) is functional. Finally, it follows from Proposition 38 that for each pair \(({{{D}},{{D}^{\prime }}})\in \mathfrak {nor}[{\Sigma },{w}]\) such that D is a reachable ODD in \({{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circledast }}\), we have that \({{D}^{\prime }}\) is a normalized ODD in \({{\widehat {{\mathscr{B}}}({\Sigma }, {w})}^{\protect \circledast }}\) that has the same language as D.
The fact that \(\mathfrak {nor}[{\Sigma },{w}]\) is \(2^{O(|{\Sigma }|\cdot {w}\cdot \log {w})}\)-regular follows from Proposition 5.(2) together with the fact that the multimap transductions \(\mathfrak {mm}[\text {NR}[{\Sigma },{w}]]\) and \(\mathfrak {mm}[\eta [{\Sigma },{w}]]\) are 2-regular (Proposition 25.(1)), and that the transduction \(\mathfrak {cp}[\text {NC}\) [Σ,w]] is \(2^{O(|{\Sigma }|\cdot {w}\cdot \log {w})}\)-regular (Proposition 25.(2)), given that \(\text {NC}[{\Sigma },{w}] \subseteq \mathcal {S}[{\Sigma },{w}]\times \mathcal {S}[{\Sigma },{w}]\), and that \(|\mathcal {S}[{\Sigma },{w}]|=2^{O(|{\Sigma }|\cdot {w}\cdot \log {w})}\). □