Algebraic Theory of Automata Networks: An Introduction (SIAM by Pal Domosi, Chrystopher L. Nehaniv

By Pal Domosi, Chrystopher L. Nehaniv

Algebraic concept of Automata Networks investigates automata networks as algebraic constructions and develops their concept in accordance with different algebraic theories. Automata networks are investigated as items of automata, and the basic ends up in regard to automata networks are surveyed and prolonged, together with the most decomposition theorems of Letichevsky, and of Krohn and Rhodes. The textual content summarizes an important result of the prior 4 a long time concerning automata networks and provides many new effects came across because the final ebook in this topic was once released. a number of new tools and detailed suggestions are mentioned, together with characterization of homomorphically whole periods of automata less than the cascade product; items of automata with semi-Letichevsky criterion and with none Letichevsky standards; automata with keep an eye on phrases; primitive items and temporal items; community completeness for digraphs having all loop edges; whole finite automata community graphs with minimum variety of edges; and emulation of automata networks through corresponding asynchronous ones.

Show description

Read Online or Download Algebraic Theory of Automata Networks: An Introduction (SIAM Monographs on Discrete Mathematics and Applications, 11) PDF

Similar mathematics books

Differential Equations & Control Theory

In response to papers on the Intl Workshop on Differential Equations and optimum keep an eye on held lately at Ohio college, Athens.

Additional info for Algebraic Theory of Automata Networks: An Introduction (SIAM Monographs on Discrete Mathematics and Applications, 11)

Example text

L. Nehaniv [1992,1995,1996]). 18 due to C. Jordan [1869] and O. Holder [1889]. The other statements are new but elementary. This page intentionally left blank Chapter 2 Directed Graphs, Automata, and Automata Networks In this chapter we introduce the concepts of directed graphs (digraphs), automata, networks constructed from them, and related algebraic structures used for studying automata that communicate according to the links of an interconnection digraph. Techniques and concepts developed here will be used throughout the monograph.

A digraph D = (V, E) is penultimately permutation complete with respect to vertex vo V if and only if for each permutation p of the vertices V \ {v0}, there is a transformation p' S(D) with p'(v) = p(v)forall v V \ {v0}. Proof. 3(2). We note that we could also follow this interpretation: Let us say that a vertex is free if it is not covered by any coin. ) In this case we would always have exactly one free vertex. , vj is not covered by any coin). The free (empty) vertex vj is changed for a coin ci if there is an edge (v k , vj) E such that vk is covered by ci and moreover vj is free.

If there does not exist any vertex u having the above property, then we identify u with the vertex v. If q1 = q2, then two paths u q1 and q2 u form a cycle C = (C, EC) where distinctness of the vertices follows from minimality. If q1 q2, then in V there is a path from q\ to q2 as D' is strongly connected. Then the three paths u q1, q1 q2, and q2 u form a cycle C = (C, EC). Let p denote the (only) C-compatible cyclic permutation and consider Moreover, for every allowed transformation Let v' with respect to D' define V be an arbitrary vertex of D'.

Download PDF sample

Rated 4.74 of 5 – based on 39 votes