The Equivalence Problem of E-Pattern Languages with Length Constraints Is Undecidable

Indeed, given some pattern with length constraints $(\alpha ,{\mathrm{\ell }}_{\alpha })\in {\mathrm{𝙿𝚊𝚝}}_{\mathrm{\Sigma },{𝒞}_{Len}}$, we can define the length constraint ${\mathrm{\ell }}_{\alpha }^{\prime }$ by using all constraints in ${\mathrm{\ell }}_{\alpha }$ and additionally, for each $x\in \mathrm{var}(\alpha )$, adding the constraint $x\ge 1$ to ${\mathrm{\ell }}_{\alpha }^{\prime }$. Then, $L_E(\alpha ,{\mathrm{\ell }}_{\alpha }^{\prime })=L_{NE}(\alpha ,{\mathrm{\ell }}_{\alpha })$.

We obtain the same result for pattern languages with regular constraints by intersecting the language of all variables with ${\mathrm{\Sigma }}^{+}$, i.e., given any language $L(x)$ for some variable $x\in X$ that is defined by some regular constraint $r\in {𝒞}_{Reg}$, we can define a regular constraint $r^{\prime }$ that defines the language $L^{\prime }(x)=L(x)\cap {\mathrm{\Sigma }}^{+}$. Then, given some pattern $\alpha \in \mathrm{𝙿𝚊𝚝}$, we obtain $L_{NE}(\alpha ,r)=L_E(\alpha ,r^{\prime })$. $◀$

The following statement then immediately follows by the previous lemma.

As shown in [26], considering regular constraints, problem cases over all patterns can be reduced to problems involving terminal-free patterns. The same does not hold in general in the case of length constraints, witnessed by the following proposition.

Assume $|\mathrm{\Sigma }|\ge 2$ and assume w.l.o.g. $𝚊,𝚋\in \mathrm{\Sigma }$ with $𝚊\ne 𝚋$. Let $(\alpha ,{\mathrm{\ell }}_{\alpha })\in {\mathrm{𝙿𝚊𝚝}}_{\mathrm{\Sigma },{𝒞}_{Len}}$ such that $\alpha =x_1𝚊$ and ${\mathrm{\ell }}_{\alpha }$ is an empty length constraint. So, $L_E(\alpha ,{\mathrm{\ell }}_{\alpha })=L_E(\alpha )={\mathrm{\Sigma }}^{\ast }\cdot \{𝚊\}$ ($L_{NE}(\alpha ,{\mathrm{\ell }}_{\alpha })=L_{NE}(\alpha )={\mathrm{\Sigma }}^{+}\cdot \{𝚊\}$). Suppose there exists some $\beta \in X^{\ast }$ and length constraint ${\mathrm{\ell }}_{\beta }$ such that $L_E(\beta ,{\mathrm{\ell }}_{\beta })=L_E(\alpha ,{\mathrm{\ell }}_{\alpha })$ ($L_{NE}(\beta ,{\mathrm{\ell }}_{\beta })=L_{NE}(\alpha ,{\mathrm{\ell }}_{\alpha })$). W.l.o.g. we continue with the erasing case. The following also holds for the non-erasing case with small changes. Let $w\in L_E(\alpha ,{\mathrm{\ell }}_{\alpha })$. Then $w=u𝚊$ for some $u\in {\mathrm{\Sigma }}^{\ast }$. As $L_E(\alpha ,{\mathrm{\ell }}_{\alpha })=L_E(\beta ,{\mathrm{\ell }}_{\beta })$, there exists some $h\in H_{{\mathrm{\ell }}_{\beta }}$ such that $h(\beta )=w=u𝚊$. Then, $\beta ={\beta }_{1}x{\beta }_2$ for $x\in X$ and ${\beta }_1,{\beta }_2\in X^{\ast }$ as well as $u=u_1{u}_2$ for some $u_1,u_2\in {\mathrm{\Sigma }}^{\ast }$ such that $h({\beta }_1)=u_1$, $h(x)=u_2𝚊$ and $h({\beta }_2)=\epsilon$. But then, we also find some $h^{\prime }\in H_{{\mathrm{\ell }}_{\beta }}$ with $h^{\prime }(x)=u_1𝚋$ as $𝚊$ and $𝚋$ are obtained at the same position by the same variable. Then, $h^{\prime }(\beta )=v𝚋$ for some $v\in {\mathrm{\Sigma }}^{\ast }$. As $v𝚋\notin {\mathrm{\Sigma }}^{\ast }\cdot \{𝚊\}$ but $L_E(\alpha ,{\mathrm{\ell }}_{\alpha })={\mathrm{\Sigma }}^{\ast }\cdot \{𝚊\}$, we know that $\beta$ cannot exist. $◀$

