\chapter{Dekompozice sekvenčního automatu}
\label{dekompozice}
\parindent= 30pt

Dekompozice sekvenčního automatu spočívá v jeho rozdělení na několik menších a jednodušších částí, které dohromady splňují funkčnost dekomponovaného automatu. Existuje několik druhů dekompozice, každá se svým vlastním specifickým uplatněním. V této práci se budu věnovat především úplné obecné symbolické dekompozici sekvenčního obvodu (vysvětlení těchto pojmů viz níže), ale pro ucelení představy o dekompozici FSM budou představeny i další druhy dekompozice.

\section{Dekompozice logické funkce}
Ačkoliv logické funkce nejsou implementovány pomocí sekvenčních obvodů, je vhodné je pro přehled uvést. Dekompozice logické funkce znamená rozklad logické funkce na menší podvýrazy. Účelem této dekompozice je obvykle snížení počtu vstupních a výstupních signálů jednotlivých podvýrazů, čímže se dosahuje optimálnější implementace především u programovatelných obvodů (LUT u FPGA obvykle obsahuje 4 nebo 5 vstupů a 2 výstupy).

Dekompozice se provádí výběrem určitého počtu vstupních proměnných, které přenášejí určitou informaci potřebnou k výpočtu výstupní informace. Z těchto proměnných se poté vytvoří podvýraz tak, aby velikost výstupu odpovídala požadavkům na implementaci a zároveň aby se přenesla pokud možno všechna důležitá informace ze vstupních proměnných. Ty proměnné, které už mají veškerou potřebnou informaci obsaženou v tomto podvýrazu již nejsou potřeba a tudíž v dalších podvýrazech se již nepoužívají (viz Obr. \ref{fDecPic}). Podmínkou platné dekompozice logické funkce je, že počet výstupů podvýrazu musí být menší než počet vstupních proměnných, které se díky tomuto podvýrazu dále nemusí používat (toto je logické, jelikož každý výstup podvýrazu tvoří nový vstup celkové funkce a při nedodržení podmínky by se celkový počet vstupů tedy zvětšil).

\begin{figure}[h]
\begin{center}
\includegraphics{log_function}
\caption{Princip dekompozice logické funkce}
\label{fDecPic}
\end{center}
\end{figure}
\newpage
\section{Dekompozice sekvenčního obvodu}
Dekompozice sekvenčního obvodu je hlavním tématem této práce. V následujícím textu bude uveden jak přehled různých druhů a metod dekompozice, tak detailně vysvětlena metoda úplné obecné dekompozice se zachováním vícestavové realizace a vysvětleny pojmy s touto metodou související.

\begin{definition}[Podautomat]
\label{subFSMef}
Jeden funkční celek vystupující z procesu dekompozice, spolu s ostatními podautomaty vzešlé z této dekompozice splňuje funkci automatu do dekompozice vstupujícího.
\end{definition}

\begin{definition}[Původní/originální automat]
\label{origFSMDef}
Původním, nebo také originálním automatem, se myslí automat vstupující do procesu dekompozice. Podautomaty z této dekompozice vystupující musí společně splňovat funkci právě tohoto automatu.
\end{definition}

\begin{definition}[Dekomponovaný automat]
\label{decFSMDef}
Automat vzniklý vhodným propojením podautomatů. Má stejnou funkčnost i stejný počet vstupů a výstupů jako původní automat, jen jinou vnitřní strukturu.
\end{definition}
 
Dekompozice sekvenčních obvodů (FSM) je ve své podstatě mnohem komplexnější než dekompozice logické funkce. Zatímco u dekompozice funkce máme jako vstupující informaci jen informaci ze vstupních proměnných, u sekvenčního obvodu máme navíc informaci o stavu. Tím se nejen komplikuje výpočet výstupní fuknce, ale zároveň je třeba spočítat i následující stav, jinak dekomponovaný automat nebude splňovat funkci původního automatu.

\subsection{Stavová a úplná dekompozice}
S ohledem na rozsah dekompozice rozeznáváme dekompozici buď stavovou nebo úplnou

\subsubsection*{Stavová dekompozice sekvenčního obvodu}
Stavová dekompozice FSM byla prvním druhem dekompozice konečného automatu představena Hartmanisem v roce 1960. Její princip spočívá ve vytvoření několika podautomatů, které mají vstupy a výstupy stejné jako původní automat, ale mají menší počet vnitřních stavů. Toto se však pro PLA ukázalo jako nedostatečné, jelikož počet vstupních i výstupních proměnných zůstával neměnný a byla omezena možnost přizpůsobení automatu technologii.

\subsubsection*{Úplná dekompozice sekvenčního obvodu}
Úplná dekompozice FSM spočívá v dekompozici nejen množiny stavů, ale také množiny vstupních a výstupních symbolů. Tím se dosahuje redukce počtu vstupních a výstupních proměnných jednotlivých podautomatů. Princip obecné úplné dekompozice je zobrazen na Obr. \ref{genDecPic}. 
\newline

\begin{figure}[ht]
\begin{center}
\includegraphics{gen_dec}
\caption{Úplná obecná dekompozice}
\label{genDecPic}
\end{center}
\end{figure}
\newpage
\subsection{Postupná a současná dekompozice}
Podle průběhu spolupráce jednotlivých podautomatů rozeznáváme druhy dekompozicí:

\subsubsection*{Postupná dekompozice}
Postupná dekompozcie se provádí rozkladem původního FSM na podautomaty spolupracující tak, že každý podautomat vykonává svou činnost v jiný okamžik než ostatní podautomaty. Proto také název postupná dekompozice, jelikož podautomaty pracují postupně. Používá se především při návrhu struktury  mikroprogramových řadičů \cite{pop01}.

\subsubsection*{Současná dekompozice}
Současná dekompozice funguje na principu okamžité spolupráce jednotlivých podautomatů. Aktuální výstup vzniká sloučením výstupů všech podautomatů (na rozdíl od postupné dekompozice, kde výstup tvoří vždy jen jeden podautomat)

\subsection{Symbolická a bitová dekompozice}

\subsubsection*{Symbolická dekompozice}
Symbolická dekompozice se provádí bez znalosti kódování vstupních a výstupních symbolů, Musíme tedy pracovat s celým symbolem jako celkem a s celou množinou těchto symbolů.

\subsubsection*{Bitová dekompozice}
Provádí se pokud známe kódování vstupních a výstupních symbolů. Metoda spočívá v dekompozici těchto symbolů ne v celku, ale po jednotlivých řádech bitů, čímž se dosahuje vyšší efektivity a flexibility, jelikož se nemusí pracovat s celou množinou symbolů, ale jen s částí.

\subsection{Dekompozice se společnou a oddělenou výstupní a přechodovou funkcí}
V obou případech se jedná o současnou úplnou dekompozici, oba druhy dekompozice jsou si podobné - mohou se používat k podobným účelům, vytvářet stejné hierarchie podautomatů apod.

\subsubsection*{Dekompozice s oddělenou výstupní a přechodovou funkcí}
Tato dekompozice se provádí pouze na množině vstupních symbolů a stavů. Výsledkem spolupráce podautomatů je pouze následující stav, nikoliv výstup (viz \ref{genSepDecPic}). Tento výstup se potom vypočítá ve výstupním bloku $\theta$ (viz Obr.) za pomoci informace o aktuálním stavu (dodané podautomaty) a informace o vstupu (dodané přímo ze vstupu dekomponovaného automatu). 

Výhodou této dekompozice je snažší hledání vhodné dekompozice, jelikož se nedekomponují výstupní symboly. Nevýhodou je ale složitá výstupní funkce, která u složitějších automatů musí být sama dekomponována (viz Dekompozice logické funkce), což může být samo o sobě poměrně složité a zdlouhavé.

\begin{figure}[ht]
\begin{center}
\includegraphics{gen_sep_dec}
\caption{Obecná dekompozice s oddělenou realizací přechodové a výstupní funkce}
\label{genSepDecPic}
\end{center}
\end{figure}

