| 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.
|
|---|