With that, we know that we cannot restrict ourselves to only show hardness or undecidability for the general case, as the terminal-free case may result in something else. We begin with the membership problems for both, the erasing- and non-erasing pattern languages. Those have been shown to be NP-complete for patterns without constraints in the terminal-free and general cases (see, e.g.,[1, 18, 33]). Hence, we observe the following for patterns with length constraints.

Indeed, NP-hardness is immediately obtained by the NP-hardness of patterns without any constraints. Given some $(\alpha ,{\mathrm{\ell }}_{\alpha })\in {\mathrm{𝙿𝚊𝚝}}_{\mathrm{\Sigma },{𝒞}_{Len}}$, NP containment follows by the fact that any valid certificate results in a substitution $h\in H_{{\mathrm{\ell }}_{\alpha }}$ of length at most $|h(\alpha )|=|w|$ and that we can check in polynomial time whether some given substitution is ${\mathrm{\ell }}_{\alpha }$-valid. This can be done by checking whether the lengths of the variable substitutions $|h(x)|$ for all $x\in \mathrm{var}(\alpha )$ satisfy ${\mathrm{\ell }}_{\alpha }$. This concludes the membership problem for all cases.

Another result that can be immediately obtained is the general undecidability of the inclusion problem for pattern languages with length constraints. For pattern languages without any constraints, this problem has been generally shown to be undecidable, first, for unbounded alphabets by Jiang et al. [19] and later on for all bounded alphabets of sizes $|\mathrm{\Sigma }|\ge 2$ by Freydenberger and Reidenbach in [11] as well as Bremer and Freydenberger in [3]. So, we have the following.

Out of that, in the general case, we immediately obtain the following for pattern languages with length constraints.

That leaves us with the terminal-free cases of the inclusion problem as well as the general and terminal-free cases of the equivalence problems for both, erasing and non-erasing pattern languages with length constraints. The first and most significant main result shows that the most prominent open problem for pattern languages, i.e., the equivalence problem for erasing patterns, is undecidable for pattern languages with length constraints, even if we are restricted to terminal-free patterns and use no disjunctions in the length constraints.

Based on the proofs in, e.g., [19] and [11], we reduce the emptiness problem for nondeterministic 2-counter automata without input to the equivalence problem of erasing pattern languages with length constraints. Due to the length of the formal proof, here, we only give a sketch of the idea and provide the formal construction of the reduction. For a full extension of the proof containing a collection of shown properties and a formal proof of the correctness of the reduction itself, see [27].

Given an automaton $A$, we construct two patterns with length constraints $(\alpha ,{\mathrm{\ell }}_{\alpha })$ and $(\beta ,{\mathrm{\ell }}_{\beta })$ such that $L_E(\alpha ,{\mathrm{\ell }}_{\alpha })=L_E(\beta ,{\mathrm{\ell }}_{\beta })$ if and only if $\mathrm{𝚅𝚊𝚕𝙲}(A)=\mathrm{\varnothing }$. The pattern with length constraints $(\alpha ,{\mathrm{\ell }}_{\alpha })$ can be seen as a pattern which allows for all possible words of a specific format to be obtained, especially also encodings of valid computations of $A$. The pattern with length constraints $(\beta ,{\mathrm{\ell }}_{\beta })$ can be seen as a tester pattern that allows only for words that are not encodings of valid computations of $A$ that have this specific structure. By that, if $A$ has some valid computation and, hence, an encoding of a valid computation of $A$ exists, we have that there exists a word in $L_E(\alpha ,{\mathrm{\ell }}_{\alpha })$ that is not in $L_E(\beta ,{\mathrm{\ell }}_{\beta })$, hence $L_E(\alpha ,{\mathrm{\ell }}_{\alpha })\ne L_E(\beta ,{\mathrm{\ell }}_{\beta })$.