\subsubsection*{Dekompozice se společnou výstupní a přechodovou funkcí}
Jedná se o obecnější a univerzálnější typ dekompozice. Spočívá v dekompozici nejen množiny vstupů a stavů, ale také výstupů. Tomuto druhu dekompozice se věnuje tato práce a proto v následujícím textu bude dekompozice automaticky považována právě za dekompozici se společnou výstupní a přechodovou funkcí, ačkoliv jak bylo řečeno výše většina principů se dá buď beze změny nebo s drobnými úpravami použít i při dekompozici s oddělenou výstupní a přechodovou funkcí.

\subsection{Struktura dekomponovaného automatu}
Ačkoliv struktura dekomponovaného automatu se může v mnohém lišit, základní prvky jsou většinou podobné (viz \ref{strDecPic}). Obecná struktura dekomponovaného automatu je zobrazena na Obr. a obsahuje tyto části:

\paragraph{Vstupní blok $\Psi$:}
Vstupní blok je reprezentován logickou funkcí, která na základě primárního vstupního symbolu vypočítá vstupní symboly pro jednotlivé podautomaty.

\paragraph{Podautomaty $M_1, \ldots , M_n$:}
Sekvenční obvody realizující část činnosti původního automatu.

\paragraph{Propojovací členy $con_1, \ldots,con_n$:}
Logické funkce vybírající z celkové informace dostupné od ostatních podautomatů informaci potřebnou právě pro daný podautomat.

\paragraph{Výstupní blok $\Theta$:}
Výstupní blok je reprezentován logickou funkcí, která na základě výstupů z jednotlivých podautomatů vypočítává primární výstupní symbol.

\begin{figure}[ht]
\begin{center}
\includegraphics{str_dec}
\caption{Struktura úplné obecné dekompozice s \emph{n} podautomaty}
\label{strDecPic}
\end{center}
\end{figure}

\subsection{Uspořádání podautomatů}
Ačkoliv struktura propojení a spolupráce podautomatů může být velice různorodá, z důvodu dostatečné komplexnosti a také univerzálnosti se používají především tři druhy zapojení - paralelní, seriové a obecné. Tato propojení se mezi sebou liší v množství komunikace mezi jednotlivými podautomaty.

\begin{figure}[ht]
\begin{center}
\includegraphics{par_dec}
\caption{Paralelní dekompozice}
\label{parDecPic}
\end{center}
\end{figure}

\subsubsection*{Paralelní dekompozice}
Jedná se o nezávisle pracující podautomaty, které mezi sebou nijak nekomunikují. Výsledný výstup se vypočítá až na základě výstupních symbolů jednotlivých podautomatů ve výstupním bloku. Každý podautomat tedy musí umět vypočítat svůj výstup a následný stav bez znalosti aktuálního stavu jiných podautomatů a informace o vstupním symbolu a stavu jsou jediné dostupné (viz Obr. \ref{parDecPic}).

\newpage
\subsubsection*{Sériová dekompozice}
U tohoto způsobu propojení jeden podautomat pracuje samostatně bez informace o druhém podautomatu (označuje se head), a druhý automat (tail) používá informaci produkovanou tímto podautomatem k výpočtu výstupu a následujícího stavu. V případě sériového propojení více podautomatů jsou podautomaty uspořádány do takovýchto dvojic jdoucích za sebou (viz Obr.~\ref{serDecPic}).

\begin{figure}[ht]
\begin{center}
\includegraphics{ser_dec}
\caption{Sériová dekompozice}
\label{serDecPic}
\end{center}
\end{figure}

\subsubsection*{Obecná dekompozice}
Každý podautomat tohoto propojení využívá informaci dostupnou z ostatních podautomatů k výpočtu výstupu a následujícího stavu. O vhodnou distribuci informace se starají propojovací členy, které vybírají jen tu informaci, kterou podautomat potřebuje k výpočtům (viz Obr. \ref{genDecPic}).
\newpage
\subsubsection*{Porovnání uspořádání}
Ačkoliv se může zdát použití paralelní dekompozice nejvýhodnější, nemusí tomu tak být vždy. Jednak ne u každého podautomatu může existovat paralelní dekompozice (podle \cite{FriedMeno01} jsme jen u 30\% podautomatů schopni najít paralelní dekompozici) a jednak při této dekompozici nemusí docházet k potřebné redukci vnitřních stavů, což snižuje kvalitu dekompozice (\cite{jozw02,jozw03}).

Obecná dekompozice má tu výhodu, že může používat i informaci dostupnou od ostatních podautomatů a tyto potom nemusí sami o sobě produkovat tolik informace, čímž se dá dosáhnout kvalitnější dekompozice. Na druhou stranu zatěžuje obvod jednak samotnými propojeními mezi podautomaty a jednak propojovacími členy, které mohou sami vyžadovat dekompozici, aby splnili technologické podmínky implementace.

Seriová dekompozice je potom někde mezi těmito dvěmi uspořádáními. Ne každý automat může mít platnou sériovou dekompozici a ne vždy musí být optimální co do zjednodušení struktury podatuomatu. Na druhou stranu nevyžaduje tolik komunikace mezi podautomaty a je tudíž méně náročná na implementaci.

\section{Dekompozice úplně zadaného konečného automatu}

Ačkoliv je tato práce zaměřena na dekompozici neúplně zadaného automatu, pro úplnost a snazší porozumnění problematice zde bude nejprve vysvětlen a předvedena dekompozice úplně zadaného automatu. Tato dekompozice se dá považovat také za podmnožinu dekompozice neúplně zadaného podautomatu, jen ne tolik obecnou. 

Teorie použitá v této části práce vychází z \cite{jozw04}. Nejprve zde uvedu některé pojmy potřebné k pochopení principu dekompozice a poté pro názornost předvedu dekompozici na příkladu. Teoretická část popsaná v této části je potom základem pro dekompozici neúplně zadaného automatu, tudíž některé pojmy vysvětlené v této části budou beze změny používány nadále, některé jsou pro neúplně zadané automaty nedostačující a budou tedy nahrazeny sice podobnými, ale více obecnými pojmy.

\subsection{Teorie}
Účelem dekompozice je zredukovat počet stavů a vstupních a výstupních symbolů FSM tak, aby bylo možno automat lépe implmentovat na požadovanou platformu. K tomu se využívají rozklady u úplně zadaných FSM popř. systémy množin u neúplně zadaných FSM. Před vysvětlením principu dekompozice je třeba zavést následující rozklady:

\begin{definition}[Rozklad nad množinou vstupních symbolů $\pi_I$]
\label{inPartDef}
Rozklad $\pi_I$ je rozkladem (systémem množin) nad množinou vstupních symbolů, pokud sloučením všech bloků tohoto rozkladu vznikne množina všech vstupních symbolů.
\end{definition}

\begin{definition}[Rozklad nad množinou stavů $\pi_S$]
\label{statePartDef}
Rozklad $\pi_S$ je rozkladem (systémem množin) nad množinou stavů, pokud sloučením všech bloků tohoto rozkladu vznikne množina všech stavů.
\end{definition}

\begin{definition}[Rozklad nad množinou výstupních symbolů $\pi_{S \times I}$]
\label{outputPartDef}
Rozklad $\pi_{S \times I}$ je rozkladem (systémem množin) nad množinou výstupních symbolů, pokud sloučením všech bloků tohoto rozkladu vznikne množina všech prvků kartézského součinu množin vstupních symbolů a stavů.
\end{definition}

\begin{definition}[Rozklad nad množinou primárních výstupních symbolů $\pi_O$]
\label{primOutPartDef}
Rozklad $\pi_O$ je rozkladem (systémem množin) nad množinou primárních výstupních symbolů, pokud sloučením všech bloků tohoto rozkladu vznikne množina primárních výstupních symbolů, tedy výstupních symbolů původního automatu.
\end{definition}

Rozklad $\pi_{I\times S}$ byl zaveden jako rozklad, na který je přímo možné namapovat kombinace vstupních symbolů a aktuálních stavů. Tyto kombinace nám potom dávají veškerou informaci, kterou potřebujeme jak k určení výstupního symbolu, tak následujícího stavu. Ve starších pracích je uváděn jen rozklad $\pi_O$, ale zavedení $\pi_{I\times S}$ umožnilo využít efektivněji celkovou vstupní informaci a tím zlepšit výslednou dekompozici.

