Isomorphism of the characteristic semigroup of the direct sum and direct product of strongly connected asynchronous automata and fixed analogues of their extensions

The article demonstrates that the characteristic semigroup of the direct sum and direct product of strongly connected asynchronous automata and fixed analogues of their extensions are isomorphic. Given that the characteristic semigroup determines the information processing capability, the direct sum and direct product can be considered as implementations of sequential and parallel computations, respectively. The obtained results imply that this capability does not depend on the sequential or parallel implementation (the same number of abstraction classes of the corresponding characteristic semigroups).The publication [7] presents considerations regarding automata from the DFASC2 (deterministic finite asynchronous strongly connected) and EXT DFASC (deterministic finite asynchronous strongly connected extensions) classes. Works [9, 10, 11] present theorems on:- The complexity of the characteristic semigroup of the direct sum and direct product of strongly connected asynchronous DFASC automata [9], (…)

Isomorphism of the characteristic semigroup of the direct sum and direct product of strongly connected asynchronous automata and fixed analogues of their extensions – PDF file for download