Siguiente: El teorema de Kleene Un nivel arriba: Estructura algebraica de las Anterior: Puntos fijos de ecuaciones

Matrices de expresiones regulares

Una matriz de expresiones regulares de m renglones y n columnas es un arreglo $\mbox{\bf A}=\left(A_{ij}\right)_{1\leq i\leq m}^{1\leq j\leq n}$ tal que $\forall i,j: A_{ij}\in\mbox{\it ER\/}(\Sigma)$. Denotemos por $\mbox{\it ER\/}(\Sigma)^{m\times n}$ a la clase de matrices de expresiones regulares de m renglones y n columnas. Si $\mbox{\bf A},\mbox{\bf B}\in\mbox{\it ER\/}(\Sigma)^{m\times n}$ su suma es la matriz $\mbox{\bf C}\in\mbox{\it ER\/}(\Sigma)^{m\times n}$ tal que $\forall i,j: C_{ij}=A_{ij}+B_{ij}$. Si $\mbox{\bf B}\in\mbox{\it ER\/}(\Sigma)^{m\times n}$ y $A\in\mbox{\it ER\/}(\Sigma)$ el producto por un escalar por la izquierda $A\mbox{\bf B}$ es la matriz $\mbox{\bf C}\in\mbox{\it ER\/}(\Sigma)^{m\times n}$ tal que $\forall i,j: C_{ij}=A\cdot B_{ij}$. Simétricamente, el producto por la derecha $\mbox{\bf B}A$ es la matriz $\mbox{\bf C}\in\mbox{\it ER\/}(\Sigma)^{m\times n}$ tal que $\forall i,j: C_{ij}=B_{ij}\cdot A$. También de manera convencional, definimos el producto de dos matrices $\mbox{\bf A}\in\mbox{\it ER\/}(\Sigma)^{m\times n}$ y $\mbox{\bf B}\in\mbox{\it ER\/}(\Sigma)^{n\times p}$ como la matriz $\mbox{\bf C}\in\mbox{\it ER\/}(\Sigma)^{m\times p}$ tal que $\forall i,j: C_{ij}={\displaystyle \sum_{k=1}^nA_{ik}\cdot B_{kj}}$. Con estas operaciones las matrices cuadradas $\mbox{\it ER\/}(\Sigma)^{n\times n}$ poseen una estructura de semianillo (lo único que les falta para ser un anillo son inversos aditivos) no-conmutativo. La unidad aditiva es la matriz cero $\mbox{\bf0}^{n\times n}$ y la unidad multiplicativa es la matriz identidad $\mbox{\bf Id}_n=\mbox{\it diag\/}(\mbox{\bf 1},\ldots,\mbox{\bf 1})$. Las operaciones matriciales son congruentes con ``particiones por bloques'', es decir, si se parte a dos matrices $\mbox{\bf A},\mbox{\bf B}\in\mbox{\it ER\/}(\Sigma)^{n\times n}$ como

$$\begin{array}{ccc} \mbox{\bf A}=\left[\begin{array}{cc} \mb... ... B}_{21} & \mbox{\bf B}_{22} \end{array}\right] \end{array}$$

donde bloques con mismos índices ij son de mismos tamaños, entonces

$$\begin{eqnarray*}\mbox{\bf A}+\mbox{\bf B} &=& \left[\begin{array}{cc} \mbox{\b... ...}_{12}+\mbox{\bf A}_{22}\mbox{\bf B}_{22} \end{array}\right] \end{eqnarray*}$$

Dadas dos matrices $\mbox{\bf A},\mbox{\bf B}\in\mbox{\it ER\/}(\Sigma)^{n\times n}$, diremos que $\mbox{\bf A}\leq \mbox{\bf B}$ si $\forall i,j\leq n:\ A_{ij}\leq B_{ij}$. Diremos también que una matriz $\mbox{\bf A}$ posee la CPV si $\mbox{\bf Id}\leq \mbox{\bf A}$. Ahora la operación ``estrella'' de matrices ha de generalizar la operación ``estrella'' de las expresiones regulares. Consecuentemente, se ha de definir de manera que

• se satisfaga la ecuación $\mbox{\bf A}^*=\mbox{\bf Id}+\mbox{\bf A}\mbox{\bf A}^*$, y
• la solución de la ecuación $\mbox{\bf X}=\mbox{\bf A}\mbox{\bf X}+\mbox{\bf B}$ sea $\mbox{\bf X}=\mbox{\bf A}^*\mbox{\bf B}$, siempre que $\mbox{\bf A}$ no posea la CPV.

Para esto, supongamos primero que ya se haya construido tal operación ``estrella''. Denotemos por $\mbox{\bf Y}=\mbox{\bf A}^*$ a la ``estrella'' de $\mbox{\bf A}$. Si consideramos particiones de tamaños similares

$$\begin{array}{ccccc} \mbox{\bf A}=\left[\begin{array}{cc} \... ...\mbox{\bf0} & \mbox{\bf Id}'' \end{array}\right] \end{array}$$

