% P�eklad: Stanislav Opichal (INF95)
% Ne�pln� p�eklady a nepochopen� ��sti jsou ozna�eny *** pro snadn�j�� vyhled�n�
\documentclass{article}

\usepackage{amsmath,amsthm}

\sloppy

%%\newcounter{xx}
%%\setcounter{xx}{\value{subsection}}
%%\newenvironment{definition}[1][Definice]{{\bf \thesubsection #1}}{\stepcounter{xx}}

\newtheorem{lema}{Lema}[section]
\newtheorem{theorem}{Teor�m}[section]

\theoremstyle{definition}
\newtheorem{definice}{Definice}[subsection]
\newtheorem{priklad}{P��klad}[subsection]

\newcommand{\K}     {\mathcal{K}}
\newcommand{\RegS}  {\mathbf{Reg_{\Sigma}}}
\newcommand{\RExpS} {\mathbf{RExp_{\Sigma}}}

\begin{document}

\section{Nejkrat�� cesta a tranzitivn� uz�v�r}

\subsection{Nejkrat�� cesta pro definovan� za��tek}

Nech� $G = (V,E)$ je neorientovan� graf a $\ell$ je funkce
p�i�azuj�c� ka�d� hran� grafu nez�pornou d�lku. Roz�i�me $\ell$ do
b�ze $V \times V$ tak �e definujeme $\ell(v,v) = 0$ a $\ell(u,v) =
\infty$ pokud $(u,v) \notin E$. Definujme d�lku\footnote{V tomto
kontextu se term�ny "d�lka" a "nejkrat��" pou�it� pro cestu
vztahuj� k $\ell$ a ne k po�tu hran v cest�.} cesty $p = e_1e_2
\dots e_n$ jako $\ell(p) = \sum _{i=0}^n \ell(e_i)$. Pro $u,v \in
V$, definujeme $vzd�lenost$ $d(u,v)$ $u$ a $v$ jako d�lku
nejkrat�� cesty z $u$ do $v$ nebo $\infty$ kdy� takov� cesta
neexistuje. Probl�mem nalezen� nejkrat�� cesty pro definovan�
za��tek je naj�t pro v�echny uzly $s \in V$ hodnotu $d(s,u)$ pro
v�echny ostatn� uzly $u$ grafu $G$.

Pokud je graf neohodnocen� (tzn. v�echny hrany maj� d�lku 1),
m��eme pak probl�m �e�it pou�it�m BFS*** v line�rn� �ase. Pro v�ce
obecn� p��pad je tu algoritmus podle Dijkstra \cite{Dijkstra}.
Pozd�ji si uk�eme implementaci pomuc� Fibonacciho hald s
obt�nost� $O(m+n \log n)$. Tento algoritmus je Greedyho typu:
vytv��� mno�inu $X$ uzel po uzlu tak, �e v�dy p�id� ten nejbl힚�
k $X$.

\bigskip
\fbox{
\begin{minipage}{300pt}
    {\bf Algoritmus \thesubsection\ (Dijkstr�v) }
    \begin{tabbing}
        $X:=\{s\};$ \\
        $D(s):=0;$ \\
        pro v�echny $u \in V - \{s\}$ d�lej \\
        dokud \=$X \ne V$ d�lej \kill
        \> $D(u):= \ell(s,u);$ \\
        dokud \=$X \ne V$ d�lej \\
        \> nech� $u \in V - X$ takov�, �e $D(u)$ je minim�ln�; \\
        \> $X := X \cup \{u\};$ \\
        \> pro v�e\=chny hrany $(u,v)$ s $v \in V - X$ d�lej \\
        \> \> $D(v) := \min( D(v), D(u) + \ell(u,v)$ \\
        dokud konec
    \end{tabbing}
\end{minipage}
}
\bigskip

Po proveden� je $D(u)$ rovno $d(s,u)$. Spr�vnost tohoto algoritmu
se d� ov��it d�kazem zachov�n� platnosti n�sleduj�c�ch invariant�
v pr�b�hu cyklu algoritmu:
\begin{itemize}
    \item pro v�echna u je $D(u)$ vzd�lenost $s$ a $u$ nejkrat��
    cestou vedena pouze p�es uzly v $X$
    \item pro v�echny $u \in X$ a $v \notin X$ je $D(u) \leq D(v)$
\end{itemize}

\subsection{Reflexivn� tranzitivn� uz�v�r}

Ozna�me $E$ inciden�n� matic� orientovan�ho grafu $G = (V,E)$.
Pomoc� booleovsk�ho n�soben� matic m� matice $E^2$ jedni�ky na
pozic�ch uv pokud je cesta z uzlu $u$ do $v$ d�lky 2. Tzn. pokud
existuje uzel $w$ tak, �e $(u,v), (w,v) \in E$. Podobn� m��eme
indukc� pro $k$ dok�zat �e $(E^k)_{uv} = 1$ pokud je cesta z uzlu
$u$ do $v$ d�lky $k$.

\par Reflexivn� tranzitivn� uz�v�r $G$ je
\begin{eqnarray}
    E^* & = & I \vee E \vee E^2 \vee \dots \nonumber \\
    & = &  I \vee E \vee E^2 \vee \dots E^{n-1} \nonumber \\
    & = &  (I \vee E)^{n-1}.  \nonumber
\end{eqnarray}

Sou�ty jsou kone�n� proto�e jestli�e existuje cesta spojuj�c� $u$
a $v$, potom je sou�et roven maxim�ln� $n - 1$.
\par M�jme dv� $n \times n$ booleovsk� matice n�sobiteln� v �ase
$M(n)$. Pak $E^* = (I \vee E)^{n-1}$ m��eme vypo��tat v �ase
$O(M(n) \log n)$ pomoc� umoc�ov�n� matice $E$ $\log n$ kr�t.
Pozd�j� si uk�eme, jak vypo��tat $E^*$ v �ase $O(M(n))$. Opa�n�,
jestli�e existuje algoritmus pro v�po�et $E^*$ v �ase $T(n)$, pak
$M(n)$ je $O(T(n))$ (pod podm�nkou, �e $M(3n)$ je $O(M(n))$): k
vyn�soben� matic $A$ a $B$ je um�st�me do $3n \times 3n$ matice
pak jej� reflexivn� tranzitivn� uz�v�r je:
\begin{equation}
    \left[ \begin{matrix}
        0 & A & 0 \cr 0 & 0 & B \cr 0 & 0 & 0
    \end{matrix} \right]^* =
    \left[ \begin{matrix}
        I & A & AB \cr 0 & I & B \cr 0 & 0 & I
    \end{matrix} \right] \nonumber
\end{equation}
Sou�in $AB$ pak najdeme v horn�m prav�m bloku v�sledn� matice.

Zde je algorimus pro v�po�et $E^*$ v �ase $M(u)$ metodou rozd�l a
panuj.

\bigskip
\fbox{
\begin{minipage}{300pt}
\label{Alg_ReflTransClosure}
    {\bf Algoritmus \thesubsection\ (Reflexivn� tranzitivn�
    uz�v�r) }
    \begin{enumerate}
        \item Rozd�l�me $E$ do �ty� podmatic $A, B, C, D$ zhuba velikost�
        $\frac{n}{2} \times \frac{n}{2}$ tak, �e $A$ a $D$ jsou �tvercov�:
            $$ E = \left[
                \begin{tabular}{c|c}
                $A$ & $B$ \\ \hline
                $C$ & $D$ \\
                \end{tabular}
            \right] $$
        \item Rekurzivn� po��t�me $D^*$. Po��t�me:
            $$ F = A + BD^*C. $$
            Rekurzivn� po��t�me $F^*$
        \item Pak:
            $$ E^* = \left[
                \begin{tabular}{c|c}
                $F^*$ & $F^*BD^*$ \\ \hline
                $D^*CF^*$ & $D^* +D^*CF^*BD^*$ \\
                \end{tabular}
            \right] $$
    \end{enumerate}
\end{minipage}
}
\bigskip

Rozd�lujeme mno�inu uzl� do dvou disjuktn�ch mno�in $U$ a $V$, kde
$A$ reprezentuje hrany z $U$ do $U$, $B$ reprezentuje hrany z $U$
do $V$, $C$ reprezentuje hrany z $V$ do $U$ a $D$ reprezentuje
hrany z $V$ do $V$. Rekurzivn� po��t�me reflexivn� tranzitivn�
uz�v�r na t�chto mno�in�ch a tyto informace pou��v�me k ur�en�
reflexivn�ho tranzitivn�ho uz�v�ru $E$. V�imn�me si, �e po��t�me
dva reflexivn� tranzitivn� uz�v�ry, n�kolikr�t n�sob�me a s��t�me
matice.***

$$T(n) = 2T(\frac{n}{2}) + cM(\frac{n}{2}) + d(\frac{n}{2})^2$$

kde $c$ a $d$ jsou konstanty. Za p�edpokladu, �e $M(2n) \geq
4M(n)$, je �e�en� t�to rekurze obt�nosti $O(M(n))$.

\subsection{Nejkrat�� cesta pro v�echny p�ry}

Ozna�me $E$ inciden�n� matic� ohodnocen�ho orientovan�ho grafu.
Nahra�me jedni�ky v matici vahami p��slu�ej�c�ch hran a nuly
nahra�me nekone�nem ($\infty$). Pou�ijeme algorimus
\ref{Alg_ReflTransClosure} pro v�po�et $E^*$, a� na to, �e
pou�ijeme + m�sto $\wedge$ a min m�sto $\vee$. P��t� si uk�eme,
�e toto �e�� probl�m nalezen� nejkrat�� cesty pro v�echny p�ry.

\section{Kleenovy algebry}

P�edpokl�dejme bin�rn� relaci na $n$ �lenn� mno�in�
reprezentovanou $n \times n$ booleovskou matic� $E$. V minul�
kapitole jsme si uk�zali jak spo��tat reflexivn� tranzitivn�
uz�v�r matice $E$ pomoc� metody rozd�l a panuj n�sledovn�:
rozd�l�me $E$ do �ty� podmatic $A, B, C, D$ zhuba velikost�
$\frac{n}{2} \times \frac{n}{2}$ tak, �e $A$ a $D$ jsou �tvercov�:
 $$ E = \left[
    \begin{tabular}{c|c}
      $A$ & $B$ \\ \hline
      $C$ & $D$ \\
    \end{tabular}
 \right] $$
Indukc� pak po��t�me matice $D^*$, $F = A + BD^*C$ a $F^*$. Pak
m�me:
\begin{equation}
\label{eq:1}
    E^* = \left[
        \begin{tabular}{c|c}
        $F^*$ & $F^*BD^*$ \\ \hline
        $D^*CF^*$ & $D^* +D^*CF^*BD^*$ \\
        \end{tabular}
    \right]
\end{equation}
Dok�eme, �e matice $E^*$ jak je v (\ref{eq:1}) definovan� je
opravdu reflexivn� tranzitivn� uz�v�r $E$. D�kaz budeme
konstruovat v�ce abtraktn� cestou tak, abychom jej mohli pou��t i
d�le. Na p��klad budeme schopni stejn�m obecn�m algoritmem
spo��tat d�lky nejkrat��ch cest pro v�echny p�ry uzl� v
ohodnocen�m orientovan�m grafu, a to pouze zm�nou interpretace
z�kladn�ch operac�. Jak jsme p�i�li na v�razy ve vztahu
(\ref{eq:1})? Nejl�pe si to m��eme p�ibl�it n�sledovn�: m�jme
kone�n� deterministick� automat nad abecedou $\sum = \{a,b,c,d\}$
se stavy $s,t$ a pravidly $s \xrightarrow{a} s, s \xrightarrow{b}
 t, t \xrightarrow{c} s, t \xrightarrow{d} t$:

\begin{center}
\begin{picture}(80,35)(0,0)
    \put(0,15){  \circle{20} }
    \put(10,15){ \circle*{3} }
    \put(50,15){ \oval(80,20)[l] }
    \put(50,15){ \oval(20,20)[r] }
    \put(60,15){ \circle*{3} }
    \put(70,15){ \circle{20} }
    \put(8,24){ \vector(1,-4){2} }
    \put(12,6){ \vector(-1,4){2} }
    \put(58,24){ \vector(1,-4){2} }
    \put(62,5){ \vector(-1,4){2} }
    \put(-16,12){ $a$ }
    \put(13,12){ $s$ }
    \put(35,26){ $b$ }
    \put(35,0){ $c$ }
    \put(54,12){ $t$ }
    \put(81,12){ $d$ }
\end{picture}
\end{center}

Pro ka�d� p�r stav� $u, v$ uva�ujme mno�inu vstupn�ch �et�zc�
$\sum^*$ pot�ebn�ch pro p�echod ze stavu $u$ do stavu $v$. Ka�d�
takov� mno�ina je regul�rn� podmno�inou $\sum^*$ a je
reprezentov�na regul�rn�m v�razem objevuj�c�m se ve vztahu
(\ref{eq:1}):
\begin{eqnarray}
    s \rightarrow s &:& f^* \nonumber \\
    s \rightarrow t &:& f^*bd^* \nonumber \\
    t \rightarrow s &:& d^*cf^* \nonumber \\
    t \rightarrow t &:& d^* +d^*cf^*bd^* \nonumber \ ,
\end{eqnarray}
kde $f = a + bd^*c$. (viz. [3, \S9.1, pp. 318-319] pro v�ce
informac� o kone�n�ch deterministick�ch automatech a regul�rn�ch
v�razech).

\subsection{Definice kleenovy algebry}

�rove� abstrakce, o kter� jsme se zm�nili v minul� kapitole, n�m
poskytuj� Kleenovy algebry. Toto pojet� probl�mu se odkazuje na
knihu Kleen \cite{Kleen}, ale r�zn� podn�ty jsou br�ny z pr�ce
Conway \cite{Conway}. N�sleduj�c� definice je vybr�na z
\cite{x63}.

\begin{definice} Kleenova algebra je struktura tvaru:
 $$ \K = (S, +, ., *, 0, 1) $$
\end{definice}

Kde $S$ je mno�ina prvk�, + a . jsou bin�rn� operace tvaru
 $S \times S \rightarrow S$, * je un�rn� operace tvaru $S \rightarrow S$,
a 0 a 1 jsou r�zn� prvky $S$ spl�uj�c� n�sleduj�c� axiomy:
\begin{align}
\label{ax:2}
 a + (b + c) & = (a + b) + c & & (+ je asociativn�) \\
\label{ax:3}
 a + b & = b + a & & (+ je komutativn�) \\
\label{ax:4}
 a + b & = a & & (+ je idenpotentn�) \\
\label{ax:5}
 a + 0 & = 0 + a = a & & (0 je a neutr�ln� prvek pro +) \\
\label{ax:6}
 a \cdot (b \cdot c) & = (a \cdot b) \cdot c & & ( \cdot je asociativn�) \\
\label{ax:7}
 a \cdot 1 & = 1 \cdot a = a & & (1 je a neutr�ln� prvek pro \cdot ) \\
\label{ax:8}
 0 \cdot a & = 0 \cdot a = 0 & & (0 je a ru��c� prvek pro \cdot ) \\
\label{ax:9}
 a \cdot (b + c) & = a \cdot b + a \cdot c & &( \cdot je distributivn� p�es +) \\
\label{ax:10}
 (b + c) \cdot a & = b \cdot a + c \cdot a
\end{align}
plus axiom pro * oper�tor, pro jeho� definici budeme pot�ebovat
n�sleduj�c� vysv�tlen�:
\begin{equation}
\label{ax:11}
 ab^*c = \sup _{n > 0} ab^nc
\end{equation}
kde
\begin{eqnarray}
    b^0 & = & 1 \nonumber \\
    b^{n+1} & = & b \cdot b^n \nonumber
\end{eqnarray} \qed

Axiomy (\ref{ax:2}-\ref{ax:5}) ��kaj� �e struktura (S, +, 0) je
idempotentn� komutativn� monoid. Axiomy (\ref{ax:6}-\ref{ax:7})
��kaj� �e (S, ., 1) je monoid. Axiomy (\ref{ax:8}-\ref{ax:10})
popisuj� interakci t�chto dvou monoid�. Dohromady, axiomy
(\ref{ax:2}-\ref{ax:10}) ��kaj� �e $\K$ je idempotentn� pologrupa.

Axiomy (\ref{ax:11}) zaji��uje existenci suprema nebo nejmen��
horn� z�vory dan� mno�iny s ohledem na jej� ��ste�n� uspo��d�n�.
Ve libovoln� idempotentn� pologrup� je ��ste�n� uspo��d�n�
definov�no n�sleduj�c�m vztahem:
\begin{equation}
\label{eq:12} a \leq b \ \leftrightarrow\  a + b = b
\end{equation}
Z axiom� (\ref{ax:2}-\ref{ax:5}) vypl�v� �e $\leq$ je opavdu
��ste�n� uspo��d�n�; tj.:
\begin{itemize}
    \item reflexivn�: $a \leq a$
    \item antisymetrick�: jestli�e $a \leq b$ a $b \leq a$ pak $a =
    b$; a
    \item tranzitivn�: jestli�e $a \leq b$ a $b \leq c$ pak $a
    \leq c$.
\end{itemize}
Jestli�e $A$ ��ste�n� uspo��dan� mno�ina, pak prvek $y$ je {\em
supremem} nebo {\em nejmen�� horn� z�vorou} mno�iny $A$
(ozna�ujeme $y = \sup A$) jestli�e:
\begin{itemize}
    \item $y$ je horn� z�vora $A$; tj. $x \leq y$ pro $\forall x \in
    A$;
    \item $y$ je nejmen�� horn� z�vora $A$; tj. $y \leq z$, kde $z$ je libovoln� jin� horn� z�vora v
    $A$;
\end{itemize}
Existuje supremum pro libovoln� p�r prvk� $x, y$ mno�iny a je
roven $x + y$. Z toho vypl�v�, �e existuje supremum libovoln�
kone�n� mno�iny a je rovno $a_1 + \dots + a_n$ (z�vorkov�n� nen�
pot�eba, proto�e + je asociativn�). Supremum nekon�n� mno�iny,
pokud existuje, je jedin�. Axiom (\ref{ax:11}) zaji��uje existenci
suprema mno�iny $\{ab^nc\ |\ n \geq 0\}$, kter� je rovno $ab^*c$.

Podm�nka (\ref{ax:11}) v sob� axiomaticky zahrnuje definici
chov�n� bin�rn� relace jako reflexivn�ho tranzitivn�ho uz�v�ru.
Tak� definuje chov�n� Kleenova oper�toru * z teorie form�ln�ch
jazyk�. Nav�c existuje mnoho p�iklad� nestandartn�ch Kleenov�ch
algeber, kter� jsou pou��v�ny pro r�zn� ��ely. N�sleduje n�kolik
p��klad�.

M�sto Kleenov�ch algeber pou��v� mnoho autor� (jako nap�.
\cite{x3, x78}) tzv. {\em uzav�en� pologrupy}. Tyto jsou velmi
bl�zk�mi Kleenov�m algebr�m, ale jsou definov�ny diskr�tn�, tj.
oper�tor $\Sigma$ m�sto suprema. V uzav�en�ch grup�ch, oper�tor *
nen� primitivn�, ale je definov�n jako:
 $$b^* = \sum_{n \geq 0} b^n$$
Diskr�tn� suma�n� oper�tor $\Sigma$, kter� s��t� spo�etn� �ady
prvk� nesm� z�viset na po�ad� prvk� v �ad� nebo na jejich
n�sobnosti, a z toho je to nutn� supremum. Oper�tor $\Sigma$ tak�
mus� vyhovovat podm�nce nekone�n� distributivity, kterou pro ka�d�
supremum dostaneme jednodu�e zaveden�m axiomu (\ref{ax:11}).

Hlavn� nev�hodou uzav�en�ch pologrup je to, �e nutn� aby supremum
pro v�echny spo�etn� mno�iny existovalo, co� u� je moc. T�m��
v�echny uzav�en� grupy jsou Kleenov�mi algebrami. Jist� existuj�
p��klady Kleenov�ch algeber, kter� nejsou uzav�en�mi grupami.
Nejd�le�it�j��m p��kladem takov� Kleenovy algebry je rodina
$\RegS$ regul�rn�ch podmno�in $\Sigma^*$, kde $\Sigma$ je kone�n�
abeceda (p��klad \ref{ex:62} n�e) Tento p��klad je d�le�it�,
proto�e je to Kleenova algebra voln� generovan� oper�torem
$\Sigma$, kter� ��k�, �e rovnost mezi regul�rn�mi v�razy nad
$\Sigma$ je nutn� zachov�na v Kleenov�ch algebr�ch tehdy a jen
tehdy jestli�e je zachov�na v $\RegS$. Uvid�me, �e tato skute�nost
je velice u�ite�n� p�i redukc�ch argument� Kleenov�ch algeber a
obecn� argument� regul�rn�ch podmno�in $\Sigma^*$.

Kleenovy algebry byly hloub�ji probr�ny v monografii Conway
\cite{Conway}. Je mo�n� axiomatizovat teorii Kleenov�ch algeber
jako �ist� kone�nou*** \cite{x64}.

\subsection{P��klady Kleenov�ch algeber}

Kleenov�ch algeber se hojn� vyu��v� v informatice. Zde jsou n�jak�
p��klady.

\begin{priklad} \label{ex:62}
Nech� $\Sigma$ je kone�n� abeceda a nech� $\RegS$ ozna�uje rodinu
regul�rn�ch v�raz� nad mno�inou $\Sigma$ s n�sleduj�c�mi
operacemi:
\begin{eqnarray}
    A + B & = & A \cup B \nonumber \\
    A \cdot B & = & \{xy\ |\ x \in A, y \in B \} \nonumber \\
    A^* & = & \{x_1x_2 \dots x_n\ |\ x \geq 0 \ \text{a}\ x_i \in A, i \leq i \leq n \} \nonumber \\
    & = & \bigcup_{n \geq 0} A^n \nonumber \\
    0 & = & \O \nonumber \\
    1 & = & \{ e \} \nonumber
\end{eqnarray}
kde $A^n$ je definov�no induc� vztahy:
\begin{eqnarray}
    A^0 & = & \{ e \} \nonumber \\
    A^{n + 1} & = & A \cdot A^n \nonumber
\end{eqnarray}
a $e$ je pr�zdn� �et�zec. S t�mito operacemi je $\RegS$ Kleenova
algebra, nav�c to nejd�le�it�j��: je to voln� Kleenova algebra
generovan� volnou mno�inou gener�tor� $\Sigma$***, co� znamen�, �e
libovoln� rovnost $\alpha = \beta$ mezi regul�rn�mi v�razy ja
platn� v Kleenov� algeb�e jestli�e je platn� v $\RegS$. \qed
\end{priklad}

\begin{priklad} \label{ex:63}
Nech� $X$ je mno�ina a $\mathcal{R}$ rodina bin�rn�ch relac� nad
$X$ uzav�en� n�sleduj�c�m operac�m:
\begin{eqnarray}
    R + S & = & R \cup S \nonumber \\
    R \cdot S & = & \{(x,y)\ |\ \exists y \in X\ (x,y) \in R\ \text{a}\ (y,z) \in S \} \nonumber \\
    R^* & = & \bigcup_{n \geq 0} R^n \nonumber \\
    & = & \text{reflexivn� tranzitivn� uz�v�r} R \nonumber \\
    0 & = & \O \nonumber \\
    1 & = & \{ (x,x)\ |\ x \in X \} \nonumber
\end{eqnarray}
kde $R^n$ je definov�no induc� vztahy:
\begin{eqnarray}
    R^0 & = & \{ (x,x)\ |\ x \in X \} \nonumber \\
    R^{n + 1} & = & R \cdot R^n \nonumber
\end{eqnarray}
S t�mito operacemi je $\mathcal{R}$ Kleenova algebra. Kleenovy
algebry bin�rn�ch relac� se pou��vaj� pro modelov�n� v danymick� a
jin�ch logik�ch program�. \qed
\end{priklad}

\begin{priklad} \label{ex:64}
Mno�ina $\{0, 1 \}$ booleovsk�ch pravdivostn�ch hoodnot s
n�sleduj�c�mi operacemi Kleenova algebra:
\begin{eqnarray}
    a + b & = & a \vee b \nonumber \\
    a \cdot b & = & a \wedge b \nonumber \\
    a^* & = & 1 \nonumber
\end{eqnarray}
a 0 a 1 jako norm�ln� hodnoty. Toto je nejmen�� Kleenova algebra.
\qed
\end{priklad}

\begin{priklad} \label{ex:65}
Rodina $x \times n$ booleovsk�ch matic s n�sleduj�c�mi operacemi
je Kleenova algebra:
\begin{eqnarray}
    A + B & = & A \vee B \nonumber \\
    A \cdot B & = & \text{booleovsk� n�soben� matic} \nonumber \\
    A^* & = & \text{reflexivn� tranzitivn� uz�v�r} \nonumber \\
    0 & = & \text{nulov� matice} \nonumber \\
    1 & = & \text{jednotkov� matice} \nonumber
\end{eqnarray}
Toto je v podstat� p��klad \ref{ex:63}, ale pro $n$-prvkovou
mno�inu $X$. \qed
\end{priklad}

\begin{priklad} \label{ex:66}
Tento docela zvl�tn� p��klad je u�ite�n� p�i v�po�tu pro v�echny
p�ry nejkrat�� cesty v ohodnocen�m grafu. Aby nedo�lo k z�m�n�m,
mus�me zav�st jasn�j�� ozna�ov�n�.

Ozna�me $\mathcal{R}_+$ rodinu nez�porn�ch re�ln�ch ��sel, a
$\infty$ jako nov� prvek. Ozna�me $+_\mathcal{R}$ jako norm�ln�
s��t�n� v $\mathcal{R}_+ \cup \{ \infty \}$, kde definujme:
 $$ a +_\mathcal{R} \infty = \infty +_\mathcal{R} a = \infty$$
pro $\forall a \in \mathcal{R}_+ \cup \{ \infty \}$. Ozna�me
$\leq_\mathcal{R}$ jako p�irozen� uspo��d�n� na $\mathcal{R}_+
\cup \{ \infty \}$, s $a \leq_\mathcal{R} \infty$ pro $\forall a
\in \mathcal{R}_+$. Ozna�me $\min_\mathcal{R}\{a,b\}$ men�� z
prvk� $a$ a $b$ s ohledem na definovan� uspo��d�n�. Ozna�me
$0_\mathcal{R}$ jako re�ln� ��slo 0.

Nyn� definujme operace kleenovy algebry $+_\K, \cdot_\K, ^{*_\K},
0_\K$ a $1_\K$ na $\mathcal{R}_+ \cup \{ \infty \}$ n�sledovn�:
\begin{eqnarray}
    a +_\K b & = & \min{\!_\mathcal{R}}\{a,b\} \nonumber \\
    & = & \begin{cases} a, & \text{jestli�e $a \leq_\mathcal{R} b$} \\ b, & \text{jinak} \end{cases} \nonumber \\
    a\ \cdot_\K b & = & a +_\mathcal{R} b \nonumber \\
    a^{*_\K} & = & 0_\mathcal{R} \nonumber \\
    0_\K & = & \infty \nonumber \\
    1_\K & = & 0_\mathcal{R} \nonumber
\end{eqnarray}
Jestli to vypad� zmaten�, nezoufejte, opravdu to zmaten� je. Aby
to d�valo smysl, uv�domme si, �e symboly na lev� stran� rovnic se
vztahuj� k definovan� Kleenov� algeb�e, kde pak symboly na prav�
stran� pat�� k p�irozen�m operac�m na $\mathcal{R}_+ \cup \{
\infty \}$. V�imn�me si, �e nulov� prvek kleenovy algebry je
$\infty$, neutr�ln� prvek k $\min_\mathcal{R}\{a,b\}$ a
multiplikativn� neutr�ln� prvek 1 kleenovy algebry je re�ln� ��slo
0, neutr�ln� prvek pro s��t�n� v $\mathcal{R}_+ \cup \{ \infty \}$
(co� je pro kleenovu algebru multiplikativn� operace). Nejhor�� je
��st o ��ste�n�m uspo��d�n� $\leq_\K$ definovan� pro kleenovu
algebru ve vztahu (\ref{eq:12}) jako obr�cen� k
$\leq_\mathcal{R}$; tj. $a \leq_\K b$ jestli�e $b \leq_\mathcal{R}
a$

Tato algebra je �asto naz�v�na jako min,+ kleenova algebra. \qed
\end{priklad}

\section{V�ce o kleenov�ch algebr�ch}

V t�to kapitole si uk�eme, jak se pou��vaj� kleenovy algebry v
�ad� situac� t�kaj�c�ch se *-�ch operac�. Hlavn� v�sledek
dovoluj�c� takov�to pou�it� je, �e $n \times n$ matic nad
kleenovou algebrou d�v� op�t kleenovu algebru. V pr�b�hu vyslov�me
hlavn� lema kter� vyslovuje d�le�itost regul�rn� mno�iny $\RegS$
nad kone�nou abecedou $\Sigma$ v �vah�ch o kleenov�ch algebr�ch
obecn�.

Nech�
 $$ \K = (K, +_\K, \cdot_\K, ^{*_\K}, 0_\K, 1_\K )$$
je kleenova algebra. Nech� $\Sigma$ je mno�ina a ozna�me $\RExpS$
rodinu regul�rn�ch v�raz� nad $\Sigma$ (viz. [3, \S9.1, pp.
318-319]). Interpretace nad $\K$ je zobrazen�:
 $$ I : \Sigma \rightarrow \K $$
p�i�azuj�c� prvek $\K$ ka�d�mu prvku $\Sigma$. Interpretace m��e
b�t roz���ena na b�zi $\RExpS$ indukc� n�sledovn�:
\begin{eqnarray}
    I(0) & = & 0_\K \nonumber \\
    I(1) & = & 1_\K \nonumber \\
    I(\alpha + \beta) & = & I(\alpha) +_\K I(\beta) \nonumber \\
    I(\alpha \cdot \beta) & = & I(\alpha) \cdot_\K I(\beta) \nonumber \\
    I(\alpha^*) & = & I(\alpha)^{*_\K} \nonumber
\end{eqnarray}
S rizikem z�m�ny oper�tor� regul�rn�ch v�raz� a p��slu�n�ch
operac� v $\K$ m��eme vynechat indexy $\K$.

Nap��klad interpretace
\begin{eqnarray}
    R & : & \Sigma \rightarrow \RegS \nonumber \\
    & & a \rightarrow \{ a \} \nonumber
\end{eqnarray}
nad $\RegS$ se roz���� na zobrazen�
 $$ R : \RExpS \rightarrow \RegS $$
ve kter�m $R(\alpha)$ je regul�rn� mno�ina ozna�en� regul�rn�m
v�razem $\alpha$ v b�n�m smyslu. Interpretace $R$ se naz�v� {\em
stndartn� interpretac� nad $\RegS$ }

N�sleduj�c� lema zobec�uje (\ref{ax:11}).

\bigskip
\begin{lema} \label{lm:71} Nech� $R : \Sigma \rightarrow
\RegS$ je standartn� interpretace nad $\RegS$ a nech� $I : \Sigma
\rightarrow \K$ je interpretace nad libovolnou kleenovou algebrou
$\K$. Pro libovoln� regul�rn� v�raz $\alpha$ nad $\Sigma$,
\end{lema}
\begin{equation} \label{eq:13}
 I(\alpha) = \sup _{x \in R(\alpha)} I(x)
\end{equation}
V�imn�me si, �e kdy� je $R(\alpha)$ regul�rn� mno�ina �et�zc� nad
abecedou $\Sigma$, pak $x$ v (\ref{eq:13}) ozna�uje �et�zec.
�et�zce nad $\Sigma$ jsou samy o sob� regul�rn�mi v�razy nad
$\Sigma$, tak�e v�raz $I(x)$ m� smysl. Rovnice (\ref{eq:13}) ��k�,
�e existuje supremum mno�iny (i nekone�n�)
 $$ \{ I(x)\ |\ x \in R(\alpha) \} \subseteq \K $$
a je rovno $I(\alpha)$. D�kaz lematu \ref{lm:71} nech�me na
p��klad (dom�c� �kol 3, p��klad 2).

Z v��e uveden�ch vztah� vypl�v�, �e pro libovoln� p�r regul�rn�ch
v�raz� $\alpha, \beta$ nad $\Sigma$, je rovnost $\alpha = \beta$
d�sledkem axiom� kleenovy algebry, tzn. je zachov�na ve v�ech
interpretac�ch kleenov�ch algeber, tehdy a jen tehdy je-li
zachov�na interpretace $R$ nad $\RegS$. P�edsaviteln�ji to lze
��ci takto: $\RegS$ je kleenova algebra generovan� voln�mi
gener�tory $\Sigma$.

\setcounter{theorem}{\value{lema}}
\begin{theorem} \label{tm:72}
Nech� $\alpha$ a $\beta$ jsou regul�rn� v�razy nad $\Sigma$ a
nech� $R$ je standartn� interpretac� nad $\RegS$. Pak
 $$ I(\alpha) = I(\beta) $$
pro v�echny interpretace I nad kleenov�mi algebrami tehdy a jen
tehdy jestli�e
 $$ R(\alpha) = R(\beta) $$

D�kaz:  ($\rightarrow$) Je z�ejm� ze skute�nosti, �e $\RegS$ je
kleenova algebra a $R$ je interpretace nad $\RegS$.

        ($\leftarrow$) Uva�ujme $R(\alpha) = R(\beta)$. Pak
\begin{align}
    I(\alpha) & = \sup _{x \in R(\alpha)} I(x) && \text{podle lematu \ref{lm:71}} \nonumber \\
    & = \sup _{x \in R(\beta)} I(x) && \text{podle p�edpokladu} R(\alpha) = R(\beta) \nonumber \\
    & = I(\beta), && \text{op�t podle lematu \ref{lm:71}} \nonumber
\end{align} \qed
\end{theorem}

\subsection{Maticov� kleenovy algebry}

Kolekce $M(n,\K)$ matic $n \times n$ s prvky kleenovy algebry $\K$
je op�t kleenova algebra, jastli�e jsou oper�tory na $M(n,\K)$
p��slu�n� definov�ny. My definujeme oper�tor + jako oby�ejn�
s��t�n� matic, . jako n�soben� matic, 0 jako nulovou matici, 1
jako jednotkovou matici a * rekurzivn� podle vztahu (\ref{eq:1}) v
p�edchoz� kapitole. Mus�me uk�zat, �e jsou spln�ny v�echny axiomy
kleenovy algebry tak� pro $M(n,\K)$ s takto definovan�mi
oper�tory, Nap��klad, v $M(2,\K)$ jsou pro + a . neutr�ln�mi prvky
\begin{equation}
    \left[ \begin{matrix}
        0 & 0 \cr 0 & 0
    \end{matrix} \right] \qquad
    \left[ \begin{matrix}
        1 & 0 \cr 0 & 1
    \end{matrix} \right] \nonumber
\end{equation}
v definovan�m po�ad�, a operace +,\ ., a * jsou d�ny vztahy
\begin{eqnarray}
    \left[ \begin{matrix}
        a & b \cr c & d
    \end{matrix} \right] +
    \left[ \begin{matrix}
        e & f \cr g & h
    \end{matrix} \right] & = &
    \left[ \begin{matrix}
        a + e & b + f \cr c + g & d + h
    \end{matrix} \right] \nonumber \\
    \left[ \begin{matrix}
        a & b \cr c & d
    \end{matrix} \right] .
    \left[ \begin{matrix}
        e & f \cr g & h
    \end{matrix} \right] & = &
    \left[ \begin{matrix}
        ae + bg & af + bh \cr ce + dg & cf + dh
    \end{matrix} \right] \nonumber \\
    \left[ \begin{matrix}
        a & b \cr c & d
    \end{matrix} \right] ^* & = &
    \left[ \begin{matrix}
        f^* & f^*bd^* \cr d^*cf^* & d^* +d^*cf^*bd^*
    \end{matrix} \right] \nonumber
\end{eqnarray}
kde $f = a + bd^*c$. V�imn�me si, �e $A \leq B$ jsou v p��rozen�m
uspo��d�n� nad $M(n,\K)$ definovan� v (\ref{eq:12}) tehdy a jen
tehdy jestli�e $A_{ij} \leq B_{ij}$ pro $\forall\ 1 \leq i,j \leq
n$.

Ov��en� v�t�iny axiom� kleenov�ch algeber pro strukturu $M(n,\K)$
je rutinn� z�le�itost�. Ov��me si nyn� zvl᚝ axiom (\ref{ax:11})
za p�edpokladu, �e jsme ji� ov��ili v�echny ostatn�. Nejprve
uk�eme, �e je pravdiv� pro ur�it� matice nad n�jakou kleenovou
algebrou regul�rn�ch mno�in, pomoc� kombina�n�ch argument�;
n�sledn� pou�ijeme teor�m \ref{tm:72} pro roz���en� v�sledku na
v�echny kleenovy algebry.

Nech� $\mathbf{A}, \mathbf{B}$ a $\mathbf{C}$ jsou $n \times n$
symbolick� matice s prvky na i-t�m ��dku a j-t�m sloupci $a_{ij},
b_{ij}$ a $c_{ij}$, kde $a_{ij}, b_{ij}, c_{ij}$ jsou r�zn�
p�smena. Nech�
 $$ \Sigma = \{ a_{ij}, b_{ij}, c_{ij}\ |\ 1 \leq i,j \leq n \} $$
Zkonstuujme automat $M_\mathbf{B}$ s $n$ stavy a prechodem ze
stavu $i$ do stavu $j$ ozna�en�m $\mathbf{b}_{ij}$. Prvek na i-t�m
��dku a j-t�m sloupci $\mathbf{B}^k$ symbolick� k-t� mocinin�
$\mathbf{B}$, je regul�rn� v�raz reprezentuj�c� mno�inu �et�zc�
d�lky $k$ nad $\Sigma$ pro p�echod ze stavu $i$ do stavu $j$ v
$M_\mathbf{B}$. To vypl�v� z �ist� kombina�n�ho induk�n�ho
argumentu pou�it�m definice $\mathbf{B}^*$ jak je d�na v
(\ref{eq:1}); Rozd�len� v (\ref{eq:1}) p��slu�� k rozd�len� stav�
v $M_\mathbf{B}$ do dvou disjunktn�ch mno�in. Pak z toho m�me
 $$ R((\mathbf{B}^*)_{ij}) = \bigcup_{k \geq 0} R((\mathbf{B}^k)_{ij}) $$
kde $R$ je standartn� interpretace.

Nech� se $M_\mathbf{A}$ a $M_\mathbf{C}$ skl�daj� ka�d� z $n$
stav�. Propojme stav i v $M_\mathbf{A}$ se stavem j v
$M_\mathbf{B}$ a p�echod ozna�me $a_{ij}$. Podobn� propojme stav i
v $M_\mathbf{B}$ se stavem j v $M_\mathbf{C}$ a p�echod ozna�me
$c_{ij}$. Takto vytvo�en� automat ozna�me $M$. Pak mno�ina
regul�rn�ch v�raz� nad $\Sigma$ ozna�en� prvkem na na i-t�m ��dku
a j-t�m sloupci matice $\mathbf{AB}^k\mathbf{C}$ je mno�ina
�et�zc� d�lky $k + 2$ pro p�echod za stavu $i$ v $M_\mathbf{A}$ do
stavu $j$ v $M_\mathbf{C}$ v $M$, a regul�rn� mno�ina ozna�en�
prvkem na na i-t�m ��dku a j-t�m sloupci matice
$\mathbf{AB}^*\mathbf{C}$ je mno�ina �et�zc� (libovoln� d�lky) pro
p�echod za stavu $i$ v $M_\mathbf{A}$ do stavu $j$ v
$M_\mathbf{C}$ v $M$. Z toho pak
 $$ R((\mathbf{AB}^*\mathbf{C})_{ij}) = \bigcup_{k \geq 0} R(\mathbf{AB}^k\mathbf{C})_{ij}) $$
Nen� nech� $A, B, C$ jsou libovoln� matice nad libovolnou
kleenovou algebrou $\K$. Nech� $a_{ij}, b_{ij}, c_{ij}$ jsou
jejich prvky. Nech� $I$ je interpretace
\begin{eqnarray}
    I(\mathbf{a}_{ij}) = a_{ij} \nonumber \\
    I(\mathbf{b}_{ij}) = b_{ij} \nonumber \\
    I(\mathbf{c}_{ij}) = c_{ij} \nonumber
\end{eqnarray}
Pak
\begin{align}
    (\mathbf{AB}^*\mathbf{C})_{ij} & =
    I((\mathbf{AB}^k\mathbf{C})_{ij}) \nonumber \\
    & = \sup\{ I(x)\ |\ x \in R((\mathbf{AB}^*\mathbf{C})_{ij}) \} & \text{podle lematu}\ \ref{lm:71} \nonumber \\
    & = \sup\{ I(x)\ |\ x \in \bigcup_{k \geq 0} R((\mathbf{AB}^k\mathbf{C})_{ij}) \} \nonumber \\
    & = \sup_{k \geq 0}\ \sup\{ I(x)\ |\ x \in R((\mathbf{AB}^k\mathbf{C})_{ij}) \} \nonumber \\
    & = \sup_{k \geq 0} I((\mathbf{AB}^k\mathbf{C})_{ij}) \nonumber \\
    & = \sup_{k \geq 0} (\mathbf{AB}^k\mathbf{C})_{ij} \nonumber\ ,
\end{align}
z toho pak
 $$ \mathbf{AB}^*\mathbf{C} = \sup_{k \geq 0} \mathbf{AB}^k\mathbf{C} $$
Co� dokazuje (\ref{ax:11}) pro $M(n,\K)$.

\subsection{Pou�it�}

Z�ejm� rozd�l a panuj algoritmus pro v�po�et $E^*$ dan�ho vztahem
(\ref{eq:1}) generuje rekurzi
 $$T(n) = 2T(\frac{n}{2}) + O(M(n))$$
kde $M(n)$ je po�et z�kladn�ch operac� pot�ebn�ch pro s��t�n� a
n�soben� dvou $n \times n$ matic nad $\K$. Pod dostate�nou
podm�kou $M(2n) \geq 4M(n)$, m� tato rekurze �e�en�
 $$T(n) = O(M(n))$$
Pro v�t�inu aplikac�, $M(n) = O(n^3)$. L�p�� hranici m��eme
obdr�et pou�it�m Strassenova algorimu nebo jin�ho algoritmu
rychl�ho n�soben� matic kdy� $kappa$ je grupa.

\bigskip
\noindent{\bf Reflexivn� tranzitivn� uz�v�r}
\smallskip

Pomoc� kleenov�ch algeber m��eme dok�zat spr�vnost algoritmu pro
v�po�et reflexivn�ho tranzitivn�ho uz�v�ru v p�edchoz� kapitole.
Ozna�me $\mathcal{B}$ douprvkovou kleenovu algebru popsanou v��e v
p��kladu \ref{ex:64}. Ozna�me $E$ inciden�n� matici orientovan�ho
grafu $G$ s $n$ uzly. Pak $E \in M(n,\mathcal{B})$, a prvek na
i-t�m ��dku a j-t�m sloupci $E^k$ je 1 tehdy a jen tehy jestli�e
existuje cesta v $G$ z uzlu $i$ do uzlu $j$ d�lky $k$. Podle
v�sledku p�edchoz� kapitoly v�me �e
 $$ E^* = \sup_{k \geq 0} E^k $$
tak�e prvek na i-t�m ��dku a j-t�m sloupci $E^k$ je 1 tehdy a jen
tehy jestli�e existuje cesta (libovoln� d�lky) z uzlu $i$ do uzlu
$j$. Pak toto je reflexivn� tranzitivn� uz�v�r.

\bigskip
\noindent{\bf Nejkrat�� cesta pro v�ech p�ry}
\smallskip

Zde pou�ijeme stejn� algoritmus, ale jinou fundment�ln� kleenovu
algebru, jmenovit� min,+ algebru z p��kladu \ref{ex:66} v��e.
Supremum v tomto upo��d�n� je infimum v b�n�m uspo��d�n� na $R_+
\cup \{\infty\}$. Z toho $a^*$ je re�ln� ��slo 0 pro v�echna $a$.

Pak toto aplikujeme na probl�m nalezen� nejkrat�� cesty pro v�ech
p�ry. Nech� $E$ je matice nad min,+ algebrou obsahuj�c� d�lky hran
ohodnocen�ho orientovan�ho grafu $G$. Jestli�e $(i,j)$ nen� hrana
v $G$, nastav�me $E_{ij} = \infty$. V $E^2$ bude prvek na i-t�m
��dku a j-t�m sloupci minimum sou�tu d�lek $(i,k)$ a $(k,j)$ p�es
v�echny uzly $k$. Tj. bude obsahovat d�lku nejkrat�� cesty o dvou
hran�ch z $i$ do $j$. Z
 $$ E^* = \sup_{k \geq 0} E^k $$
indukc� vypl�v� �e prvek na i-t�m ��dku a j-t�m sloupci $E^k$ bude
obsahovat d�lku nejkrat�� cesty o $k$ hran�ch a supremum v
kleenov� algeb�e je infimum v p�irozen�m uspo��d�n�, $E^*$ d�v�
d�lku nejkrat�� cesty o libovoln�m po�tu hran.

\pagebreak
\appendix

\begin{thebibliography}{0}

\bibitem[3]{x3}
unknown

\bibitem[28]{Dijkstra}
Dijkstra

\bibitem[61]{Kleen}
Kleen

\bibitem[21]{Conway}
Conway

\bibitem[63]{x63}
unknown

\bibitem[64]{x64}
unknown

\bibitem[78]{x78}
unknown

\end{thebibliography}

\end{document}