The previous property is the main argument used in the proofs in [19, 11] to show undecidability of the inclusion problem for erasing pattern languages. In addition to that, using length constraints, $(\alpha ,{\mathrm{\ell }}_{\alpha })$ and $(\beta ,{\mathrm{\ell }}_{\beta })$ can be constructed in such a way, that we always have $L_E(\beta ,{\mathrm{\ell }}_{\beta })\subseteq L_E(\alpha ,{\mathrm{\ell }}_{\alpha })$. This is the most significant difference to the aforementioned results. Thus, in this case, we have that the equivalence of $L_E(\alpha ,{\mathrm{\ell }}_{\alpha })$ and $L_E(\beta ,{\mathrm{\ell }}_{\beta })$ decides the emptiness problem for $A$. The latter is undecidable, resulting in the undecidability of the equivalence problem of erasing pattern languages with length constraints. This is similar to the idea of the construction in [26] for patterns with regular constraints, where the same approach but with differently constructed patterns and with another type of constraints has been used. We also mention that length constraints allow for a construction that shows undecidability even in the case of terminal-free patterns. This is interesting, as for terminal-free erasing pattern languages without any constraints, equivalence and inclusion are actually decidable.

Now, we continue with the constructions of $(\alpha ,{\mathrm{\ell }}_{\alpha })$ and $(\beta ,{\mathrm{\ell }}_{\beta })$. First, $(\alpha ,{\mathrm{\ell }}_{\alpha })$ is defined by

for independent variables $y_1,y_2,x_v,{\alpha }_1,{\alpha }_2,z,z^{\prime }\in X$, and by the following linear system ${\mathrm{\ell }}_{\alpha }$:

• $\mathrm{■}$

  $x_v=5$

• $\mathrm{■}$

  $z=1$, $z^{\prime }=1$