de la ecuación $\mbox{\bf A}^*=\mbox{\bf Id}+\mbox{\bf A}\mbox{\bf A}^*$ resultará

    

$$\mbox{\bf Y}_{11} \mbox{\bf A}_{11}\mbox{\bf Y}_{11} + \mbox{\bf A}_{12}\mbox{\bf Y}_{21} + \mbox{\bf Id}'$$ = (28)

$$\mbox{\bf Y}_{12} \mbox{\bf A}_{11}\mbox{\bf Y}_{12} + \mbox{\bf A}_{12}\mbox{\bf Y}_{22}$$ = (29)

$$\mbox{\bf Y}_{21} \mbox{\bf A}_{21}\mbox{\bf Y}_{11} + \mbox{\bf A}_{22}\mbox{\bf Y}_{21}$$ = (30)

$$\mbox{\bf Y}_{22} \mbox{\bf A}_{21}\mbox{\bf Y}_{12} + \mbox{\bf A}_{22}\mbox{\bf Y}_{22} + \mbox{\bf Id}''$$ = (31)

De la ecuación (4.19) resulta:

$$\mbox{\bf Y}_{21} =\mbox{\bf A}_{22}^*\mbox{\bf A}_{21}\mbox{\bf Y}_{11}.$$ (32)

De la ecuación (4.18) resulta:

$$\mbox{\bf Y}_{12} =\mbox{\bf A}_{11}^*\mbox{\bf A}_{12}\mbox{\bf Y}_{22}$$ (33)

Al sustituir (4.21) en (4.17) obtenemos

$$\mbox{\bf Y}_{11} =\left(\mbox{\bf A}_{11}+\mbox{\bf A}_{12}\... ...22}^*\mbox{\bf A}_{21}\right) \mbox{\bf Y}_{11}+ \mbox{\bf Id}'$$

y en consecuencia

$$\mbox{\bf Y}_{11} = \left(\mbox{\bf A}_{11}+\mbox{\bf A}_{12}\mbox{\bf A}_{22}^*\mbox{\bf A}_{21}\right)^*.$$ (34)

Al sustituir (4.22) en (4.20) obtenemos

$$\mbox{\bf Y}_{22} = \left(\mbox{\bf A}_{22}+\mbox{\bf A}_{21}... ...11}^*\mbox{\bf A}_{12}\right) \mbox{\bf Y}_{22}+\mbox{\bf Id}''$$

y en consecuencia

$$\mbox{\bf Y}_{22} = \left(\mbox{\bf A}_{22}+\mbox{\bf A}_{21}\mbox{\bf A}_{11}^*\mbox{\bf A}_{12}\right)^*.$$ (35)

De las ecuaciones (4.24), (4.23), (4.22) y (4.21) obtenemos

$$\mbox{\bf Y}=\mbox{\bf A}^*=\left[\begin{array}{rr} \left(\m... ...bf A}_{11}^*\mbox{\bf A}_{12}\right)^* \end{array}\right].$$ (36)

Ahora bien, de la identidad (X+Y)^*=(X^*Y)^*X^* obtenemos la expresión equivalente

