Algebraic Theory of Automata Networks: A Introduction
Algebraic Theory of Automata Networks investigates automata networks as algebraic structures and develops their theory in line with other algebraic theories. Automata networks are investigated as products of automata, and the fundamental results in regard to automata networks are surveyed and extended, including the main decomposition theorems of Letichevsky, and of Krohn and Rhodes. The text summarizes the most important results of the past four decades regarding automata networks and presents many new results discovered since the last book on this subject was published. Several new methods and special techniques are discussed, including characterization of homomorphically complete classes of automata under the cascade product; products of automata with semi-Letichevsky criterion and without any Letichevsky criteria; automata with control words; primitive products and temporal products; network completeness for digraphs having all loop edges; complete finite automata network graphs with minimal number of edges; and emulation of automata networks by corresponding asynchronous ones.
What people are saying - Write a review
We haven't found any reviews in the usual places.
ao-product arbitrary assume asynchronous autonomous cascade product cellular automata class of automata coin complete digraph complete with respect component computation Consider Corollary counter cycle cyclic permutation defined denote diagonal product digraph Domosi elements Esik exists feedback functions finite automata graph homomorphic image homomorphic representations homomorphically represents homomorphically simulates idempotent identity element implies input letter Krohn-Rhodes theorem Lemma Letichevsky criteria loop edges mapping monoid Moreover n-complete node nonempty nontrivial normal subgroup pair penultimately permutation complete permutation automaton permutation group positive integer prefix product of automata product of factors Proposition prove quasi-direct product represented homomorphically reset automaton respect to homomorphic satisfying Letichevsky's criterion semi-Letichevsky criterion simple group single-factor product state-subautomaton strongly connected subautomaton subgroup subsemigroup subset Suppose symmetric group transformation semigroup update vertex wreath product xn+i