next up previous contents
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{displaymath}\begin{array}{ccc}
\mbox{\bf A}=\left[\begin{array}{cc}
\mb...
... B}_{21} & \mbox{\bf B}_{22}
\end{array}\right]
\end{array}\end{displaymath}

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 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{displaymath}\begin{array}{ccccc}
\mbox{\bf A}=\left[\begin{array}{cc}
\...
...\mbox{\bf0} & \mbox{\bf Id}''
\end{array}\right]
\end{array}\end{displaymath}

de la ecuación $\mbox{\bf A}^*=\mbox{\bf Id}+\mbox{\bf A}\mbox{\bf A}^*$ resultará
    
$\displaystyle \mbox{\bf Y}_{11}$ = $\displaystyle \mbox{\bf A}_{11}\mbox{\bf Y}_{11} + \mbox{\bf A}_{12}\mbox{\bf Y}_{21} + \mbox{\bf Id}'$ (28)
$\displaystyle \mbox{\bf Y}_{12}$ = $\displaystyle \mbox{\bf A}_{11}\mbox{\bf Y}_{12} + \mbox{\bf A}_{12}\mbox{\bf Y}_{22}$ (29)
$\displaystyle \mbox{\bf Y}_{21}$ = $\displaystyle \mbox{\bf A}_{21}\mbox{\bf Y}_{11} + \mbox{\bf A}_{22}\mbox{\bf Y}_{21}$ (30)
$\displaystyle \mbox{\bf Y}_{22}$ = $\displaystyle \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:

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

De la ecuación (4.18) resulta:

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

Al sustituir (4.21) en (4.17) obtenemos

\begin{displaymath}\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}'\end{displaymath}

y en consecuencia

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

Al sustituir (4.22) en (4.20) obtenemos

\begin{displaymath}\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}''\end{displaymath}

y en consecuencia

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

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

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

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

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

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,

 \begin{displaymath}\mbox{\bf A}^*=\left[\begin{array}{ll}
\left(\mbox{\bf A}_{1...
...\bf A}_{12}\right)^*\mbox{\bf A}_{22}^*
\end{array}\right].
\end{displaymath} (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

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

entonces al hacer

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

hemos de tener que

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




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

\begin{displaymath}T(n)=3\cdot 2^{n-1}-2,\end{displaymath}

y consecuentemente T(n)=O(2n). Ahora, como un segundo ejemplo, supongamos que n=2k 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,

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

Esta vez, la recurrencia tiene solución

\begin{displaymath}T(n)=4^k=\left(2^k\right)^2=n^2.\end{displaymath}

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}$,

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

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

 \begin{displaymath}\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]
\end{displaymath} (38)

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

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

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

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

donde al hacer

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

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 bij tienen expresiones similares, en cuanto a la complejidad de sus expresiones.
next up previous contents
Siguiente: El teorema de Kleene Un nivel arriba: Estructura algebraica de las Anterior: Puntos fijos de ecuaciones
Guillermo Morales-Luna
2000-06-27