\begin{definition}[Bloková přechodová funkce $\overline{\delta}$]
\label{BlockTransDef}
$$\overline{\delta} : 2^{S \times I} \rightarrow 2^S$$
\end{definition}

Funce $\overline{\delta}(D)$ vypočítá ze všech prvků bloku D rozkladu $\pi_{S \times I}$ následující stav a vybere blok z rozkladu $\pi_S$ takový, že obsahuje všechny tyto následující stavy.

\begin{definition}[Bloková výstupní funkce $\overline{\lambda}$]
\label{BlockOutDef}
$$\overline{\lambda} : 2^{S \times I} \rightarrow 2^O$$
\end{definition}

Funce $\overline{\lambda}(D)$ vypočítá ze všech prvků bloku D rozkladu $\pi_{S \times I}$ výstupní symbol a vybere blok z rozkladu $\pi_O$ takový, že obsahuje všechny tyto symboly.

\begin{example}
\label{blockTransOutEx}
Mějme automat zadaný tabulkou \ref{compSpecFSM}, dvoublokový rozklad nad množinou výstupních prvků $\pi_{S \times I} = \{(a0,b0),(a1,b1,c0,c1)\}$. $\overline{\lambda}(D_1) = \{\lambda(a,0),\lambda(b,0),\} = \{00,11\}$ a $\overline{\delta}(D_1) = \{\delta(a,0),\delta(b,0),\} = \{c\}$, $\overline{\lambda}(D_2) = \{01,10\}$ a $\overline{\delta}(D_2) = \{a,b\}$
\newline
\end{example}

\begin{table}[ht]
\begin{center}
\begin{tabular}{c|cc|c}
\hline 
in & ps & ns & out\\
\hline
0 & a & c & 00 \\
1 & a & a & 01 \\
0 & b & c & 11 \\
1 & b & b & 01 \\
0 & c & a & 10 \\
1 & c & b & 10 \\
\hline
\end{tabular}
\end{center}
\caption{Úplně zadaný FSM}
\label{compSpecFSM}
\end{table}

\begin{definition}[Rozkladový pár S - S]
\label{ssPairDef}
Pár rozkladů $\pi_S^1$ a $\pi_S^2$ je párem typu S - S tehdy, pokud oba rozklady jsou rozklady nad množinou stavů a pokud platí:
$$\forall D \in \pi_S^1 \ \exists B \in \pi_S^2 \ : \ \overline{\delta}(D) \subseteq B$$
\end{definition}

\begin{definition}[Rozkladový pár I - S]
\label{isPairDef}
Pár rozkladů je párem typu I - S tehdy, pokud jeden rozklad je rozkladem nad množinou vstupních symbolů a druhý nad množinou stavů a pokud platí:
$$\forall A \in \pi_{I} \ \forall B \in \pi_S \ \exists B'\in \pi_{S}\ : \ \overline{\delta}_A(B) \subseteq B'$$
\end{definition}

\begin{definition}[Rozkladový pár $S \times I$ - S]
\label{sisPairDef}
Rozkladový pár je párem typu $S \times I$ - S tehdy, pokud jeden rozklad je rozkladem nad množinou výstupních symbolů a druhý nad množinou stavů a pokud platí:
$$\forall D \in \pi_{S \times I} \ \exists B \in \pi_S \ : \ \overline{\delta}(D) \subseteq B$$
\end{definition}

\begin{definition}[Rozkladový pár $S \times I$ - O]
\label{sioPairDef}
Rozkladový pár je párem typu $S \times I$ - O tehdy, pokud jeden rozklad je rozkladem nad množinou výstupních symbolů a druhý nad množinou primárních výstupů a pokud platí:
$$\forall D \in \pi_{S \times I} \ \exists C \in \pi_O \ : \ \overline{\lambda}(D) \subseteq C$$
\end{definition}

\begin{example}
\label{partPairsEx}
Mějme automat zadaný tabulkou \ref{compSpecFSM} a rozklad $\pi_{S \times I}$ z příkladu \ref{blockTransOutEx}. Máme-li rozklady $\pi_S = (\overline{a,b};\overline{c})$ a $\pi_O = (\overline{00,11};\overline{01,10})$ tak po aplikaci funcí $\overline{\delta}$ a $\overline{\lambda}$ vidíme, že tyto dvojice jsou rozkladové páry $S \times I$ - S, resp. $S \times I$ - O.
\newline
\end{example}

\begin{definition}[Rozkladová trojice $\pi_I, \pi_S, \pi_{S \times I}$]
\label{partTrinDef}
Trojice rozkladů ($\pi_I, \pi_S, \pi_{S \times I}$) je rozkladovou trojicí automatu M jen tehdy, pokud $(\pi_{S \times I}, \pi_S)$ tvoří $S \times I$ - S pár a $\pi_S \cdot \pi_I \leq \pi_{S \times I}$, popř. $\pi_S \cdot \pi_I \geq \pi_{S \times I}$ (jedno musí být menší nebo rovno druhému).
\end{definition}

Rozkladová trojice  v podstatě reprezentuje vytvořený podautomat. Bloky $\pi_I$ reprezentují vstupní symboly, bloky $\pi_S$ jednotlivé stavy a $\pi_{S \times I}$ výstupní symboly tohoto podautomatu. Samotný proces dekompozice potom spočívá právě ve hledání nejvhodnějších rozkladových trojic, kdy se spojují jednotlivé bloky původního automatu tak, aby jejich počet byl co nejnižší a dekomponovaný automat stále splňoval požadavky na funkčnost původního automatu.

