Fractal dimension

## Abstract

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.

### Keywords

- small-angle scattering
- multi-fractals
- fractals
- cellular automata

## 1. Introduction

Morphology of many systems at nano- and microscales appears to exhibit properties of scaling and self-similarity [1], 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 [2]. The main parameter of the fractal is the fractal (Hausdorff) dimension

where

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) [4]. 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 [5]. 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 [6]. 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

where

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].

In the case of CA consisting of a line of sites (one-dimensional CA), it is known that they fall into four distinct universality classes [15, 16]:

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

where

where

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

The structure generated by such rule for 2-state ACA when

The structure generated by this rule for

where

A more general case of fractal structure can be obtained by considering that the states

### 2.2. Transition matrix method

One additional effective approach to compute the fractal dimension of ACA is the TM method [18] which analyzes only the transition rule. Let us suppose a set of one-dimensional blocks of length * nontrivial*blocks left. We can define a configuration of

*th block. The largest eigenvalue*u

For Rule 90 the length of the block

for the purpose of finding the transition matrix, we reduce upper configurations to three middle elements in the row [18]:

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

M = 2 | M = 3 | M = 4 | M = 5 | M = 6 | M = 7 | M = 8 | M = 9 | |
---|---|---|---|---|---|---|---|---|

Rule 90 | 1.58496 | 1.63093 | 1.58496 | 1.68261 | 1.61315 | 1.71241 | 1.58496 | 1.63093 |

Rule 150 | 1.69424 | 1.63093 | 1.69424 | 1.82948 | 1.70622 | 1.84558 | 1.69424 | 1.63093 |

The most natural way is to consider an * i*” simply as “state-

*.” All three subsets have nonuniform distribution of points and, thus, may have properties of multi-fractals.*i

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 * i*th box

### 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 “

*,” 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.*not occupied

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

Let us suppose an ensemble of objects with scattering length

where

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

where

where

where

where

## 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

Usually, scattering structure factor spectra consist of three main regions. The first one, Guinier region, is characterized by constant intensity at low

From monodisperse scattering data (Figure 4, left part), one can find that at steps

The fractal iteration number

The normalization we used in our calculations is performed in such a way that asymptotes of scattering curves tend to the value

where * j*th 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

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

Thus, by representing the data from Figure 6 (left part) in a Guinier plot

Numerical values for the slopes of scattering data for 4-state Rule 90 and Rule 150 for the corresponding state-* i*,

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

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 * M*-state ACA, there are

In the case of 4-state ACA, we set

For large values of

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

For self-similar fractals, the total number of scattering units at * n*th iteration is given by [26]

From Eqs. (8) and (7), one can find that

## 4. Conclusions

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

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.