Fractal dimension of -state Rule 90 and Rule 150.
Structural analysis of fractals generated using one-dimensional additive cellular automata (ACA) is presented in this chapter. ACA is a dynamical system that evolves in discrete steps and generates two-dimensional self-similar structures. We investigate the structure of M-state ACA Rule 90 and Rule 150 using small-angle scattering (SAS; X-rays, neutrons, light) technique and multi-fractal analysis. We show how the scattering data from ACA can provide information about the overall size of the system, the number of total units, the number of rows, the size of the basic fractal units, the scaling factor, and the fractal dimension. In this case, when a particular row number reproduces a complete structure of the fractals, we can also obtain the fractal iteration number. We show that subsets of different states of M-state ACA can manifest both mono- and multi-fractal properties. We provide some useful relations between structural parameters of ACA that can be obtained experimentally from SAS.
- small-angle scattering
- cellular automata
Morphology of many systems at nano- and microscales appears to exhibit properties of scaling and self-similarity , meaning that they completely or partially preserve their structure on different scales of observation. Such structures are referred as fractals and are the objects of the fractal geometry . The main parameter of the fractal is the fractal (Hausdorff) dimension that is defined by the minimal number of spheres of the size that can penetrate each other and are needed to cover all points containing the object, as 
where is a constant. Usually, fractal objects have non-integer value of , whereas regular shapes have fractal dimension equal to the dimension of the space into which they are embedded. Thus, fractal dimensions of point, line, and regular surface are 0, 1, and 2, respectively.
One of the most efficient ways to investigate structures at nanoscale that exhibit fractal properties is a small-angle scattering (SAS) of X-ray (SAXS), neutron (SANS), and light (SALS) . SAS gives an information about the structure of the sample from the spatial variations of its electron density, providing the differential cross section as a function of transferred momentum. When neutrons are used, the scattering is given by the interaction of the incident beam with the atomic nuclei and with the magnetic moments . For X-rays, the scattering is mainly determined by their interaction with the electrons. Then, the obtained cross section represents the spatial density-density correlations in the investigated volume. Generally, data analysis and model development procedures can be interchanged between SANS and SAXS since the wavelength of X-rays is of the same order of magnitude as those of thermal neutrons . The SAS technique has the net advantage that is noninvasive, the investigated samples do not require additional preparation, and physical quantities are averaged over a macroscopic volume.
The main advantage of the SAS in the investigations of the fractals is the power-law behavior of the scattering exponent of the scattering intensity that reveals one of the main features of the fractal, the fractal dimension, as 
where , is the scattering angle, and is the wavelength of incident radiation. The exponent is the fractal dimension. For fractal structures, SAS can also differentiate between mass  and surface fractals [8, 9]. It was shown, recently, that SAS can be applied in structural investigations of various types of fractals , as fat fractals [11, 12] and chaos-game representation of fractals .
Many algorithms of the fractal construction exist, and most of them require either contraction or expansion mappings of the object onto itself, in order to obtain scaled and self-similar pattern [2, 14]. In the case of deterministic fractals, self-similarity is exact, meaning that the fractal is identical at all scales. Usually, natural systems do not have deterministic structure, and self-similarity they exhibit is stochastic. One can model them by introducing some randomness, assigning probabilities to generating rules. In addition, some systems can be multi-fractals, so they have more than one fractal dimension or scaling rule. The processes of generating all these fractals are performed separately, depending on which of particular type of fractal is needed to model and investigate. However, there is a mathematical model called cellular automata (CA) that can show a very diverse and complex behavior and manifests the properties of all different types of fractals [15, 16, 17].
Cellular automaton (CA) is a simple model of locally interacting dynamical systems that evolve in discrete steps. Single cellular automaton represents the site that has a finite number of states and changes each step, depending on the states of the neighboring sites. Although each site of the CA evolves according to the same rule, interactions between neighboring sites can lead to fairly complex patterns. CA can generate a large diversity of structures using simple initial conditions and their transition rules. CAs are often used as a model of physical systems with many degrees of freedom as biological systems, percolation clusters, diffusion-limited aggregates, and others. A particular type of CA, called additive cellular automata, can generate self-similar fractals [18, 19, 22].
Spatially homogeneous state, yielding behavior similar to limit points.
Sequence of simple stable or periodic structures, yielding behavior similar to limit cycles.
Chaotic aperiodic behavior, similar to “strange” attractors.
Complicated localized structures, where properties are undecidable.
In the approach used here, we view additive cellular automata (ACA) as discrete dynamical systems, in which the set of possible configurations ACA forms a fractal set [18, 19]. We provide characterization of structural properties of the fractals generated by additive cellular automata using small-angle scattering technique and multi-fractal analysis. We consider each site as a scattering unit. Scattering structure factors are calculated using efficient optimization of Debye formula [20, 21]. We show here how to extract structural information and fractal properties of ACA from SAS data, such as the fractal dimension, the overall size of the sample, the sizes of basic units, the scaling factor, and the number of generated steps.
2. Theoretical background
The following section presents the theoretical basics of used models and methods. We briefly explain the mathematical description of the cellular automata and the theoretical foundations of the small-angle scattering technique. We also discuss the transition matrix method as an algorithm for calculating the fractal dimension of ACA.
2.1. Cellular automata
In general, an arbitrary site of the -state CA, where is a prime and is a natural number, with the value at position and step is determined by a transition rule and depends on the state of the site itself and states of its neighbors at step ; thus
where is called a neighborhood index and is the dimensionality of the lattice. A particular type of CA called additive cellular automata is described by an additive (linear) rule of the type:
where are coefficients with . The initial state contains a single element that is considered as a non-zero site. For other initial conditions with multiple non-zero sites, due to linearity property, we shall obtain a superposition of structures generated from a single site .
There are two unique and distinct nontrivial one-dimensional ACA rules that can be obtained by using Eq. (4). In the first case, we have , , and all other terms equal to zero; the obtained relation will be given by
The structure generated by such rule for 2-state ACA when is shown in Figure 1 (left part). In the limit of the high number of generated steps, this structure will be nothing but the well-known Sierpinski triangle fractal. In the second case, we choose , , , and all other terms equal to zero. Therefore, the recurrence relation becomes
The structure generated by this rule for and is shown in Figure 1 (right part). Unlike the previous case, when the whole structure is self-similar, this structure has self-similar parts . Since the structure generated by ACA is self-similar, then one can determine its fractal dimension . It was shown that the growth rate dimension of ACA is equal to the fractal dimension [18, 19] and given by
where is the total number of non-zero state sites.
A more general case of fractal structure can be obtained by considering that the states and coefficients of each site can take arbitrary values. For arbitrary , we name these patterns “M-state Rule 90” and “M-state Rule 150” in order to underline that the recurrence relations are the same for each number of possible states. For and , Eqs. (5) and (6) give the well-known ACA Rule 90 and Rule 150, respectively.
2.2. Transition matrix method
One additional effective approach to compute the fractal dimension of ACA is the TM method  which analyzes only the transition rule. Let us suppose a set of one-dimensional blocks of length with all possible configurations of states. The length of the blocks should not be less than the difference in positions of the first and the last terms (neighbors) in Eq. (4), i.e., . Omitting the trivial block with all zero elements, there are of nontrivial blocks left. We can define a configuration of th block of length by inserting zeros, as . Then, applying an ACA transition function (see Eq. (4)) on this configuration, we obtain . The transition matrix shows how many blocks of a certain type are generated by the transition function from the configuration of uth block. The largest eigenvalue of the transition matrix gives the fractal dimension of the ACA by using the relation 
For Rule 90 the length of the block and the number of states , so the number of distinct nontrivial blocks , and they are [0 1], [1 0], and [1 1]. Now, inserting zeros between elements of the blocks and applying Eq. (5), we obtain
for the purpose of finding the transition matrix, we reduce upper configurations to three middle elements in the row :
Calculating the number of different blocks in each obtained reduced two-row configurations, the transition matrix can be derived. In the first configuration, block [0 1] appears twice and [1 0] once; in the second [1 0] once and [0 1] twice; and in the third both [1 0] and [0 1] once. In all configurations block [1 1] does not occur. The final form of the transition matrix for Rule 90 is
From Table 1 one can see that at and all the fractal dimensions are equal both for M-state Rule 90 and Rule 150. The same results hold for any -state ACA at constant and arbitrary . It is known that if a fractal consists of two or more different sub-fractals, then the fractal dimension of the fractal is equal to the biggest value among fractal dimensions of the sub-fractals .
|M = 2||M = 3||M = 4||M = 5||M = 6||M = 7||M = 8||M = 9|
The most natural way is to consider an -state ACA as a composition of sub-fractals formed by different values of the ACA sites. Since an M-state ACA has non-zero distinct states, 4-state ACA can be presented as a decomposition into three subsets of different states. Figure 2 shows the decomposition of 4-state Rule 90 and Rule 150 into the corresponding sets of state-1, state-2, and state-3. Thereafter, we refer to “set of state-i” simply as “state-i.” All three subsets have nonuniform distribution of points and, thus, may have properties of multi-fractals.
To characterize such nonuniform fractals, one needs to weight the well-known box-counting method according to the number of points inside a box. Then, one can define a generalized dimension spectrum as
where is the normalized measure of the ith box . We use here the barycentric fixed-mass (BFM) method to estimate the dimension spectra, both for ACA and their subsets . In order to perform such analysis, as for the SAS, we consider occupied sites of ACA as points. In the BFM method, the boxes grow by reaching their nearest neighbor that covers the same mass. At large scales when leveling effect occurs, an effective way to reduce it can be accomplished by a pivot point selection and usage of a non-overlapping criteria for reduction of the edge effects, for computational time and for precision improvements .
2.3. Small-angle scattering
In this chapter we provide a structural analysis of 2-state ACA and 4-state ACA. The latter ones presented in Figure 2 is considered as a 2-state system, regardless of the value of each occupied site, meaning that there are only two possible values of the site, “occupied” and “not occupied,” as shown in Figure 3. In the similar manner, all subsets of different states in 4-state ACA are also considered as 2-state system.
Generally, a typical small-angle scattering experiment performed using beams of neutrons, X-rays, or light. Experimental setup consists of a source of monochromatic beam of particles, an irradiated sample, and a detector. The incident beam with wave vector scatters the sample with the wave vector at the angle . The quantity measured is the differential cross section per unit volume as a function of the scattering vector .
Let us suppose an ensemble of objects with scattering length and the scattering length density SLD , where is the position of the scattering units. The total scattering amplitude is defined by the Fourier transform of by , where is the total irradiated volume. If we consider scattering from the system where particles of density are immersed in a uniform solid matrix of density , then the scattering contrast will be given as , and the intensity from the entire sample can be obtained according to
where is the concentration of objects, is the volume of each object, and is the normalized form factor with . The symbol stands for ensemble averaging over all orientations.
Real fractal samples usually have polydisperse distribution of the sizes of composing units. Thus, the corresponding scattering intensity from polydisperse fractals can be regarded as the sum of each individual form factor weighted with the corresponding volume and contrast . We choose here a continuous distribution of fractals with different sizes that gives the probability of finding a fractal of the size lying in the range . We consider here a lognormal distribution of fractal sizes, such as
where , is the mean length, is the relative variance, and . Since for a polydisperse fractal dispersion the volume of each fractal has a continuous variation with its size, we have
where is the normalized form factor. Since in our investigations we use cellular automata (CA) to generate the sites that are considered as scattering points, we shall compute the scattering intensity using the Debye formula :
where is the intensity scattered by each fractal unit and is the distance between units and . When the number of units exceeds few thousands, the computation of the term is very time-consuming and can be handled via a pair-distance histogram , with a bin-width commensurate with the experimental resolution . Thus, Eq. (13) becomes
where is the pair-distance histogram at pair distance . For determining fractal properties, we can neglect the form factor and consider . Thus, Eq. (14) gives the structure factor:
3. Results and discussion
3.1. 2-state ACA
Results of numerical calculations for mono- and polydisperse scattering structure factors of 2-state ACA Rule 90 and Rule 150 with at different steps are shown in Figure 4.
Usually, scattering structure factor spectra consist of three main regions. The first one, Guinier region, is characterized by constant intensity at low range and indicates the overall size of the irradiated sample by the rightmost part of the plateau as , where is the height of the ACA. The following region is called fractal and provides information about fractal properties of the sample from the power-law behavior of the scattering curve. The slope of the curve reveals the fractal dimension of the sample, and the rightmost part of the fractal region is related with the sizes of basic units, as , where is the side length of the basic unit. The presence of the most pronounced minima and their periodicity in this region can say about the fractal iteration number and the scaling factor. The third characteristic region is asymptote at high values of that gives the number of units composing the fractal sample. Note that for the purposes of our investigations we normalized the size of all ACA at different steps , in order to compare only their structural and fractal properties; thus, at low all scattering curves are approximately equal.
From monodisperse scattering data (Figure 4, left part), one can find that at steps and curves almost completely overlap each other in Guinier and fractal regions, except the asymptotic region due to different numbers of composing units. While behavior of the curve at is different, which arises from the fact that for -state () ACA the number of steps which generates a complete fractal structure is [18, 22], where is the fractal iteration number. In the case of 2-state ACA, the only possible prime and complete fractal structures appear when . At steps and , the structure is a complete fractal at two consecutive iterations as shown in Figure 5.
The fractal iteration number can be obtained from SAS data as the number of the most pronounced minima in fractal region. Fractal dimension can be better determined from polydisperse scattering structure factor and coincide with theoretical results from Table 1. In polydisperse case minima in fractal regions are smoothened due to different distributions of the sizes of basic units; thus, the iteration number and the scaling factor can no longer be determined.
The normalization we used in our calculations is performed in such a way that asymptotes of scattering curves tend to the value , where is the number of units composing the fractal; in the case of ACA, it is the number of occupied sites at step . For 2-state ACA Rule 90 and Rule 150, one can find analytical relations between the number of occupied sites and the fractal iteration number:
where is the fractal iteration number and is the jth element of the Fibonacci series.
3.2. 4-state ACA
Results of numerical calculations for mono- and polydisperse scattering structure factors of 4-state ACA Rule 90 and Rule 150 with and their subsets of different states are shown in Figure 6.
One can see that the scattering curves of both Rule 90 and Rule 150 in the Guinier region do not coincide. This is due to different distributions of sites in total 4-state and subsets of different states. To analyze this difference, we can compare a radius of gyration of these four structures. The radius of gyration of ACA can be obtained from Guinier region by performing a series expansion of the scattering intensity (Eq. (15)):
Thus, by representing the data from Figure 6 (left part) in a Guinier plot , the previous expansion gives a linear region of slope, from which the radius of gyration can be obtained through .
Numerical values for the slopes of scattering data for 4-state Rule 90 and Rule 150 for the corresponding state-i, , are shown in Figure 7. For both rules one can see that state-1 has the biggest radius of gyration. As shown in Figure 2, this can be explained by the fact that in state-1 a higher density of sites is found at the edges of ACA, for state-2 regions of higher density are spread inside, and for state-3 and total 4-state, there are little differences between regions of different densities.
Nonuniform distribution of sites of the subsets is the reason of their multi-fractal properties. To proof this fact, we provide a multi-fractal analysis using barycentric fixed-mass method according to Eq. (9) to the subset states of total 4-state ACA Rule 90 and Rule 150. Figure 8 shows the dimension spectra of the subsets, and the value is changing along range, meaning that they are multi-fractals. By definition of generalized dimensions, gives the box-counting dimension, which is obtained from SAS simulations.
SAS spectra from Figure 6 show that the fractal dimension of the subsets of different states does not coincide with the fractal dimension of total 4-state. In fact, that occurs due to inappropriate choice of the decomposition, presented in Figure 2. From Table 1 we know that 2-state and 4-state ACA have the same value of fractal dimension; thus, it is expected to have one structure being the part of other. In fact, such pattern appears when state-1 and state-3 of total 4-state ACA are superimposed and form 2-state ACA, as shown in Figure 9. 2-State ACA has a bigger value of the fractal dimension than state-2; thus, it equals to the fractal dimension of the total 4-state.
3.3. ACA with different coefficients in transition rule
In previous sections we dealt only with ACA transition rules where all coefficients . More general cases of ACA may be obtained varying these coefficients. For an M-state ACA, there are different distinct combinations of exist, where is the number of terms in transition rule (neighborhood). Most of these combinations generate structures that are trivial and/or are mirror reflection of each other. However, some of them give quite intricate patterns with the same overall structure as if but with different arrangements of the subsets, presented in Figure 10.
In the case of 4-state ACA, we set and calculated corresponding SAS and multi-fractal spectra. Unlike the arrangement presented in Figure 2, in this case subsets state-1 and state-3 have more uniform and similar arrangement of the sites. From SAS data (Figure 11, left part), one can find that scattering curves of state-1 and state-3 almost completely overlap. The difference appears only in transition between fractal and asymptotic regions. The dimension spectrum (Figure 11, right part) shows that there is a little difference in the fractal dimensions of state-1 and state-2, and due to uniform distribution of the sites, the spectra are almost constant along range, meaning that state-1 and state-2 are mono-fractals. The arrangement of the sites of state-2 is the same as in Figure 2, meaning that superposition of the state-1 and state-2 gives the 2-state ACA. It is confirmed by the slope of the scattering curve in fractal region.
For large values of , Eq. (7) can be approximated by
Thus, using the value of the fractal dimension obtained from SAS data (Figure 4) and the asymptotic values, we can find a good approximation of the number of rows generated by ACA. Using Eq. (18) one can find connection between the number of rows generated by ACA, the fractal iteration number, and the scaling factor of the corresponding fractal structure:
For self-similar fractals, the total number of scattering units at nth iteration is given by 
From Eqs. (8) and (7), one can find that . The last expression shows that Eq. (20) can be extended for fractals generated by -state cellular automata. Thus, the scaling factor of such fractals is the inverse of this prime :
In this chapter we investigated the structural properties of the fractals generated by additive cellular automata. The small-angle scattering technique and multi-fractal analysis are considered to characterize the structure of the nano- and microscale models of ACA fractals. We present the theoretical foundations of the methods of ACA characterization, such as the transition matrix method, the small-angle scattering, and the multi-fractal analysis. We show how they can be implemented in the structural investigations of the fractals generated by ACA. The analysis is performed using an efficient and optimized version of Pantos and barycentric fixed-mass method for calculating the small-angle scattering and the dimension spectra, respectively.
The mathematical description of the general algorithm for the construction of the fractals using additive cellular automata (ACA) is explained. We show how to obtain the well-known Rule 90 and Rule 150 that generate self-similar fractals using deterministic algorithm. We explain how to construct generalization of these rules for arbitrary state. The comparison of the structural characteristics of the 2-state and 4-state ACA is presented. We showed cases when subsets of different states of 4-state ACA are mono- and multi-fractals.
For each introduced M-state ACA, we calculate the scattering and the multi-fractal spectrum, and we explain how to extract the main fractal and structural properties such as the fractal dimension, the number of steps generated by ACA, the fractal iteration number, the scaling factor, the overall size, the sizes of the basic units, and the number of units in the system.
The obtained results can be applied for structural investigations of the nano-/microscale systems, modeled by cellular automata.