Издательство Springer, 2005, -268 pp.
An automata network is a collection of automata connected together according to a directed graph D. The vertices of D are considered as automata and the edges indicate the existence of communication links. Thus D has no parallel edges. Each automaton can change its state at discrete time steps as a local transition function of the states and a global input, and synchronous action of the local state transitions defines a global transition on the entire network. We investigate automata networks as algebraic structures and develop their theory in line with other algebraic theories, such as those of semigroups, groups, rings, and fields.
In this monograph we restrict ourselves almost exclusively to finite automata networks (with notable exceptions in the study of asynchronous networks) for two reasons. This introductory monograph is devoted to the most fundamental cases. These occur when the network is finite: there are only finitely many component automata in the network (i.e., the interconnection digraph D is finite) and all component automata are also finite, having only finitely many states. On the other hand, finiteness is a natural constraint arising for real-world networks, including those in computational and technical applications. Algebraic interpretations arise from consideration of the semigroup of transformations induced on the set of states by all possible finite sequences of inputs, but they also enter the subject in other ways when we study division relations of automata and the completeness of networks.
We also investigate automata networks as "products of automata,"i.e., as compositions of automata obtained by cascading without feedback or with feedback of various restricted types, or, most generally, with the feedback dependencies controlled by an arbitrary directed graph. We survey and extend the fundamental results in regard to automata networks, including the main decomposition theorems of Letichevsky, of Krohn and Rhodes, and others. These theorems also indicate what basic components are necessary and sufficient for the synthesis of particular finite computational structures using particular types of networking, including limitations on feedback and number of local connections in the (directed graph of) communication links.
We deal with classes of finite automata that are complete in one or several of four different senses. In particular, we consider completeness with respect to homomorphic representation, isomorphic representation, homomorphic simulation, and isomorphic simulation. In all four types of completeness, it is understood that not necessarily is the class itself complete but rather that its closure under a given type of product is complete.
In other words, we investigate complete classes of automata, i.e., classes of automata whose closure under various notions of products allow the simulation of ordinary automata in various senses. The questions arise naturally when one tries to understand how to decompose or synthesize complicated automata as combinations of simpler ones. An issue of central importance is to understand the behavior and computational power of automata networks having given restricted types of communication links.
This monograph is an effort in this direction. We characterize the structure of the communication links of those whose finite automata networks (as several product types of automata) which have as simple a structure as possible, and representational power preserves the representational power of the most general networks or of the (general) cascade networks. Real-world examples of automata networks include computer networks, electrical networks, transport networks, the Inteet, and genetic regulatory networks. Many of these can modify their inteal structure in the course of their functioning. Our book covers the foundations of what is currently known about automata networks, leading the reader to the forefront of research in many areas. It also lays a foundation upon which a rigorous theory of dynamic automata networks (that change their topology, member components, and functioning) may one day be constructed. We also pay some attention to the case in which network can cyclically modify its inner structure during its work as well as to asynchronous automata networks.
Preliminaries
Directed Graphs, Automata, and Automata Networks
Krohn-Rhodes Theory and Complete Classes
Without Letichevsky's Criterion
Letichevsky's Criterion
Primitive Products and Temporal Products
Finite State-Homogeneous Automata Networks and Asynchronous Automata Networks
An automata network is a collection of automata connected together according to a directed graph D. The vertices of D are considered as automata and the edges indicate the existence of communication links. Thus D has no parallel edges. Each automaton can change its state at discrete time steps as a local transition function of the states and a global input, and synchronous action of the local state transitions defines a global transition on the entire network. We investigate automata networks as algebraic structures and develop their theory in line with other algebraic theories, such as those of semigroups, groups, rings, and fields.
In this monograph we restrict ourselves almost exclusively to finite automata networks (with notable exceptions in the study of asynchronous networks) for two reasons. This introductory monograph is devoted to the most fundamental cases. These occur when the network is finite: there are only finitely many component automata in the network (i.e., the interconnection digraph D is finite) and all component automata are also finite, having only finitely many states. On the other hand, finiteness is a natural constraint arising for real-world networks, including those in computational and technical applications. Algebraic interpretations arise from consideration of the semigroup of transformations induced on the set of states by all possible finite sequences of inputs, but they also enter the subject in other ways when we study division relations of automata and the completeness of networks.
We also investigate automata networks as "products of automata,"i.e., as compositions of automata obtained by cascading without feedback or with feedback of various restricted types, or, most generally, with the feedback dependencies controlled by an arbitrary directed graph. We survey and extend the fundamental results in regard to automata networks, including the main decomposition theorems of Letichevsky, of Krohn and Rhodes, and others. These theorems also indicate what basic components are necessary and sufficient for the synthesis of particular finite computational structures using particular types of networking, including limitations on feedback and number of local connections in the (directed graph of) communication links.
We deal with classes of finite automata that are complete in one or several of four different senses. In particular, we consider completeness with respect to homomorphic representation, isomorphic representation, homomorphic simulation, and isomorphic simulation. In all four types of completeness, it is understood that not necessarily is the class itself complete but rather that its closure under a given type of product is complete.
In other words, we investigate complete classes of automata, i.e., classes of automata whose closure under various notions of products allow the simulation of ordinary automata in various senses. The questions arise naturally when one tries to understand how to decompose or synthesize complicated automata as combinations of simpler ones. An issue of central importance is to understand the behavior and computational power of automata networks having given restricted types of communication links.
This monograph is an effort in this direction. We characterize the structure of the communication links of those whose finite automata networks (as several product types of automata) which have as simple a structure as possible, and representational power preserves the representational power of the most general networks or of the (general) cascade networks. Real-world examples of automata networks include computer networks, electrical networks, transport networks, the Inteet, and genetic regulatory networks. Many of these can modify their inteal structure in the course of their functioning. Our book covers the foundations of what is currently known about automata networks, leading the reader to the forefront of research in many areas. It also lays a foundation upon which a rigorous theory of dynamic automata networks (that change their topology, member components, and functioning) may one day be constructed. We also pay some attention to the case in which network can cyclically modify its inner structure during its work as well as to asynchronous automata networks.
Preliminaries
Directed Graphs, Automata, and Automata Networks
Krohn-Rhodes Theory and Complete Classes
Without Letichevsky's Criterion
Letichevsky's Criterion
Primitive Products and Temporal Products
Finite State-Homogeneous Automata Networks and Asynchronous Automata Networks