Názov:Parallel decompositions of finite automata
Vedúci:Prof. RNDr. Branislav Rovan, PhD.
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.

Súbory diplomovej práce: