Cellular Automata

This work develops a two-dimensional cellular automaton (CA) which solves single source shortest path problem for a grid graph. Grid graphs are represented as configurations of the CA, and maximum degree of a node is considered as four. Nodes and edges of the graph are modeled by cells with different state sets. The cells for nodes use a rule to update their states whereas the rest cells including the cells for edges use another rule. That is, two rules are used by the automaton which makes it a non-uniform CA. The worst case time complexity for the scheme is \(\mathcal {O}(n)\) where n is the total number of nodes in the connected graph.

The authenticated encryption (AE) scheme ACORN v3, a CAESAR competition finalist, has been shown to be particularly vulnerable against Differential Fault Attack (DFA), even more so than its previous version ACORN v2. In this paper, we analyse how fault attacks can be prevented in ACORN v3 by using cellular automata (CA). The good pseudorandom properties of CA are exploited and renders the ACORN v3 infeasible to perform fault attacks on. The Programmable Cellular Automata (PCA) 90-150 is effectively deployed to make ACORN cipher robust against DFA.

ASCON is a sponge function based authenticated encryption (AE) scheme chosen in CAESAR competition for lightweight applications. Its suitability for high performance applications make it desirable in environments like Internet of Things (IoT) where large number of very constrained devices communicate with high-end servers. The drawback is that fault analyses like Statistical Ineffective fault attack (SIFA) and Sub-Set Fault Analysis (SSFA) are possible. In this paper, we modify ASCON 128a exploiting the pseudo-random properties of Cellular Automata (CA) to prevent these attacks.

In this paper, we show that the theory of information offers some tools to detect changes in the interaction topology of a dynamical system defined on a graph. As an illustrative example, the system we consider is a probabilistic voter model defined on a scale-free network. We show that, using time-delayed mutual-information, the interaction topology of an unknown graph can be reconstructed to some level. We apply this approach on a sliding time window to detect possible changes in the interaction topology over time.

In this paper, we define observability for cellular automaton. Then we extend the Kalman observability criterion to affine cellular automaton with a time-varying output operator. Finally, this observability characterisation is applied to the observation of affine cellular automaton through mobile sensors.

Semi-bent Boolean functions are interesting from a cryptographic standpoint, since they possess several desirable properties such as having a low and flat Walsh spectrum, which is useful to resist linear cryptanalysis. In this paper, we consider the search of semi-bent functions through a construction based on cellular automata (CA). In particular, the construction defines a Boolean function by computing the XOR of all output cells in the CA. Since the resulting Boolean functions have the same algebraic degree of the CA local rule, we devise a combinatorial algorithm to enumerate all quadratic Boolean functions. We then apply this algorithm to exhaustively explore the space of quadratic rules of up to 6 variables, selecting only those for which our CA-based construction always yields semi-bent functions of up to 20 variables. Finally, we filter the obtained rules with respect to their balancedness, and remark that the semi-bent functions generated through our construction by the remaining rules have a constant number of linear structures.

In this paper, we present a new Cellular Automata (CA) based authenticated encryption scheme, named as EnCash. Both for encryption and authentication, it proposes a CA-based cost-effective design structure. Encryption follows the substitution-permutation-network (SPN) where, at the substitution layer, randomized mapping is introduced and cellular automata, both linear and non-linear are used for the permutation. We perform the cryptanalysis of the substitution table and also the Strict Avalanche Criterion test for the encryption function. The results assure the security of EnCash.

In this paper we explore the possibility of using high-order cellular automata to perform edge detection. Experiments are conducted to show how to find optimal values for the model. Using these optimal values, the model is compared to common methods for edge detection. The obtained results are encouraging since they are very close to the best performing commonly used methods.

Cellular Automata (CA) have recently evolved as a good cryptographic primitive. CA have been used as pseudorandom number generators in stream ciphers, block ciphers and hash functions. The eSTREAM cipher Trivium, though secure in its complete rounds, was cryptanalyzed in its reduced rounds. Trivium has a simple internal structure and a very long key setup phase that consists of 1152 rounds. This paper emphasizes the advantage of using CA of higher radii in Trivium. Here, we have proposed a 5-neighbourhood CA to be used in Trivium which helps the cipher to attain better cryptographic properties at a faster rate. The diffusion and randomness of the cipher also increases with the use of higher radii, but at the cost of increased computational complexity. The new cipher is named Pentavium.

This paper deals with energy management in a microgrid through peer-to-peer (P2P) energy exchange method. The P2P process is executed on the basis of cellular automaton (CA) approach and implemented by smart contracts blockchain over a time horizon, enabling consensus to be recorded between consumers in a secure and fully automated transaction. The CA proposed model identifies the end-user state in a set of five possible states and supports the convergence of supply and demand decisions, thus ensuring the decentralization of energy distribution.

In this work, we consider the control problem for a phenomenon modeled by Cellular Automata (CA) through actuators and attributes. To achieve this, we introduce what we called attributes and the adaptation of the definition of actuators to the CA in connection with attributes. The proposed control is then given through the attributes and not directly on the state of the system, as was the case in previous works like for the additive (elementary) CA. To illustrate our approach, we consider the fire forest control problem in the 3D cellular automata.

We consider a multi-agent system composed of the second-order nonuniform Cellular Automata (CA)–based agents, where a spatial Prisoner’s Dilemma (PD) game describes the interaction between agents. Each agent has some strategy that can change in time and acts in such a way to maximize its income. We intend to study conditions of emergence of collective behavior in such systems measured by the average total payoff of a team of agents in the game or by an equivalent measure – the total number of cooperating players. While the emergence of collective behavior depends on many parameters, we introduce to the game an income sharing mechanism, giving a possibility to share incomes locally by agents wishing to do it. We present results showing that under some conditions, the introduced mechanism can significantly increase the level of collective behavior.

This work proposed the application of an evolutionary technique to optimise the parameters of a coordination model for swarms of robots. A genetic algorithm with standard characteristics was applied in order to find suitable parameters for the IACA-DI model (Inverted Ant Cellular Automata with Discrete pheromone diffusion and Inertial motion), which, in turn, was proposed in previous works. The IACA-DI is a model to coordinate swarms of robots based on the combination of two bio-inspired techniques: cellular automata and inverted ant system. The main purpose of the model is to carry out surveillance, exploration and foraging tasks. Experiments were performed in different configurations of environments and with different movement strategies to validate this application. Results have shown significant improvements in the model performance compared with previous empirical calibrations, granting a better understanding of the IACA-DI parameters, and allowing significant improvements to be investigated in future works.

The objective is to find Cellular Automata (CA) which are able to cover the 2D space by a minimum number of so-called “Sensor Tiles”. A sensor tile consists of a central sensor pixel and 12 surrounding sensing pixels. Two probabilistic CA rules were designed that can perform this task. The first rule evolves very fast stable sub–optimal coverings, starting from a random configuration. The second rule finds several optimal or near-optimal coverings but needs much more time for their evolution.

We propose a novel architecture for the implementation of Cellular Automata (CA). The novel architecture is based on graphene nanoribbons with magnetic contacts, which are used as building blocks. In this CA implementation, information processing is obtained through top-gates, back-gates and the angles and magnitudes of the polarizations of the magnetic contacts. We use tight-binding Hamiltonians and non-equilibrium Green’s functions to model and simulate the operation of the building blocks of the proposed CA implementation. Interconnections are local and CA cell states can be represented using top-gate and back-gate potentials, and the angles and magnitudes of the contact polarizations. We also describe the CA evolution rules. Our results showed that this CA implementation is capable of both digital and analog information processing. Furthermore, it can be effectively used for neuromorphic and in-memory computing.

This study copes with the problem of finding the optimal route that a pedestrian could follow in order to move into an urban environment taking into consideration various criteria and possible points of interest, either objective nor subjective. For this purpose, an appropriate computational model has been designed, based on Cellular Automata (CA) that responds taking into consideration the walkability of the urban area under study. The latter feature encompasses a variety of qualitative parameters in regard to the pedestrian mobility. Thus, this model aims at enforcing more sustainable transport approaches, such as walking. In order to evaluate the functionality of the proposed model, an initial application is carried out in the city of Xanthi, North-East Greece, in order to verify the plausibility and completeness of the proposed routes in different scenarios.

A discretization of time in computer simulation of pedestrian movement is considered. Time step is very influencing on computational performance. But not only quick calculations is a criterion. The other one is a confidence to a simulation result. From both aspects, the discrete-continuous model SigmaEva is considered in the paper. It is shown that low and high time steps are not reasonable.

DESERTICAS is a cellular automata software specially designed for modelling and simulating the evolution of land degradation over time and space. It is based on coupling a continuous cellular automaton with the MEDALUS method that has been applied to assess the desertification phenomena on Mediterranean areas. Additionally, the built model will incorporate land use practices, exploitability and ownership factors. From an arbitrary initial configuration, DESERTICAS can predict the space-time evolution of land degradation towards the most advanced stage. The fully parameterized software will be applied to real data that are being processed for model validation.

We perform a numerical study of thermal diffusion effects on double-diffusive mixed convection in a lid-driven square cavity, differentially heated and salted. The fluid flow is solved by a multiple relaxation time (MRT) lattice Boltzmann method (LBM), whereas the temperature and concentration fields are computed by finite difference method (FDM). To assess numerical accuracy, the model (MRT-LBM coupled with FDM) are verified and validated using data from the literature. Besides reasonable agreement, satisfactory computational efficiency is also found. Thereafter, the model is applied for the thermal diffusion effect on a double-diffusive mixed convection in a cavity with moving lid. Results are obtained depending on various dimensionless parameters. It is found that upon increasing the Soret number, heat transfer is slightly enhanced whereas the thickness of the concentration boundary layer increases, thereby decreasing the mass transfer rate.

The new approach for logical operations implementations in cellular automata is proposed. For the implementation of logical gates the propagation of the gliders of cellular automata in bounded domain is considered. Special laws for collisions of gliders with domain walls and internal obstacles in domain are displayed. Logical gate XOR construction, examples of computations and some discussion are described. Comparison with usual approach is given.

Carbon dioxide concentration in closed spaces is an indication of air quality and a means of measuring the number of occupants for controlling energy consumption. However, the dispersion of the gas and the accuracy of the concentration measurements as logged by carbon dioxide sensors are highly sensitive to the configuration of the closed space. Conducting case by case studies for each closed space is neither practical nor cost-effective. We hereby propose a formal model using cellular discrete-event system specifications for studying carbon dioxide dispersion indoors and for analyzing the effect of different configurations on the sensors measurements of the concentration. We present a case study of the model and compare the simulation results to ground truth data collected from two physical systems of two computer laboratories. The results demonstrate that the proposed model can be used to study carbon dioxide dispersion and the change of sensors’ readings in closed spaces based on the configurations of the space.

Improved Susceptible-Infected-Recovered (SIR) models have been used to study the COVID-19 pandemic. Although they can predict epidemiology curves, spatial models cannot be easily built, and cannot model individual interactions. In this research, we show a definition of SIR-based models using the Cell-DEVS formalism (a combination of Cellular Automata and DEVS), showing how to deal with these issues. We validate the equivalence of a simple Cell-DEVS SIR model, and we present a SIIRS model, whose parameters are configured to imitate the spread of SARS-CoV-2 in South Korea. Such models may assist in the decision-making process for defining health policies, such as social distancing, to prevent an uncontrolled expansion of the virus.

The numerical studies of disease spreading processes are almost one-century old. The mainstream of these analyses is based on the ordinary differential equations which enable to estimate, especially, the epidemic curves for some assumed values of parameters describing the aggregate probabilities of passing through different phases if illness. In our paper, we present some results which can be obtained for the more individualized model, based on the analysis of direct interactions between the members of the community. We use the concepts of the SEIR model but we apply the different mechanisms to study the process of transfer of illness based on the representation of the community as the scale-free network. We can obtain the typical epidemic curves, study their spread, and also analyze the epidemic process in the internal groups of the community.

A model to simulate the spreading of a disease on a network is proposed. The SIR model, a social distancing factor and network circulation restrictions are considered. We perform some experiments that give us an idea of how a disease spreads on different network topologies and social distancing factors.

The propagation of infectious diseases through social interactions can be mitigated when health measures aim to reduce or remove the results of these interactions. This is the scenario of ongoing COVID-19 pandemic adopted quarantine policies, from social distancing to lockdown, and of immunization programs. When a sufficient number of interactions is suppressed, the spread of an infectious disease is ended achieving herd immunity, defined as the indirect protection given by immune individuals to susceptible individuals. Here we describe the preliminaries of a stochastic cellular automaton based framework designed to emulate the spread of SARS-CoV-2 in a population of static individuals interacting only via Moore neighbourhood of radius one, with a view to analyze the impact of initially immune individuals on the dynamics of COVID-19. This impact was measured comparing a progression of initial immunity ratio from 0 to 90% of the population with the number of susceptible individuals not contaminated, the peak value of active cases, the total number of deaths and the emulated pandemic duration in days. A herd immunity threshold of 60% was obtained from this procedure, which is in tune with the estimates of the currently available medical literature. Nevertheless, more accurate results demand more research efforts including better analysing the model probabilities of propagation and duration.