Demostrar que la PCP unitaria es decidible.

Question

Demostrar que el PCP unitario (Problema de Post Correspondencia donde $\vert \Sigma \vert = 1$ ) es decidible.

Caso $1$ : Si una tupla $(x_i, y_i)$ con $\vert x_i\vert = \vert y_i\vert$ existe, entonces la respuesta es "sí" y la prueba es trivial.

Caso $2$ : Si una tupla $(x_i, y_i)$ con $\vert x_i\vert > \vert y_i\vert$ y una tupla $(x_j, y_j)$ con $\vert x_j\vert < \vert y_j\vert$ existe, entonces la respuesta es "sí". Dejemos que $a:= \vert x_i\vert - \vert y_i\vert$ y $b:= \vert y_j\vert - \vert x_j\vert$ . Entonces, lo consigues:

\begin{align} \vert x_i^b \cdot x_j^a\vert &= b \cdot \vert x_i\vert + a \cdot \vert x_j\vert \\ &= (\vert y_j\vert - \vert x_j\vert) \cdot \vert x_i\vert + (\vert x_i\vert - \vert y_i\vert) \cdot \vert x_j\vert \\ &= \vert y_i\vert \cdot \vert x_i\vert - \vert x_j\vert \cdot \vert y_i\vert \\ &= (\vert y_j\vert - \vert x_j\vert) \cdot \vert y_i \vert + (\vert x_i\vert - \vert y_i\vert) \cdot \vert y_j \vert \\ &= b \cdot \vert y_i \vert + a \cdot \vert y_j \vert \\ &= \vert y_i^b \cdot y_j^a\vert \end{align}

Caso $3$ : Si cada tupla que tenemos que $\vert x_i \vert > \vert y_i\vert$ o $\vert x_i \vert < \vert y_i\vert$ Entonces la respuesta es "no" porque entonces una de las cuerdas es siempre más larga que la otra y no habrá solución.

Tengo problemas con el caso $2$ porque no puedo entender cómo pasamos del lado izquierdo al derecho.

Answer 1

Tenemos que demostrar que $|x_i^bx_j^a| = |y_i^by_j^a|$ .

Aquí, $s_1s_2$ significa la concatenación de las dos cadenas $s_1$ y $s_2$ y $s^k$ significa concatenar $k$ veces la cadena $s$ con ella misma: $\underbrace{ss\ldots s}_{k~\text{times}}$

Además, tenga en cuenta que $(*)~a=|x_i|−|y_i|\text{and}b=|y_j|−|x_j|$ .

Así que tenemos: \begin{align} |x_i^bx_j^a| &= |x_i^b| + |x_j^a| & \text{(string concatenation)}\\ &=b|x_i|+ a|x_j| &\text{(string concatenation)}\\ &=(|y_j|−|x_j|)|x_i|+ (|x_i|−|y_i|)|x_j| &\text{(using the equations in}~(*))\\ &= |y_j||x_i| - |y_i||x_j| &\text{(distributivity and deletion of opposites)}\\ &= |y_j||x_i| - |y_i||y_j| + |y_i||y_j| - |y_i||x_j| &\text{(introduction of opposites)}\\ &= (|x_i| - |y_i|)|y_j| + (|y_j| - |x_j|)|y_i|&\text{(factorization)}\\ &= a|y_j| + b|y_i| &\text{(using the equations in}~(*))\\ &= |y_j^a| + |y_i^b| = |y_j^ay_i^b| & \text{(string concatenation)} \end{align}