Notice that any word in $L_E(\alpha ,{\mathrm{\ell }}_{\alpha })$ has a suffix of fixed length with the form $vuv$ where $v\in {\mathrm{\Sigma }}^5$ and $u\in \{0000,\mathrm{\#}\mathrm{\#}\mathrm{\#}\mathrm{\#},0\mathrm{\#}\mathrm{\#}0,\mathrm{\#}00\mathrm{\#}\}$. In comparison to the construction in [11] that made use of a specific prefix and a specific suffix to enforce predicate choice, only this suffix suffices for this purpose in this construction.

Next, we construct $(\beta ,{\mathrm{\ell }}_{\beta })$. We set the pattern $\beta$ to

for new and independent variables $y_1^{\prime },y_2^{\prime }\in X$ and terminal-free patterns ${\widehat{\beta }}_i,{\ddot{\beta }}_i\in X^{\ast }$. Assume $\mu$ to be defined as in [11]. For $i\in [\mu +1]$, set

• $\mathrm{■}$

  ${\widehat{\beta }}_i=x_i{\gamma }_i{x}_i{\delta }_i{x}_i$,

• $\mathrm{■}$

  ${\ddot{\beta }}_i=x_i{\eta }_i{x}_i$,

for new and independent variables $x_i\in X$ and terminal-free patterns ${\gamma }_i,{\delta }_i,{\eta }_i\in X^{\ast }$. Assume

• $\mathrm{■}$

  ${\eta }_i=z_i{z}_i^{\prime }{z}_i^{\prime }{z}_i$ and $z_i\ne z_i^{\prime }$ for $i\in [\mu ]$,

• $\mathrm{■}$

  ${\eta }_{\mu +1}={(z_{\mu +1})}^4$,

• $\mathrm{■}$

  $\mathrm{var}({\gamma }_i{\delta }_i{\eta }_i)\cap \mathrm{var}({\gamma }_j{\delta }_j{\eta }_j)=\mathrm{\varnothing }$ if $i\ne j$ for $i,j\in [\mu +1]$, and

• $\mathrm{■}$

  $x_k,y_1^{\prime },y_2^{\prime }\notin \mathrm{var}({\gamma }_i{\delta }_i{\eta }_i)$ for all $i,k\in [\mu +1]$

for new and independent variables $z_i,z_i^{\prime }\in X$. Hence, all variables inside $\mathrm{var}({\gamma }_i{\delta }_i{\eta }_i)$ do not occur anywhere else but in these factors. The length constraint ${\mathrm{\ell }}_{\beta }$ is defined by the following and only the following system (no additional constraints will be added later on).

1. 1.

   ${\sum }_{i=1}^{\mu +1}{z}_i=1$

2. 2.

   ${\sum }_{i=1}^{\mu }{z}_i^{\prime }\le 1$

3. 3.

   ${\sum }_{i=1}^{\mu +1}{x}_i=5$

4. 4.

   $x_i-5z_i=0$ for all $i\in [\mu +1]$

5. 5.

   $z_i-z_i^{\prime }=0$ for all $i\in [\mu ]$

For all $i\in [\mu ]$, we say that ${\gamma }_i$ and ${\delta }_i$ are defined just as in [11]. For the case of $\mu +1$, we set ${\gamma }_{\mu +1}$ and ${\delta }_{\mu +1}$ by

• $\mathrm{■}$

  ${\gamma }_{\mu +1}=y_{\mu +1}$, and

• $\mathrm{■}$

  ${\delta }_{\mu +1}=y_{\mu +1}^{\prime }$

for new and independent variables $y_{\mu +1}$ and $y_{\mu +1}^{\prime }$.

We now give a really rough sketch of the idea on why this construction works. First, the length constraints ${\mathrm{\ell }}_{\beta }$ allow for only one ${\ddot{\beta }}_i$, for $i\in [\mu +1]$, to be substituted to a non-empty word. Any word obtained by ${\ddot{\beta }}_i$ can be obtained by the suffix $x_{v}z{z}^{\prime }{z}^{\prime }z{x}_v$ of $(\alpha ,{\mathrm{\ell }}_{\alpha })$. Additionally, everything obtained in ${\widehat{\beta }}_i$ can then be obtained by $x_v{\alpha }_1{x}_v{\alpha }_2{x}_v$ in $(\alpha ,{\mathrm{\ell }}_{\alpha })$. Everything else can be obtained by the variables $y_1$ and $y_2$. Hence, we get the most significant property of this proof, i.e., $L_E(\beta ,{\mathrm{\ell }}_{\beta })\subseteq L_E(\alpha ,{\mathrm{\ell }}_{\alpha })$.

Now, for the other direction, we consider two cases. These are, given some substitution $h\in H_{{\mathrm{\ell }}_{\alpha }}$, whether $h(z)=h(z^{\prime })$ or whether $h(z)\ne h(z^{\prime })$. By ${\mathrm{\ell }}_{\alpha },$ we know $|h(z)|=|h(z^{\prime })|=1$. It can be shown that, if $h(z)=h(z^{\prime })$, then we can use ${\ddot{\beta }}_{\mu +1}$ to obtain $h(x_{v}z{z}^{\prime }{z}^{\prime }z{x}_v)$ and ${\widehat{\beta }}_{\mu +1}$ to obtain $h(x_v{\alpha }_1{x}_v{\alpha }_2{x}_v)$. $h(y_1)$ can be obtained in $y_1^{\prime }$ and the same holds analogously for $h(y_2)$ and $y_2^{\prime }$. Hence, if $h(z)=h(z^{\prime })$, then $h(\alpha )\in L_E(\beta ,{\mathrm{\ell }}_{\beta })$. If on the other hand we have $h(z)\ne h(z^{\prime })$ and $h(y_1)=\epsilon$ as well as $h(y_2)=\epsilon$, we need to find some ${\widehat{\beta }}_i$ and ${\ddot{\beta }}_i$, for $i\in [\mu ]$, to obtain $h(x_v{\alpha }_1{x}_v{\alpha }_2{x}_v)$ and $h(x_{v}z{z}^{\prime }{z}^{\prime }z{x}_v)$. By the construction in [11], we know that this only works if $h({\alpha }_1)$ is not the encoding of a valid computation of $A$ or if $h({\alpha }_2)$ either contains $h(z^{\prime })$ or $|h({\alpha }_2)|$ is a unary word over $h(z)$ that is short enough (If $h(y_1)\ne \epsilon$ or $h(y_2)\ne \epsilon$, we can either use $y_1^{\prime }$ or $y_2^{\prime }$ in $\beta$ to obtain parts of $h(\alpha )$, or we also have to rely on some ${\ddot{\beta }}_i$ and ${\widehat{\beta }}_i$ and the same property as before holds). Hence, if and only if there exists some valid computation for $A$, we can find a substitution $h\in H_{{\mathrm{\ell }}_{\alpha }}$ for which $h(\alpha )\notin L_E(\beta ,{\mathrm{\ell }}_{\beta })$. This concludes the sketch for the binary case of the proof of Theorem 8. See Appendix C for a sketch on how to extend this to arbitrary fixed alphabets. As mentioned before, see [27] for a full formal proof of this result. $◀$

Due to the construction in the proof of Theorem 8, the undecidability of the inclusion problem for terminal-free erasing pattern languages immediately follows.

Suppose it was decidable. Then, we could decide whether $L_E(\alpha ,{\mathrm{\ell }}_{\alpha })\subseteq L_E(\beta ,{\mathrm{\ell }}_{\beta })$ and whether $L_E(\beta ,{\mathrm{\ell }}_{\beta })\subseteq L_E(\alpha ,{\mathrm{\ell }}_{\alpha })$ and by that decide if we have $L_E(\alpha ,{\mathrm{\ell }}_{\alpha })=L_E(\beta ,{\mathrm{\ell }}_{\beta })$. That is a contradiction to Theorem 8. $◀$

The second main result of the paper, and the last one regarding patterns with only length constraints, shows that the inclusion problem for terminal-free non-erasing pattern languages with length constraints is also undecidable for all alphabets $\mathrm{\Sigma }$ with $|\mathrm{\Sigma }|>2$. In [32], Saarela has shown this problem to be undecidable for patterns without any constraints in the binary case.

Hence, the undecidability of the inclusion problem for pattern languages with length constraints follows immediately in this case.

In the case of length constraints, a general extension to all alphabet sizes is possible. We obtain the following.

Again, we only give a sketch of the idea and the formal construction used in this proof. The binary case follows by Corollary 11, i.e., the result by Saarela [32]. The general proof idea is based on the construction done by Freydenberger and Bremer [3] for the binary case and significantly adapted in its extension to arbitrary alphabets. As the extension to larger alphabets is strongly based on the construction for the binary case, we give the construction for the binary case here and sketch out the extension to arbitrary alphabets in Appendix D. As for Theorem 8, due to its extensive length, the full formal proof can be found in [27].

The idea is relatively similar to the idea for the proof of Theorem 8 (or the proof in [3]) in that is utilizes a pattern $(\alpha ,{\mathrm{\ell }}_{\alpha })$ in which all words with a specific structure can be obtained, in particular, special encodings of valid computations of the specific universal Turing machine $U$ over any input $I$, as defined in Appendix B, and a pattern $(\beta ,{\mathrm{\ell }}_{\beta })$ from which we can obtain all words that are in $L_{NE}(\alpha ,{\mathrm{\ell }}_{\alpha })$ but these encodings of valid computations. As this result only shows undecidability of the inclusion problem, we do not have the property $L_{NE}(\beta ,{\mathrm{\ell }}_{\beta })\subseteq L_{NE}(\alpha ,{\mathrm{\ell }}_{\alpha })$ and only use the case distinction whether $L_{NE}(\alpha ,{\mathrm{\ell }}_{\alpha })\subseteq L_{NE}(\beta ,{\mathrm{\ell }}_{\beta })$ to decide the emptiness of ${\mathrm{𝚅𝚊𝚕𝙲}}_U(I)$.

We continue with the formal construction used to reduce the emptiness problem of the universal Turing machine $U$ to the inclusion problem of terminal-free non-erasing pattern languages with length constraints in the binary case. After hat, we give a sketch of the idea on why this construction works. For the binary case, we essentially take slight adaptations of the constructed patterns from [3] but swap out any occurrence of the letter $0$ with a new variable $x_0$ and any occurrence of the letter $\mathrm{\#}$ with a new variable $x_{\mathrm{\#}}$ (also similar, to some extend, to the idea in [32]). In that sense, the patterns look very similar to the constructed patterns in [3], but do not contain any terminals. With length constraints, we can restrict the obtainable words in such a way that the inclusion property $L_{NE}(\alpha ,{\mathrm{\ell }}_{\alpha })\subseteq L_{NE}(\beta ,{\mathrm{\ell }}_{\beta })$ decides the emptiness of ${\mathrm{𝚅𝚊𝚕𝙲}}_U(I)$.

First, we construct $(\beta ,{\mathrm{\ell }}_{\beta })$, as the construction of $(\alpha ,{\mathrm{\ell }}_{\alpha })$ is based on it. We define $\beta$ by

for new and independent variables $x_0,x_{\mathrm{\#}},x_a,x_b,x_1,x_2,\mathrm{\dots },x_{\mu +1},r_1,r_2,\mathrm{\dots },r_{\mu +2}\in X$ and terminal-free patterns ${\widehat{\beta }}_1,\widehat{{\beta }_2},\mathrm{\dots },{\widehat{\beta }}_{\mu +1}\in X^{+}$. Notice that $\mu \in \mathbb{N}$ is a number given by the construction in [3]. For all $i\in [\mu +1]$ we say that

for terminal-free patterns ${\gamma }_i,{\delta }_i\in X^{+}$ that are defined later. The length constraints ${\mathrm{\ell }}_{\beta }$ are defined by the system

• $\mathrm{■}$

  $x_0=1$, $x_{\mathrm{\#}}=1$, $x_a+x_b=\mu +2$, and

• $\mathrm{■}$

  $x_i=1$ for all $i\in [\mu +1]$

Let $\tau :{(\mathrm{\Sigma }\times X)}^{\ast }\to X^{\ast }$ be a homomorphism defined by $\tau (0)=x_0$, $\tau (\mathrm{\#})=x_{\mathrm{\#}}$, and $\tau (x)=x$ for all $x\in X$. Then we say that for all $i\in [\mu ]$ we have ${\gamma }_i=\tau ({\gamma }_i^{\prime })$ and ${\delta }_i=\tau ({\delta }_i^{\prime })$ for ${\gamma }_i^{\prime }$ and ${\delta }_i^{\prime }$ being the patterns used in the construction in [3]. The specific construction of each such pattern is not relevant here and for details we refer to [3]. What is important is that we use the same patterns as in [3] but map them to terminal-free patterns that have the variable $x_0$ instead of each occurrence of a terminal symbol $0$ and the variable $x_{\mathrm{\#}}$ instead of each occurrence of $\mathrm{\#}$.

For the missing case of $\mu +1$, we define

for new and independent variables $y_{\mu +1},y_{\mu +1}^{\prime }\in X$ and $I$ being the encoding of the initial configuration of $U$ as in [3]. This will be used to obtain all substitutions $h(\alpha )$ where we have $h(x_0)=h(x_{\mathrm{\#}})$ in $L_{NE}(\beta ,{\mathrm{\ell }}_{\beta })$. Now, we construct $(\alpha ,{\mathrm{\ell }}_{\alpha })$. $\alpha$ is defined by

for some patterns ${\alpha }_1$ and ${\alpha }_2$, $x_0$ and $x_{\mathrm{\#}}$ defined as in $\beta$, $v=x_0{x}_{\mathrm{\#}}{x}_{\mathrm{\#}}{x}_{\mathrm{\#}}{x}_0$ and $t=\psi (r_1{\widehat{\beta }}_1{r}_2\mathrm{\dots }{r}_{\mu +1}{\widehat{\beta }}_{\mu +1}{r}_{\mu +2})$ with $\psi :X^{\ast }\to X^{\ast }$ defined by $\psi (x_0)=x_0$, $\psi (x_{\mathrm{\#}})=x_{\mathrm{\#}}$, and $\psi (x)=x_0$ for all other $x\in \mathrm{var}(\beta )$. We define ${\alpha }_1$ and ${\alpha }_2$ as ${\alpha }_1=\tau ({\alpha }_1^{\prime })$ and ${\alpha }_2=\tau ({\alpha }_2^{\prime })$ where ${\alpha }_1^{\prime }$ and ${\alpha }_2^{\prime }$ are the patterns given in [3, Section 4.4] for the second case.

The most important fact we take from there is that ${\alpha }_1^{\prime }=\mathrm{\#}\mathrm{\#}I\mathrm{\#}\mathrm{\#}x\mathrm{\#}{0}^6{0}^{1}0\mathrm{\#}\mathrm{\#}$ for some new and independent variable $x\in X$ and some encoded initial configuration $I$. By that, we see that $\tau ({\alpha }_1^{\prime })$ starts with $x_{\mathrm{\#}}{x}_{\mathrm{\#}}\tau (I)x_{\mathrm{\#}}{x}_{\mathrm{\#}}$ which is used later on in this adaptation of the proof. The length constraints ${\mathrm{\ell }}_{\alpha }$ are defined by the equations $x_0=1$ and $x_{\mathrm{\#}}=1$. Notice that the $x$ in ${\alpha }_1$ has no length constraint. With that, we can now sketch out why this construction works in the binary case.

Notice, if for some $h\in H_{{\mathrm{\ell }}_{\alpha }}$ we have $h(x_0)\ne h(x_{\mathrm{\#}})$, then we immediately obtain essentially the same construction as in [3] and can rely on their proof that shows that these patterns can be used to decide the emptiness of ${\mathrm{𝚅𝚊𝚕𝙲}}_U(I)$. That leaves us with the case $h(x_0)=h_{(}{x}_{\mathrm{\#}})$. But then, we notice that $h({\alpha }_1)$ starts with a unary word of length at least $|x_{\mathrm{\#}}{x}_{\mathrm{\#}}\tau (I)x_{\mathrm{\#}}{x}_{\mathrm{\#}}|=|I|+4$ that has the form $h({\alpha }_1)=h{(x_{\mathrm{\#}})}^{|I|+4}=h{(x_0)}^{|I|+4}$. So, we can use ${\widehat{\beta }}_{\mu +1}$ to obtain $h(v{x}_0{\alpha }_1{x}_{0}v{x}_0{\alpha }_2{x}_{0}v)$ and use the rest of $(\beta ,{\mathrm{\ell }}_{\beta })$ to obtain the surrounding factors just as in [3]. So, if $h(x_{\mathrm{\#}})=h(x_0)$, then we always have $h(\alpha )\in L_{NE}(\beta ,{\mathrm{\ell }}_{\beta })$. Hence, by the result from [3], there only exists some $h\in H_{{\mathrm{\ell }}_{\alpha }}$ for which we have $h(\alpha )\notin L_{NE}(\beta ,{\mathrm{\ell }}_{\beta })$ if and only if ${\mathrm{𝚅𝚊𝚕𝙲}}_U(I)\ne \mathrm{\varnothing }$, concluding this reduction for the binary case.

To extend this construction to arbitrary alphabets, we can introduce for each additional letter $𝚊\in \mathrm{\Sigma }$ a new variable $x_{𝚊}$ in the patterns $\alpha$ and $\beta$, resulting in variables $x_0,x_{\mathrm{\#}},x_{{𝚊}_1},\mathrm{\dots },x_{{𝚊}_{\sigma }}$ for w.l.o.g. $\mathrm{\Sigma }=\{0,\mathrm{\#},{𝚊}_1,\mathrm{\dots },{𝚊}_{\sigma }\}$. With length constraints, we can restrict the length of each substitution on these variables to $1$. The construction can be extended in such a way that if any two variables of $x_0,x_{\mathrm{\#}},x_{{𝚊}_1},\mathrm{\dots },x_{{𝚊}_{\sigma }}$ are substituted by the same letter, then there always exists some ${\widehat{\beta }}_i$ which can be used to obtain anything obtained in $h(v{x}_0{\alpha }_1{x}_{0}v{x}_0{\alpha }_2{x}_{0}v)$. In a second extension we can ensure that we can also always find some ${\widehat{\beta }}_i$ if any of the letters obtained by $h(x_{{𝚊}_1}\mathrm{\dots }{x}_{{𝚊}_{\sigma }})$ appears later on somewhere in $h({\alpha }_1)$ or $h({\alpha }_2)$. By that, we essentially can only obtain words not in $L_{NE}(\beta ,{\mathrm{\ell }}_{\beta })$, if only the letters obtained in $h(x_{\mathrm{\#}})$ and $h(x_0)$ are used in $h({\alpha }_1)$ and $h({\alpha }_2)$. This restricts us to the same cases as in [3] and allows us to, again, rely on their arguments. As mentioned before, the construction of the extension to arbitrary alphabets is outlined in Appendix D. The full formal proof is given in [27]. $◀$

Whether the equivalence problem of non-erasing pattern languages with length constraints is decidable, is left as an open question with no specific conjecture so far. Interestingly, also in the case of regular constraints, no definite answer for the decidability of this problem could be given, yet (cf. [26]). A summary of the current results can be found in Table 1 at the end of the final discussion.