Meno:  Peter


Priezvisko:  Gaži


Názov:  Parallel decompositions of finite automata


Vedúci:  Prof. RNDr. Branislav Rovan, PhD.


Rok:  2006


Blok:  MMI


Kľúčové slová:  deterministic finite automaton, parallel decomposition, decomposition of state behavior


Abstrakt:  We have studied the possibilities of parallel decomposition of a
deterministic finite automaton into a pair of automata such that they are both simpler
then the original one, but the results of their independent computations on any input word
can determine the result of computation of the original automaton. We have used the
results describing the decompositions of sequential machines, and also defined
several new kinds of decomposition. Then we have proved some conditions for existence of such
decompositions and inspected relationships between them. We have also studied the classes of
undecomposable and perfectly decomposable languages and we have shown that there exist
automata for most degrees of decomposability from the interval given by these two
boundaries.

