The chapter presents the principles of functioning of asynchronous cellular automata with a group of cells united in a colony. The rules of the formation of colonies of active cells and methods to move them along the field of a cellular automaton are considered. Each formed colony of active cells has a main cell that controls the movement of the entire colony. If several colonies of identical cells meet and combine, then the main cell is selected according to the priority, which is evaluated by the state of the cells of their neighborhoods. Colonies with different active cells can interact, destroying each other. The methods of interaction of colonies with different active states are described. An example of colony formation for solving the problem of describing contour images is presented. The image is described by moving the colony through the cells belonging to the image contour and fixing the cell sectors of the colony, which include the cells of the contour at each time step.
TopBasic Theses And Definitions
In previous chapters, cellular automata were considered in which states changed with the help of active cells. ACA behaviors are described in which each active cell functions independently of other active cells. However, AСA structures are possible in which homogeneous groups of active cells (colonies of active cells) function. Homogeneous groups of active cells are characterized by the fact that they perform basic logical operations in interaction with other active cells. These cells can be neighboring (cells of a given shape of the neighborhood) and can be cells of the neighborhood of neighboring cells.
Interacting active cells can perform the same logical function, but can perform LSF, which depends on the performed LSF of neighboring active cells. A group of active cells is cells that are not isolated from each other. Cells of a group can interact with each other through other active cells of the same group. Examples of such groups of cells on Figure 1 are presented.
Figure 1. Examples of groups of active cells
Figure 1 shows the groups of active cells that are highlighted in black. Each active cell of such a group can transmit active and informational signals to any other active cell of this group. These examples show that all active cells that make up the active groups have the same properties (have the same state). However, active groups are united not by basic informational states, but by states of activity. Examples of such groups on Figure 2 are presented.
Figure 2. Examples of groups of active cells with different informational states
In Figure 2, groups of different colors are formed from cells with different basic information states. Each group of active cells is highlighted in black. Thus, active groups are formed only by active cells.
However, in such groups (colonies) for the normal functioning of the groups, the active cells in them are divided into internal and extreme active cells. Edge active cells are called active cells, in which there are inactive cells in the vicinity, and internal active cells have only active cells in the neighborhood of the colony to which they belong.