\begin{definition}[Podmínky platnosti obecné dekompozice]
\label{genDecTermsDef}
Mějme konečný automat M a množinu rozkladových trojic nad tímto automatem, nechť $\pi_{S\times I}^{ij}$ je rozklad takový, že $\pi_{S\times I}^{i} \leq \pi_{S\times I}^{ij}$ a ${\pi'_{S\times I}}^j = \prod_{i=1 \ldots n}\pi_{S\times I}^{ij}$. Nechť $\pi_{S\times I} = \prod_{i=1 \ldots n}\pi_{S\times I}^{i}$. Nechť ${\pi_{S\times I}^I}^i$ a ${\pi_{S\times I}^S}^i$ jsou rozklady indukované na množině $S \times I$ pomocí rozkladů $\pi_S^i$ a $\pi_I^i$. Nechť $\pi_{S\times I}^I = \prod_{i=1 \ldots n} {\pi_{S\times I}^{I}}^i$ a $\pi_{S\times I}^S = \prod_{i=1 \ldots n} {\pi_{S\times I}^{S}}^i$. Aby tato dekompozice byla platná, musí platit:
\begin{enumerate}
\item $({\pi_{S \times I}^S}^i \cdot {\pi_{S \times I}^I}^i \cdot {\pi'_{S \times I}}^i, \pi_S^i)$ je rozkladový pár $S \times I$ - S
\item ${\pi_{S \times I}^S}^i \cdot {\pi_{S \times I}^I}^i \cdot {\pi'_{S \times I}}^i \leq \pi_{S \times I}^i$
\item $\pi_{S \times I}^S \cdot \pi_{S \times I}^I \leq {\pi'_{S \times I}}^i$
\item $(\pi_{S \times I}, \pi_O(0))$ je rozkladový pár $S \times I$ - O
\item $\prod_i \pi_S^i = \pi_S(0)$
\end{enumerate}
\end{definition}

Pokud množina rozkladových trojic splňuje tyto podmínky, lze být použita pro tvorbu dekomponovaného automatu. Rozklad $\pi_{S\times I}^{ij}$ reprezentuje informaci produkovanou podautomatem \textit{i} a importovanou podautomatem \textit{j}, ${\pi'_{S\times I}}^j$ je celková informace importovaná podautomatem \textit{j} produkovaná ostatními podautomaty, $\pi_{S\times I}$ je součinem výstupních rozkladů všech podautomatů, stejně jako $\pi_{S\times I}^I$ a $\pi_{S\times I}^S$ jsou součinem rozkladů na množině $S \times I$ indukovaných pomocí množiny S nebo I všech podautomatů realizujících dekompozici.

První pravidlo znamená, že na základě všech vstupních informací musí být možné jednoznačně vypočítat blok rozkladu $\pi_S$, druhé že výstupní rozklad musí být větší (obsahovat méně informace) než maximální možná dostupná vstupní informace (nebylo by možné dosáhnout informace, jež do systému nevstupuje), třetí že imporované informace musí být méně než získané na základě vnitřní struktury podautomatu. Čtvrté potom klade požadavek na jednoznačnost primárního výstupního symbolu, tedy že z průniku množin informací o výstupech z jednotlivých podautomatů musí být možné jednoznačně vypočítat primární výstupním symbol. Páte pravidlo zaručuje, že bude v jakémkoliv okamžiku jednoznačně rozlišitelný aktuální stav celého dekomponovaného automatu a není nutné k dosažení funkčnosti původního automatu, ačkoliv některé aplikace mohou vyžadovat zachování tohoto chování.

\begin{definition}[Podmínky platnosti paralelní dekompozice]
\label{parDecTermsDef}
Množina rozkladových trojic tvoří platnou paralelní dekompozici pokud platí:
\begin{enumerate}
\item $({\pi_{S \times I}^S}^i \cdot {\pi_{S \times I}^I}^i, \pi_S^i)$ je rozkladový pár $S \times I$ - S
\item ${\pi_{S \times I}^S}^i \cdot {\pi_{S \times I}^I}^i \leq \pi_{S \times I}^i$
\item $(\pi_{S \times I}, \pi_O(0))$ je rozkladový pár $S \times I$ - O
\item $\prod_i \pi_S^i = \pi_S(0)$
\end{enumerate}
\end{definition}

\begin{definition}[Podmínky platnosti sériové dekompozice]
\label{serDecTermsDef}
Množina rozkladových trojic tvoří platnou sériovou dekompozici pokud platí:
\begin{enumerate}
\item u prvního podautomatu platí: $({\pi_{S \times I}^S}^1 \cdot {\pi_{S \times I}^I}^1, \pi_S^1)$ je rozkladový pár $S \times I$ - S, u ostatních potom: $({\pi_{S \times I}^S}^i \cdot {\pi_{S \times I}^I}^i \cdot \pi_{S \times I}^{i(i-1)}, \pi_S^i)$ je rozkladový pár $S \times I$ - S
\item u prvního podautomatu platí: ${\pi_{S \times I}^S}^1 \cdot {\pi_{S \times I}^I}^1 \leq \pi_{S \times I}^1$, u ostatních potom: ${\pi_{S \times I}^S}^i \cdot {\pi_{S \times I}^I}^i \cdot \pi_{S \times I}^{i(i-1)} \leq \pi_{S \times I}^i$
\item u všech podautomatů kromě prvního platí: $\pi_{S \times I}^S \cdot \pi_{S \times I}^I \leq \pi_{S \times I}^{i(i-1)}$
\item $(\pi_{S \times I}, \pi_O(0))$ je rozkladový pár $S \times I$ - O
\item $\prod_i \pi_S^i = \pi_S(0)$
\end{enumerate}
\end{definition}

\subsection{Příklad dekompozice úplně zadaného automatu}
Následující příklad je ukázkou, jak pomocí dvojice rozkladových trojic vytvořit dekomponovaný automat o dvou podautomatech. Původní automat je zadán tabulkou \ref{compSpecFSMDec}, sloupec \emph{S} označuje symbol nebo-li řádek automatu, \emph{in} vstupní symbol, \emph{ps} vnitřní stav, \emph{ns} následující stav a \emph{out} výstupní symbol.

\begin{table}[ht]
\begin{center}
\begin{tabular}{c|c|cc|c}
\hline 
S & in & ps & ns & out\\
\hline
1 & 00 & a & a & 00 \\
2 & 01 & a & b & 00 \\
3 & 10 & a & c & 11 \\
4 & 11 & a & d & 01 \\
5 & 00 & b & b & 10 \\
6 & 01 & b & b & 10 \\
7 & 10 & b & d & 01 \\
8 & 11 & b & c & 11 \\
9 & 00 & c & c & 01 \\
10 & 01 & c & b & 01 \\
11 & 10 & c & c & 00 \\
12 & 11 & c & d & 00 \\
13 & 00 & d & d & 10 \\
14 & 01 & d & b & 11 \\
15 & 10 & d & d & 11 \\
16 & 11 & d & c & 00 \\
\hline
\end{tabular}
\end{center}
\caption{Úplně zadaný FSM - příklad dekompozice}
\label{compSpecFSMDec}
\end{table}

Mějme dvě rozkladové trojice reprezentující podautomaty $M_1$ a $M_2$ vypsané níže. Rozklady jsou zde uvedeny jednak jako symboly dané množiny (stavy, vstupní symboly), jednak rozepsány jako množiny řádků a jednak jako symbolické označení jednotlivých bloků (s, i, y, ...), které je dále použito v tabulkách.
\newpage
\noindent podautomat $M_1$:
\begin{description} 
\item $\pi_S^1 = \{\overline{a,b},\overline{c,d}\} = \{\overline{1,2,3,4,5,6,7,8},\overline{9,10,11,12,13,14,15,16}\} = \{s_1,s_2\}$
\item $\pi_I^1 = \{\overline{00}, \overline{01}, \overline{10,11}\} = \{\overline{1,5,9,13}, \overline{2,6,10,16}, \overline{3,4,7,8,11,12,15,16}\} = \{i_1,i_2,i_3\}$ 
\item $\pi_{S\times I}^1 = \{\overline{1,2,5,6}, \overline{3,4,7,8,14,16}, \overline{9,13}, \overline{11,12,15,16}\} = \{y_1,y_2,y_3,y_4\}$
\item
\end{description}
\noindent podautomat $M_2$:
\begin{description} 
\item $\pi_S^2 = \{\overline{a,c},\overline{b,d}\} = \{\overline{1,2,3,4,9,10,11,12},\overline{5,6,7,8,13,14,15,16}\} = \{t_1,t_2\}$ 
\item $\pi_I^2 = \{\overline{00,10}, \overline{01}, \overline{11}\} = \{\overline{1,3,5,7,9,11,13,15}, \overline{2,6,10,14}, \overline{4,8,12,16}\} = \{j_1,j_2,j_3\}$
\item $\pi_{S\times I}^2 = \{\overline{1,3,9,11}, \overline{2,4,10,12}, \overline{5,6,8,14,16}, \overline{7,13,15}\} = \{z_1,z_2,z_3,z_4\}$
\item
\end{description}

Nejprve je potřeba ověřit, zda obě tyto trojice splňují podmínky dekompozice. Snadno přitom zjistíme, že trojice podautomatu $M_2$ nesplňuje podmínku 1. Aby tato podmínka byla splněna, je potřeba importovat navíc informace $5\vert 7, 5\vert 13$ a $5 \vert 15$. Tato informace je dostupná z výstupu podautomatu $M_1$, proto ji přivedeme na vstup $M_2$. Nemusíme navíc importovat celou informaci, ale propojovací člen zajistí redukci informace na ${\pi'_{S\times I}}^2 = \{\overline{1,2,5,6},\overline{3,4,7,8,9,10,11,12,13,14,15,16}\} = \{k_1,k_2\}$. Import této informace potom vede ke splnění všech podmínek pro oba podautomaty.

\begin{table}[ht]
\begin{center}
\begin{tabular}{cc|cc}
\hline 
$X_1$ & $X_2$ & $\pi_I^1$ & $\pi_I^2$\\
\hline
0 & 0 & $i_1$ & $j_1$ \\
0 & 1 & $i_2$ & $j_2$ \\
1 & 0 & $i_3$ & $j_1$ \\
1 & 1 & $i_3$ & $j_3$ \\
\hline
\end{tabular}
\end{center}
\caption{logická funkce vstupního bloku}
\label{logFuncInpBl}
\end{table}

\subsection*{Vstupní blok $\Psi$}
V tomto bloku se uskuteční transformace primárního vstupního symbolu na vstupní symboly jednotlivých podautomatů. Toho lze jednoduše dosáhnout logickou funkcí:

Implementace vstupní funkce vyžaduje zakódování symbolických jmen do nějakého binárního tvaru. Je proto nutno počítat s tím, že pro realizaci funkce bude zapotřebí minimálně $\lceil \log_2 \vert B \vert \rceil$ výstupních proměnných ($\vert B \vert$ označuje počet symbolů).

Stejně jako vstupní funkce je implementováná i výstupní funkce, popř. propojovací člen, i zde je tedy vhodné vyhnout se složitým výrazům s mnoha vstupními resp. výstupními symboly, jejichž implementace by vyžadovala také dekompozici, která sama o sobě bývá poměrně náročná.

\subsection*{Podautomaty $M_1$ a $M_2$}
Při konstrukci jednotlivých podautomatů využijeme skutečnost, že lze pro oba rozklady nad množinou stavů jednoznačně vypočítat blok stavů následujících. Můžeme proto vytvořit tabulku přechodů tak, že vstupní symboly budou tvořeny bloky vstupního rozkladu, stavy určeny bloky rozkladu nad stavy, následující stavy budou potom určeny na základě kombinace aktuálního bloku a vstupního symbolu, stejně jako výstupní symbol. Např. pokud bude aktuální stav $s_1 = \overline{a,b}$ a aktuální vstup $i_3 = \overline{10,11}$, můžeme jednoznačně určit následující blok a výstupní symbol z kombinace symbolů $(\overline{3,4,7,8})$, což je blok $s_2 = \overline{c,d}$ a symbol $y_2 = \overline{3,4,7,8,14,16}$.

\begin{table}[ht]
\begin{center}
\begin{tabular}{cc|cc}
\hline 
in & ps & ns & out\\
\hline
$i_1$ & $s_1$ & $s_1$ & $y_1$ \\
$i_2$ & $s_1$ & $s_1$ & $y_1$ \\
$i_3$ & $s_1$ & $s_2$ & $y_2$ \\
$i_1$ & $s_2$ & $s_2$ & $y_3$ \\
$i_2$ & $s_2$ & $s_1$ & $y_2$ \\
$i_3$ & $s_2$ & $s_2$ & $y_4$ \\
\hline
\end{tabular}
\end{center}
\caption{tabulka přechodů podautomatu $M_1$}
\label{subAutM1Tab}
\end{table}

Tab. \ref{subAutM1Tab} a \ref{subAutM2Tab} představují kompletní přechodové tabulky pro oba podautomaty. Stavy a vstupní a výstupní symboly jsou zde označeny symbolickými hodnotami uvedenými výše u popisu rozkladů. Oproti původnímu automatu je zde viditelné snížení počtu stavů. U prvního podautomatu je také redukce počtu vstupních symbolů, u druhého tomu tak není z důvodu dalšího vstupu importované informace. Počet výsupních symbolů je stejný jako u původního automatu, takže zde nedochází k žádné redukci, ale ani k žádnému nárustu. Ve třetím řádku označuje symbol \uv{-} skutečnost, že všechny vstupní bloky mají v takovéto kombinaci nulový průnik, tudíž tato situace nemůže nastat.

\begin{table}[ht]
\begin{center}
\begin{tabular}{ccc|cc}
\hline 
in & imp in & ps & ns & out\\
\hline
$j_1$ & $k_1$ & $t_1$ & $t_1$ & $z_1$ \\
$j_2$ & $k_1$ & $t_1$ & $t_2$ & $z_2$ \\
$j_3$ & $k_1$ & $t_1$ & - & - \\
$j_1$ & $k_1$ & $t_2$ & $t_2$ & $z_3$ \\
$j_2$ & $k_1$ & $t_2$ & $t_2$ & $z_4$ \\
$j_3$ & $k_1$ & $t_2$ & $t_1$ & $z_3$ \\
$j_1$ & $k_2$ & $t_1$ & $t_1$ & $z_1$ \\
$j_2$ & $k_2$ & $t_1$ & $t_2$ & $z_2$ \\
$j_3$ & $k_2$ & $t_1$ & $t_2$ & $z_2$ \\
$j_1$ & $k_2$ & $t_2$ & $t_2$ & $z_4$ \\
$j_2$ & $k_2$ & $t_2$ & $t_2$ & $z_4$ \\
$j_3$ & $k_2$ & $t_2$ & $t_1$ & $z_3$ \\
\hline
\end{tabular}
\end{center}
\caption{tabulka přechodů podautomatu $M_2$}
\label{subAutM2Tab}
\end{table}

\subsection*{Propojovací člen $con_2$}
Propojovací člen se vytvoří stejně jako vstupní blok logickou funkcí (viz Tab. \ref{logFuncCon}). Jejím úkolem je jen spojit nepotřebnou informaci do jednoho bloku a tím zminimalizovat komplexnost propojení podautomatů.

\begin{table}[ht]
\begin{center}
\begin{tabular}{c|c}
\hline 
$Y_1$ & imp in\\
\hline
$x_1$ & $k_1$ \\
$x_2$ & $k_2$ \\
$x_3$ & $k_2$ \\
$x_4$ & $k_2$ \\
\hline
\end{tabular}
\end{center}
\caption{logická funkce propojovacího členu $con_2$}
\label{logFuncCon}
\end{table}

\subsection*{Výstupní blok $\Theta$}
Stejně jako vstupní blok a propojovací člen je blok tvořen logickou funkcí vstupních proměnných tvořenými výstupy z podautomatů a výstupnímy symboly tvořeny symboly primárního výstupu (Tab. \ref{logFuncOutpBl}).

\begin{table}[ht]
\begin{center}
\begin{tabular}{cc|c}
\hline 
$M_1$ & $M_2$ & out\\
\hline
$y_1$ & $z_1$ & 00\\
$y_1$ & $z_2$ & 01\\
$y_1$ & $z_4$ & 11\\
$y_2$ & $z_1$ & 11\\
$y_2$ & $z_2$ & 00\\
$y_2$ & $z_3$ & 00\\
$y_2$ & $z_4$ & 10\\
$y_3$ & $z_1$ & 01\\
$y_3$ & $z_4$ & 10\\
$y_4$ & $z_1$ & 00\\
$y_4$ & $z_2$ & 00\\
$y_4$ & $z_3$ & 00\\
$y_4$ & $z_4$ & 11\\
\hline
\end{tabular}
\end{center}
\caption{logická funkce výstupního bloku}
\label{logFuncOutpBl}
\end{table}

\section{Dekompozice neúplně zadaného automatu}
V předchozí části byla představena dekompozice úplně zadaného automatu, pracující s  rozklady a determinismem vyplývajícím z jednoznačnosti zadání automatu. V případě neúplně zadaných automatů však toto není dostatečné a je třeba definovat nástroje pro práci s nejednoznačnostmi takovýchto automatů. 

Nejvýraznější změnou je potom zavedení systémů množin místo rozkladů, jelikož rozklady nejsou schopny pokrýt \textit{don't-care} stavy, jelikož tyto symboly by byly poté obsaženy ve více blocích, což odporuje definici rozkladu. Dále je ještě třeba nahradit funkce vypočítávající následující blok funkcemi vypočítávající množinu následujících bloků a představit teorii umožňující tuto dekompozici.

\subsection{Teorie}
Definice uvedené v této části jsou zobecněním definic z části předchozí. Dají se tedy všechny aplikovat i na automat definovaný úplně. Níže uvedená metoda je nejobecnější metodou dekompozice a je aplikovatelná na všechny FSM \cite{JozwSlus01}.

\begin{definition}[Operátor $\overline{\bigcup}$]
\label{UOpDef}
$$\overline{\bigcup}([D_i]_{i=1\ldots n}) = \{B\vert \exists C^1 \subseteq D_1, C^1 \neq 0 \ldots \exists C^n \subseteq D_n, C^n \neq 0 \ : \  B = \bigcup_{i = 1 \ldots n} C^n\}$$
\end{definition}

Operátor $\overline{\bigcup}$ vybere z vektoru podmnožin symbolů S všechny možné neprázdné kombinace. 

\begin{example}
\label{UEx}
\begin{eqnarray}
\overline{\bigcup} = \left( \left[
\begin{array}{c}
\{1,2,3\}\\
\{1,4\}\\
\end{array}
\right] \right) \nonumber
& = & \{\{1\},\{1,2\},\{1,3\},\{1,4\},\{2,4\},\{3,4\},\\ \nonumber
& &\{1,2,3\},\{1,2,4\},\{2,3,4\},\{1,2,3,4\}\} \nonumber
\end{eqnarray}
\newline
\end{example}

\begin{definition}[Operátor $\overline{\bigcap}$]
\label{AOpDef}
$$\overline{\bigcap}([D_i]_{i=1\ldots n}) = \{B\vert \exists C^1 \in \ldots \exists C^n \in D_n \  : \  B = \bigcap_{i = 1 \ldots n} C^n\}$$
\end{definition}

Operátor $\overline{\bigcap}$ přijímá vektor množin podmnožin symbolů S a vybere všechny možné průniky těchto podmnožin. 

\begin{example}
\label{AEx}
$$\overline{\bigcap} = \left( \left[
\begin{array}{c}
\{1\}\{1,2\}\{2,3\}\{4\}\\
\{1,2,3\}\{4,5\}\\
\{1,2,4,5\}\\
\end{array}
\right] \right)
= \{\{1\}\{1,2\}\{2\}\{4\}\}
$$
\newline
\end{example}

Pomocí těchto dvou nástrojů můžeme zavést upravený pojem \textit{systémová přechodová funkce}, která nahrazuje \textit{blokovou přechodovou funkci} a pojem S $\times$ I - S systémový pár:

\begin{definition}[Systémová přechodová funkce $\Lambda^{\phi_S}$]
\label{SysTrFuncDef}
$$\Delta^{\phi_S}(D_i) = \{B' \in \phi_S\vert \exists B'' \in \overline{\delta}(D) \  : \  B'' \subseteq B'\}$$
\end{definition}

Tato funkce vybere ze systému množin nad množinou stavů všechny možné množiny následujících stavů.

\begin{table}[ht]
\begin{center}
\begin{tabular}{c|cc|c}
\hline 
in & ps & ns & out\\
\hline
0 & a & b,c & 00,11 \\
1 & a & a & 01 \\
0 & b & a,c & 11 \\
1 & b & b & 01 \\
0 & c & a & 10,01 \\
1 & c & b & 10,01,11 \\
\hline
\end{tabular}
\end{center}
\caption{Neúplně zadaný FSM}
\label{incSpecFSMTab2}
\end{table}

\begin{example}
\label{SysTrFuncEx}
Mějme FSM zadaný tabulkou \ref{incSpecFSMTab2} a systém množin definovaný nad množinou výstupních symbolů $\phi_{S \times I} = \{\overline{(a,0),(b,0)};\overline{(a,1),(b,1),(c,0),(c,1)}\} = \{D_1,D_2\}$ potom platí:
\begin{description}
\item $\Delta(D_1) = \overline{\bigcup}
\left[
\begin{array}{c}
\delta(a,0)\\ \delta(b,0)\\
\end{array}
\right]
= \overline{\bigcup}
\left[
\begin{array}{c}
(b,c)\\
(a,c)\\
\end{array}
\right]
= \{\{a,b\};\{a,c\};\{b,c\};\{c\};\{a,b,c\}\}
$
\item $\Delta(D_2) = \overline{\bigcup}
\left[
\begin{array}{c}
\delta(a,1)\\ \delta(b,1)\\ \delta(c,0)\\ \delta(c,1)\\
\end{array}
\right]
= \overline{\bigcup}
\left[
\begin{array}{c}
(a)\\ (b)\\ (a)\\ (b)\\
\end{array}
\right]
= \{\{a,b\}\}
$
\end{description}
\end{example}

\begin{definition}[Systémový pár S $\times$ I - S]
\label{SysPairSSDef}
$$\forall D \in \phi_{S\times I}\  : \  \Delta^{\phi_S}(D) \neq 0$$
\end{definition}

Definice vyjadřuje fakt, že aby byla dvojice S $\times$ I - S systémovým párem, stačí pouze, aby mezi množinami následujících bloků byl alespoň jeden podmnožinou bloku či blokem $\phi_S$.

\begin{example}
\label{SysPairSSEx}
Mějme FSM zadaný tabulkou \ref{incSpecFSMTab2} a systém množiny $\phi_{S \times I}$ z příkladu \ref{SysTrFuncEx} a $\phi_S = \{\overline{a,b,c};\overline{b,c}\}$. Můžeme vidět, že v připadě obou bloků $\phi_{S \times I}$ jsou mezi množinamy následujících stavů podmnožiny bloků systému množin $\phi_S$ a tudíž tyto dva systémy množin tvoří systémový rozklad.
\newline
\end{example}

Výše zmíněné funkce jsou však stále nedostatečné pro jednoznačný výpočet následujícího stavu dekomponovaného automatu. Jelikož každý podautomat by mohl zvolit libovolnou podmnožinu následujících stavů a průnik těchto následujících stavů všech podautomatů by mohl být prázdný, je třeba zajistit, aby každý podautomat přešel do stavu reprezentujícího podmnožinu stavů, do které by přešel i původní automat. To vede k pojmu synchronizovaná množina systémových páru S $\times$ I - S. 

\begin{definition}[Synchronizovaná množina S $\times$ I - S páru]
\label{SynchSetSSDef}
$([\phi^i_{S \times I}]_i,[\phi^i_S]_i)$ je Synchronizovaný systémový pár jen tehdy, pokud:
\begin{enumerate}
\item Pokud je systémovým párem podle definice \ref{SysPairSSDef}
\item Pokud průnik aktuálních bloků celé množiny $\phi^i_{S \times I}$ vede do průniku všech následujících bloků $\phi^i_S$ každého páru z množiny.
\end{enumerate}
\end{definition}

Podobně potom můžeme definovat i funkce a pojmy pro výpočet výstupních symbolů dekomponovaného automatu. I zde platí, že tyto definice budou platit i pro úplně zadaný automat.

\begin{definition}[Bloková výstupní funkce]
\label{incBlOutFuncDef}
$$\overline{\lambda} : 2^{S \times I} \rightarrow 2^O \textrm{ a } \overline{\lambda}(D) = \overline{\bigcup}_{d \in D} \lambda(d)$$
\end{definition}

Bloková výstupní funkce pro neúplný automat se liší od výstupní funkce pro úplný automat tím, že nevypočítá jeden výstup ale množinu výsutpů.

\begin{definition}[Systémová výstupní funkce]
\label{incSysOutFuncDef}
$$\Lambda^{\phi_O} : 2^{S \times I} \rightarrow 2^O \textrm{ a } \Lambda(D) = \{C \in \phi_O \mid \exists C' \in \overline{\lambda}(D) : C' \subseteq C\}$$
\end{definition}

Systémová výstupní funkce vrací blok systému množin nad primárními výstupními symboly, který obsahuje výstupní symboly získané pomocí blokové výstupní funkce.

\begin{example}
\label{incSysOutFuncEx}
Mějme automat a systém množin zadané v příkladu \ref{SysTrFuncEx}, potom můžeme zjistit:
\begin{description}
\item $\Lambda(D_1) = \overline{\bigcup}
\left[
\begin{array}{c}
\lambda(a,0)\\ \lambda(b,0)\\
\end{array}
\right]
= \overline{\bigcup}
\left[
\begin{array}{c}
(00,11)\\
(11)\\
\end{array}
\right]
= \{\{00,11\};\{11\}\}
$
\item $\Lambda(D_2) = \overline{\bigcup}
\left[
\begin{array}{c}
\lambda(a,1)\\ \lambda(b,1)\\ \lambda(c,0)\\ \lambda(c,1)\\
\end{array}
\right]
= \overline{\bigcup}
\left[
\begin{array}{c}
(01)\\ (01)\\ (10,01)\\ (10,01,11)\\
\end{array}
\right]
= \{\{01\};\{10,01\};\{01,11\};\{10,01,11\}\}
$
\end{description}
\end{example}

\begin{definition}[Systémový pár S $\times$ I - O]
\label{SysPairSODef}
$$\forall D \in \phi_{S\times I}\  : \  \Lambda^{\phi_0}(D) \neq 0$$
\end{definition}

Definice vyjadřuje fakt, že aby byla dvojice S $\times$ I - O systémový pár stačí pouze, aby mezi množinami výstupních symbolů byl alespoň jeden podmnožinou bloku či celým blokem $\phi_O$.

\begin{example}
\label{SysPairSOEx}
Mějme automat a systém množin zadané v příkladu \ref{SysTrFuncEx} a $\phi_O = \{\overline{01};\overline{11};\overline{00,10}\}$, můžeme vidět, že pro $\Lambda^{\phi_O}(D_1) = \{\overline{11}\} \neq 0$ a pro $\Lambda^{\phi_O}(D_2) = \{\overline{01}\} \neq 0$ a tudíž $\phi_{S \times I}$ a $\phi_O$ tvoří systémový pár S $\times$ I - O.
\newline
\end{example}

Výše zmíněné pojmy pak vedou k zavedení tzv. \textit{specializace systému množin}. Zohledňuje fakt, že díky existenci don't care stavů ve výstupních symbolech je možné zredukovat množinu výstupních symbolů zrušením těch symbolů, které mohou být nahrazeny právě díky možnosti vždy vybrat tento a nebo nějaký jiný symbol.

\begin{definition}[Specializace systému množin]
\label{SysSpecDef}
Systém množin $\phi_{S'}$ je specializací systému množin $\phi_S$ tehdy, pokud S' je podmnožinou S a pokud:
$$\forall A \in \phi_S \exists B \in \phi_{S'} : B \subseteq A \ \wedge \ 
\forall B \in \phi_{S'} \exists A \in \phi_S : A \supseteq B$$ 
\end{definition}

Jak již bylo zmíněno výše, použití systémů množin má ten následek, že jeden symbol může být ve více blocích. Pokud by dekomponovaný automat měl přejít do stavu, který je ve více blocích, nebylo by možné vybrat jednoznačně blok, do kterého by se měl daný podautomat přesunout, proto je třeba zavést tzv. \textit{vícestavovou realizaci automatu M}.

\begin{definition}[Vícestavová realizace konečného automatu]
\label{MultStateDef}
Neúplně zadaný automat $M_l$ je vícestavovou realizací automatu M jen tehdy, pokud:
\begin{enumerate}
\item Množiny vstupních a výstupních symbolů obou automatů jsou shodné
\item Existuje funkce $L : S \rightarrow S_l$ a inverzní funkce $L'$ realizující vazby mezi stavy M a $M_l$
\item $\delta_l$ a $\lambda_l$ realizují vícestavové chování $M_l$
\end{enumerate}
\end{definition}

\begin{example}
\label{MultStateEx}
V tabulce \ref{multStateFSMTab} je zadán FSM tvořící vícestavovou realizace FSM z Tab. \ref{incSpecFSMTab2}. Stavy \emph{a} a \emph{c} byly rozděleny na stavy \emph{a1, a2} a \emph{c1, c2} (tyto stavy nazýváme indexované). Je zde také dobře vidět, že následující stavy a výstupní symboly jsou vždy podmnožinou původních stavů. \newline
\end{example}

\begin{table}[ht]
\begin{center}
\begin{tabular}{c|cc|c}
\hline 
in & ps & ns & out\\
\hline
0 & a1 & b,c1,c2 & 00 \\
1 & a1 & a2 & 01 \\
0 & a2 & b,c2 & 00,11 \\
1 & a2 & a1 & 01 \\
0 & b & a1,c & 11 \\
1 & b & b & 01 \\
0 & c1 & a1,a2 & 10,01 \\
1 & c1 & b & 10,01,11 \\
0 & c2 & a2 & 10 \\
1 & c2 & b & 01,11	 \\
\hline
\end{tabular}
\end{center}
\caption{Vícestavová realizace neúplně zadaného FSM}
\label{multStateFSMTab}
\end{table}

Vícestavová realizace FSM nám umožňuje realizovat automat reprezentovaný systémem množin a s minimálně jedním stavem ve více blocích jelikož umožňuje rozlišení mezi těmito bloky. Koncept vícestavové realizace je možný zavést i pro úplně zadané automaty, jelikož i při jejich dekompozici lze nalézt místo rozkladů systémy množin a využít jich pro zlepšení dekompozice. Vícestavová realizace nám dáva větší svobodu ve výběru následujícího stavu a toto je pak možné zohlednit při hledání rozkladové trojice.

Pro využití vícestavové realizace je třeba rozšířit množiny stavů S na $S_l$ a výstupních symbolů z S $\times$ I na $S_l \times I$ a dále je potřeba definovat funkce pro přechod mezi oběma automaty:

\begin{definition}[Indexovaná systémová přechodová funkce]
\label{LabSysTransDef}
$$\Delta^{\phi_{S_l}} : 2^{\phi_{S_l \times I}} \rightarrow 2^{\phi_{S_l}}
\textrm{ a } 
\Delta^{\phi_{S_l}}(D) = \{B'_l \in \phi_{S_l} \mid \exists B' \in \overline{\delta}(L'(D)) : B' \subseteq L'(B'_l)$$
\end{definition}

\begin{definition}[Indexovaná systémová výstupní funkce]
\label{LabSysPutDef}
$$\Lambda^{\phi_O} : 2^{\phi_{S_l \times I}} \rightarrow 2^{\phi_{O}}
\textrm{ a } 
\Delta^{\phi_0}(D) = \{C \vert C \in \phi_{O} \wedge \exists C' \in \overline{\lambda}(L'(D)) : C' \subseteq C\}$$
\end{definition}

\begin{definition}[Systémový pár $S_l \times$ I - $S_l$]
\label{SysPairSISlDef}
$$\forall D \in \phi_{S_l\times I}\  : \  \Delta^{\phi_{S_l}}(D) \neq 0$$
\end{definition}

\begin{definition}[Systémový pár $S_l \times$ I - O]
\label{SysPairSIlODef}
$$\forall D \in \phi_{S_l\times I}\  : \  \Lambda^{\phi_0}(D) \neq 0$$
\end{definition}

Jelikož se v systému nachází dvě množiny stavů S a $S_l$, je třeba ještě zavést pojem systémového páru S - $S_l$, zohledňující fakt, že množina $S_l$ může obsahovat jen kopie stavů obsažených v S.

\begin{definition}[Systémový pár S - $S_l$]
\label{SysPairSSlDef}
$$\forall D \in \phi_{S_l} \exists B \in \phi_S \  L'(D) \subseteq B$$
\end{definition}

Pomocí výše zmíněných definic si můžeme upravit podmínky platné dekompozice úplně zadaného automatu také pro neúplně zadaný podatutomat:

\begin{definition}[Podmínky platnosti obecné dekompozice]
\label{genIncDecTermsDef}
Mějme konečný automat M a rozkladovou trojici tohoto automatu, nechť $\phi_{S_l\times I}^{ij}$ je rozklad takový, že $\phi_{S_l\times I}^{i} \leq \phi_{S_l\times I}^{ij}$ a ${\phi'_{S_l\times I}}^j = \prod_{i=1 \ldots n}\phi_{S_l\times I}^{ij}$. Nechť ${\phi_{S_l\times I}^S}^i$ a ${\phi_{S_l\times I}^I}^i$ jsou systémové páry indukované na množině $S_l \times I$ pomocí rozkladů $\phi_S^i$ a $\phi_I^i$. Nechť $\phi_{S_l\times I}^I = \prod_{i=1 \ldots n} {\phi_{S_l\times I}^{I}}^i$ a $\phi_{S_l\times I}^S = \prod_{i=1 \ldots n} {\phi_{S_l\times I}^{S}}^i$. Nechť ${\phi_{S_l \times I}^{in}}^i = {\phi_{S_l \times I}^I}^i \cdot {\phi_{S_l \times I}^{S_l}}^i \cdot {\phi'_{S_l \times I}}^i$.\newpage
Pokud bude pro každý podautomat existovat mapovací funkce $L^i : \phi_S^i \rightarrow \phi_{S_l}^i$, množina systémových trojic bude tovřit platnou dekompozici pokud bude splňovat následující podmínky:
\begin{enumerate}
\item $\Big([{\phi_{S_l \times I}^{in}}^i]_i, [\phi_{S_l}^i]_i\Big)$ je synchronizovaný systémový pár $S_l \times I$ - $S_l$
\item ${\phi_{S_l \times I}^{in}}^i \leq {\phi_{S_l \times I}}^i$
\item $\phi_{S_l \times I}^{S_l} \cdot \phi_{S_l \times I}^I \leq {\phi'_{S_l \times I}}^i$
\item $\phi_O$ má specializaci $\phi_{O'}$ a $(\phi_{S_l \times I}, \phi_{O'}))$ je rozkladový pár $S_l \times I$ - O'
\item $(\prod_i \phi_{S_l}^i = \pi_S(0))$ je $S_l$ - S systémový pár
\end{enumerate}
\end{definition}

Vysvětlení výše definovaných pojmů je analogické úplně zadanému automatu, stejně jako úpravy pro paralelní či sériovou dekompozici. Stejně tak 5. podmínka musí být splněna pouze má-li zůstat zachována schopnost rozeznat aktuání stav. Důkaz platnosti tvrzení viz \cite{JozwSlus01}.

\begin{subsection}{Příklad dekompozice neúplně zadaného automatu}
\label{incDecExSec}

\begin{table}[ht]
\begin{center}
\begin{tabular}{c|cc|c}
\hline 
in & ps & ns & out\\
\hline
00 & a & a & 00 \\
01 & a & a & 11,01 \\
10 & a & a & 11,01 \\
11 & a & c & 11 \\
00 & b & a,b & 11 \\
01 & b & a & 01 \\
10 & b & a & 01 \\
11 & b & c & 11 \\
00 & c & b & 00 \\
01 & c & a & 11,01 \\
10 & c & a & 11,01 \\
11 & c & c & 11 \\
00 & d & d & 00 \\
01 & d & a & 11,01 \\
10 & d & a & 11,01 \\
11 & d & c & 11 \\
00 & e & d,e & 11 \\
01 & e & a & 01 \\
10 & e & a & 01 \\
11 & e & c & 11 \\
\hline
\end{tabular}
\end{center}
\caption{Neúplně zadaný FSM - příklad dekompozice}
\label{incompSpecFSMDec}
\end{table}

Mějme automat M zadaný tabulkou \ref{incompSpecFSMDec} a množinu dvou systémovách trojic se systémy množin nad množinou stavů $\phi_S^1 = \{\overline{a,b};\overline{a,c};\overline{d,e}\}$ a $\phi_S^2 = \{\overline{a,c,d};\overline{a,b,e}\}$. Je tedy třeba indexovat stav \emph{a}. Potom můžeme namapovat jednotlivé řádky dle tabulky \ref{symMapDec}. Na tento mapovací prostor je možné namapovat i ostatní systémy množin (stejně bylo mapováno i u úplně zadaného automatu), tím se vytvoří indukované systémy množin ${\phi_{S_l\times I}^S}^i$ a ${\phi_{S_l\times I}^I}^i$.

\begin{table}[ht]
\begin{center}
\begin{tabular}{c|cccc}
\hline 
 & 00 & 01 & 10 & 11\\
\hline
1a & 0 & 1 & 2 & 3 \\
1a & 4 & 5 & 6 & 7 \\
b & 8 & 9 & 10 & 11 \\
c & 12 & 13 & 14 & 15 \\
d & 16 & 17 & 18 & 19 \\
e & 20 & 21 & 22 & 23 \\
\hline
\end{tabular}
\end{center}
\caption{Mapování řádků na symboly}
\label{symMapDec}
\end{table}

\noindent podautomat $M_1$:
\begin{description} 
\item $\phi_I^1 = \{\overline{00},\overline{01,10,11}\} = \{i_1,i_2\}$
\item $\phi_{S_l}^1 = \{\overline{a1,b}, \overline{a2,c}, \overline{d,e}\} = \{s_1,s_2,s_3\}$ 
\item $\phi_{S_l\times I}^1 = \{\overline{0,8,16,20}, \overline{4,12}, \overline{1,2,3,5,6,7,9,10,11,13,14,15,17,18,19,21,22,23}\} = \{y_1,y_2,y_3\}$
\end{description}
\noindent podautomat $M_2$:
\begin{description} 
\parindent = 24pt
\item $\phi_I^2 = \{\overline{00,11},\overline{01,10}\} = \{j_1,j_2\}$ 
\item $\phi_{S_l}^2 = \{\overline{a1,c,d}, \overline{a2,b,e}\} = \{t_1,t_2\}$
\item $\phi_{S_l\times I}^2 = \{\overline{0,1,2,3,4,7,11,12,13,14,15,16,17,18,19,23},$\newline \indent
$\overline{1,2,5,6,8,9,10,13,14,17,18,20,21,22}\} = \{z_1,z_2\}$
\end{description}

Konstrukce tohoto dekomponovaného automatu bude složitější o konstrukci indexovací funkce, ve které se však může zredukovat množina vstupních i výstupních symbolů. Jinak se bude postupovat stejně jako v případě úplně zadaného automatu.

Nejprve je opět potřeba zkontrolovat platnost dekompozice. Aby tato množina systémových trojic splnila podmínky platné dekompozice, musí se importovat informace z podautomatu $M_1$ do $M_2$, čímž se zvětší sice počet vstupů do $M_2$, ale na druhou stranu není třeba vytvářet žádný propojovací člen, protože stačí výstup z $M_1$ přivést na vstup $M_2$ (méně informace nestačí pro splnění podmínky). 

\begin{figure}[ht]
\begin{center}
\includegraphics{mult_dec}
\caption{Struktura dekomponovaného FSM s vícestavovou realizací}
\label{incMulPic}
\end{center}
\end{figure}

\subsection*{Konstrukce indexovaného automatu $M_l$}
Množina vstupních symbolů může být v tomto automatu redukována na symboly potřebné podautomaty. Tyto lze získat součinem všech systémů množin $\phi_I^i$, což je v našem případě následující: 
$$\phi_I = \phi_I^1 \cdot \phi_I^2\ = \{\overline{00};\overline{11};\overline{01,10}\}$$
Stejně tak je možné upravit množinu stavů a výstupních symbolů. V našem případě množina stavů zůstává beze změn (součin je nulový systém množin) a množina výstupů po vynásobení obou systémů je rovna:
\begin{eqnarray}
\phi_{S_l \times I}& = &\{\overline{0,16}(r_1);\overline{8,20}(r_2);\overline{4,12}(r_3);\nonumber \\
 & & \overline{1,2,3,7,11,13,14,15,17,18,19,23}(r_4);\nonumber \\ 
 & & \overline{1,2,5,6,9,10,13,14,17,18,21,22}(r_5)\} \nonumber
\end{eqnarray}

Pomocí těchto systémů množin jsme potom schopni vytvořit přechodovou tabulku automatu $M_l$. Pokud při tvorbě tabulky narazíme na stav, který je při indexování rozdělen na dva, je potřeba v množině násleujících stavů pro tento řádek uvést oba, resp. všechny tyto indexované stavy jako možné.

Pokud máme již vytvořenou tabulky, můžeme vytvořit přechody mezi původním automatem a podautomaty (struktura dekomponovaného automatu s vícestavovou realizací viz~Obr.~\ref{incMulPic}). Tyto přechody se opět dají realizovat pomocí logické funkce stejně jako u úplně zadaného automatu.
\end{subsection}

\subsection*{Konstrukce ostatních částí dekomponovaného automatu}
Konstrukce zbývajících částí automatu se provádí prakticky stejně jako u úplně zadaného automatu jen s tím rozdílem, že při vyhodnocování následujících stavů a výstupních symbolů je třeba použít systémovou přechodovou a výstupní funkci definovanou v \ref{SysTrFuncDef}, resp. v \ref{incSysOutFuncDef}. 