next up previous
Next: Bibliography Up: Modificaciones al capítulo 5 Previous: Unión de algoritmos

La función sucesor

Podemos describir una máquina de computación basada en mosaicos con el esquema de la tabla [*] de la página [*] que describa una función sucesor. Hay muchas otras posibilidades de interpretar una función sucesor, esta es solo una de ellas.

Vamos a describir con palabras el comportamiento esperado de este procedimiento que vamos a denotar por $ \mathfrak{S}$ . Este procedimiento comienza con un triángulo $ t_3$ y continúa al concatenar gráficamente las palabras asociadas por la diagonal, por el lado izquierdo y por la parte superior, en ese orden.

A partir de que el orden del cubrimiento sea mayor que uno, se deben de agregar las palabras en el siguiente orden:

  1. Recorrer todos los triángulos de la frontera del cubrimiento, empezando con el triángulo cuya célula origen es el origen del recorrido del cubrimiento (página [*]) y seguir la frontera en el sentido de las manecillas del reloj.

  2. Para cada triángulo de la frontera, aplicar una regla de agregación por cada lado, empezando por la diagonal, el lado izquierdo y el lado superior, mientras sea posible. Llamaremos $ n_{app}$ al número de veces que se han aplicado las reglas de agregación. Un lado de un triángulo es candidato a tomarse en cuenta por las reglas de agregación si aún no tiene alguna célula concatenada gráficamente.

Esta función sucesor toma un cubrimiento $ X\in\Phi^{(m)}$ de orden $ \vert\vert X\vert\vert=m$ , luego se genera un nuevo cubrimiento $ \mathfrak{A}(X)$ al aplicar sobre $ X$ el algoritmo $ \mathfrak{A}$ , definido con el alfabeto y el esquema del cuadro [*] en la página [*]; el orden del resultado de $ \mathfrak{A}(X)$ aumenta en 2 unidades por cada una de las $ n_{app}$ aplicaciones de las reglas de agregación. El procedimiento $ \mathfrak{S}$ es bastante regular en la cantidad de aplicaciones. El número de aplicaciones $ n_{app}$ aumenta de acuerdo a la serie $ n_{app}=1,3,6,9,12, ...$

Figure 14: Aplicación de la función sucesor en: (a) $ Succ(t_3)$ , (b) $ Succ^2(t_3)$ , (c) $ Succ^3(t_3)$ , (d) $ Succ^4(t_3)$
Image EtherHistory

De esta manera podemos definir la armadura de la función $ Succ$ con dominio e imagen en el conjunto de cubrimientos como: $ Succ:\Phi^{(m)}\to \Phi^{(m+6n_{app})}$ para algún número entero $ n_{app}\geq 0$ . Entonces la función está definida como:

$\displaystyle Succ(X)=\mathfrak{S}(X)=\mathfrak{A}(t_{3_\kappa})\;\forall\;t_{3_\kappa}\in \hat{X}$ (3)

Así

$\displaystyle Succ^n(X)=\left\{\begin{array}{ll} t_3 & \textrm{si }n=0\\ \mathf...
... & \textrm{si }n=1\\ Succ(Succ^{n-1}(X)) & \textrm{si }n>1\\ \end{array}\right.$ (4)

La interpretación de sucesor se da en la longitud de cada lado del triángulo aparente que resulta, véase la figura 14. En esta figura, se han hecho 4 aplicaciones de la operación sucesor, dando como resultado triángulos de lados con longitudes 1 en la parte (a); 2 en la parte (b); 3 en la parte (c); y 4 en la parte (d).


next up previous
Next: Bibliography Up: Modificaciones al capítulo 5 Previous: Unión de algoritmos
Abdiel Caceres-Gonzalez Jan-26-2005