Siguiente: Estimaciones de la complejidad Un nivel arriba: Presentación de la teoría Anterior: Ejemplos y observaciones

Descripciones auto-delimitadoras

Consideremos la función

$$\overline{\cdot}:\{0,1\}^{<\omega}\rightarrow\{0,1\}^{<\omega}$$

definida inductivamente como sigue:

$$\begin{eqnarray*}x\in \{0,1\}&\Rightarrow& \overline{x}=x1 \\ \begin{array}[t]... ...{<\omega}\end{array} &\Rightarrow& \overline{x}=a0\overline{y} \end{eqnarray*}$$

$\overline{x}$ se obtiene de intercalar un 0 entre cualesquiera dos símbolos de x y finalizar con un 1. La cadena $\pi(x)=\overline{\vert x\vert}\cdot x$ se dice ser la versión autodelimitadora de x. Si la longitud de x es n la longitud de $\pi(x)$ es $n+2\log(n)$. Una cadena de cadenas $\mbox{\bf x}=x_1\cdots x_k$ se codifica yuxtaponiendo a los códifos:

$$\pi(\mbox{\bf x})=\pi(x_1)\cdot \cdots \cdot\pi(x_k).$$