$$\mbox{\bf A}^*=\left[\begin{array}{rr} \left(\mbox{\bf A}_{1... ...ox{\bf A}_{12}\right)^*\mbox{\bf A}_{22}^* \end{array}\right].$$

También de la identidad (XY)^*X=X(YX)^* obtenemos

$$\begin{eqnarray*}\mbox{\bf A}_{11}^*\mbox{\bf A}_{12}\left(\mbox{\bf A}_{22}^*\m... ...*\mbox{\bf A}_{12}\right)^*\mbox{\bf A}_{22}^*\mbox{\bf A}_{21} \end{eqnarray*}$$

y por tanto,

$$\mbox{\bf A}^*=\left[\begin{array}{ll} \left(\mbox{\bf A}_{1... ...\bf A}_{12}\right)^*\mbox{\bf A}_{22}^* \end{array}\right].$$ (37)

Las ecuaciones (4.25) y (4.26) dan sendos métodos de cálculo de la matriz $\mbox{\bf A}^*$. Así, por ejemplo, de acuerdo con la ecuación (4.26), dada una matriz $\mbox{\bf A}\in\left(\mbox{\it ER\/}(\Sigma)\right)^{n\times n}$ y una partición de ella por bloques

$$\mbox{\bf A}=\left[\begin{array}{cc} \mbox{\bf A}_{11} & \mb... ...\\ \mbox{\bf A}_{21} & \mbox{\bf A}_{22} \end{array}\right]$$

entonces al hacer

$$\begin{array}{rcl@{\; , \:}rcl} \mbox{\bf C}_{11} &=& \mbox{... ...bf B}_{22} &=& \mbox{\bf D}_{22}\mbox{\bf C}_{22} \end{array}$$

hemos de tener que

$$\mbox{\bf A}^*=\left[\begin{array}{ll} \mbox{\bf B}_{11} & \... ..._{22}\mbox{\bf B}_{21} & \mbox{\bf B}_{22} \end{array}\right]$$

Los cálculos anteriores pueden realizarse para cualquier partición de la matriz $\mbox{\bf A}$ por bloques. Sin embargo, diversas particiones serán más eficientes respecto a otras. Como un primer ejemplo, supongamos que formamos bloques ``quitando'' el último renglón y la última columna. En otras palabras, supongamos

$$\begin{eqnarray*}\mbox{\bf A}_{11} &\in& \left(\mbox{\it ER\/}(\Sigma)\right)^{(... ...A}_{22} &\in& \left(\mbox{\it ER\/}(\Sigma)\right)^{1\times 1} \end{eqnarray*}$$

Sea T(n) el número de potencias ``estrellas'' escalares necesarias para calcular la potencia ``estrella'' de $\mbox{\bf A}$. Siguiendo las relaciones anteriores, necesitamos calcular 2 potencias ``estrellas'' de matrices $(n-1)\times (n-1)$, las de las matrices $\mbox{\bf A}_{11}$ y $\mbox{\bf C}_{11}\mbox{\bf B}_{12}\mbox{\bf A}_{21}$, y dos de matrices $1\times 1$, las de las matrices $\mbox{\bf A}_{22}$ y $\mbox{\bf C}_{22}\mbox{\bf B}_{21}\mbox{\bf A}_{12}$. Por tanto,

$$\begin{eqnarray*}\forall n>0:\ T(n) &=& 2T(n-1)+2 \\ T(1) &=& 1 \end{eqnarray*}$$

Al resolver la recurrencia anterior obtenemos como solución

$$T(n)=3\cdot 2^{n-1}-2,$$

y consecuentemente T(n)=O(2ⁿ). Ahora, como un segundo ejemplo, supongamos que n=2^k es una potencia de 2. En este caso, de acuerdo con las relaciones anteriores, para calcular la potencia ``estrella'' de $\mbox{\bf A}$ hay que calcular 4 potencias ``estrellas'' de matrices $\frac{n}{2}\times \frac{n}{2}$. Por tanto,

$$T(2^k)=T(n)=4T\left(\frac{n}{2}\right)=4T(2^{k-1}).$$

Esta vez, la recurrencia tiene solución

$$T(n)=4^k=\left(2^k\right)^2=n^2.$$

Ya que $\lim_{n\rightarrow+\infty}\frac{n^2}{2^n}=0$ vemos que es mucho más conveniente introducir particiones por ``medias'' matrices que quitando un renglón y una columna a la vez.


Como en el caso ``escalar'' tenemos que se cumple el siguiente

Lema 3.2   Si $\mbox{\bf A}\in\left(\mbox{\it ER\/}(\Sigma)\right)^{n\times n}$ y $\mbox{\bf b}\in\left(\mbox{\it ER\/}(\Sigma)\right)^{n}$ entonces la mínima solución de la ecuación $\mbox{\bf X}=\mbox{\bf A}\mbox{\bf X}+\mbox{\bf b}$ es $\mbox{\bf X}=\mbox{\bf A}^*\mbox{\bf b}$. Más aún, si $\mbox{\bf A}$ no posee la CPV entonces la solución mínima es la única solución.

Ejemplo: Para una matriz $\mbox{\bf A}_2\in\mbox{\it ER\/}(\Sigma)^{2\times 2}$,

$$\mbox{\bf A}_2=\left[\begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array}\right]$$

se tiene, aplicando el algoritmo de cálculo de la operación ``estrella'' en matrices, que

$$\mbox{\bf A}_2^*=\left[\begin{array}{rr} \left[a_{11}^* a_{1... ...a_{21} a_{11}^* a_{12}\right]^* a_{22}^* \end{array}\right]$$ (38)

Ahora bien para una matriz $\mbox{\bf A}_4\in\mbox{\it ER\/}(\Sigma)^{4\times 4}$,

$$\mbox{\bf A}_4=\left[\begin{array}{cccc} a_{11} & a_{12} & ... ...34} \\ a_{41} & a_{42} & a_{43} & a_{44} \end{array}\right]$$

es necesario reiterar desde un segundo nivel el procedimiento descrito de la operación ``estrella'' en matrices. En este caso tendremos que

$$\mbox{\bf A}_4^*=\left[\begin{array}{cccc} b_{11} & b_{12} ... ...34} \\ b_{41} & b_{42} & b_{43} & b_{44} \end{array}\right]$$

donde al hacer

$$\begin{array}{lclcl} \forall i,j \leq 4 &:& \ f_{ ij} &=& a_... ...w_{ijklm} &=& a_{ij} u_{jklm} + f_{ij}^* u_{iklm} \end{array}$$

resulta, por ejemplo,

$$\begin{eqnarray*}b_{11} &=& w_{12234} w_{21234}^* a_{21} a_{11}^* + \left[w... ..._{21234}^* w_{21134} \right]^* w_{12134}^* f_{12}^* a_{11}^* \end{eqnarray*}$$

y los demás términos b_ij tienen expresiones similares, en cuanto a la complejidad de sus expresiones.
Siguiente: El teorema de Kleene Un nivel arriba: Estructura algebraica de las Anterior: Puntos fijos de ecuaciones