1,721,177 research outputs found
Search space reduction of asynchrony immune cellular automata
Full text linkWe continue the study of asynchrony immunity in cellular automata (CA), which can be considered as a generalization of correlation immunity in the case of vectorial Boolean functions. The property could have applications as a countermeasure for side-channel attacks in CA-based cryptographic primitives, such as S-boxes and pseudorandom number generators. We first give some theoretical results on the properties that a CA rule must satisfy in order to meet asynchrony immunity, like central permutivity. Next, we perform an exhaustive search of all asynchrony immune CA rules of neighborhood size up to 5, leveraging on the discovered theoretical properties to greatly reduce the size of the search space.Cyber Securit
The firing squad synchronization problem on CA with multiple updating cycles
No full textClassical cellular automata have a single, global clock that allows all the cells to update their states simultaneously at every clock cycle. Here, we overturn this assumption and we study cellular automata where different cells can use different clocks cycles and, as a consequence, they update at different times. We show how it is possible to solve the firing squad synchronization problem in this new setting and propose a synchronization algorithm operating in time linear with respect to the automata size
Building Correlation Immune Functions from Sets of Mutually Orthogonal Cellular Automata
Full text linkCorrelation immune Boolean functions play an important role in the implementation of efficient masking countermeasures for side-channel attacks in cryptography. In this paper, we investigate a method to construct correlation immune functions through families of mutually orthogonal cellular automata (MOCA). First, we show that the orthogonal array (OA) associated to a family of MOCA can be expanded to a binary OA of strength at least 2. To prove this result, we exploit the characterization of MOCA in terms of orthogonal labelings on de Bruijn graphs. Then, we use the resulting binary OA to define the support of a second-order correlation immune function. Next, we perform some computational experiments to construct all such functions up to n= 12 variables, and observe that their correlation immunity order is actually greater, always at least 3. We conclude by discussing how these results open up interesting perspectives for future research, with respect to the search of new correlation-immune functions and binary orthogonal arrays.</p
Some formal properties of asynchronous cellular automata
No full textWe study the dynamical behaviour of asynchronous cellular automata by considering some formal properties of classical cellular automata and adapting them to the asynchronous case
A new genetic programming framework based on reaction systems
No full textThis paper presents a new genetic programming framework called Evolutionary Reaction Systems. It is based on a recently defined computational formalism, inspired by chemical reactions, called Reaction Systems, and it has several properties that distinguish it from other existing genetic programming frameworks, making it interesting and worthy of investigation. For instance, it allows us to express complex constructs in a simple and intuitive way, and it lightens the final user from the task of defining the set of primitive functions used to build up the evolved programs. Given that Evolutionary Reaction Systems is new and it has small similarities with other existing genetic programming frameworks, a first phase of this work is dedicated to a study of some important parameters and their influence on the algorithm’s performance. Successively, we use the best parameter setting found to compare Evolutionary Reaction Systems with other well established machine learning methods, including standard tree-based genetic programming. The presented results show that Evolutionary Reaction Systems are competitive with, and in some cases even better than, the other studied methods on a wide set of benchmarks
Sustainable multi-objective optimization problem for environmental impact and electricity production analysis of dams
No full textIn this paper, we develop a multi-objective optimization framework that employs a variant of the Multi-Objective Particle Swarm Optimizer (MOPSO) to balance the competing objectives represented by the total electricity generation and the reduction of carbon emissions, due to the construction of dams. This challenge highlights two conflicting aspects in the context of climate change and sustainability: on the one hand, hydropower represents a renewable energy source; on the other hand, the construction of dams leads to large greenhouse gas emissions. We analyse a dataset of 509 dams in the Amazon basin, categorized by geographical and technical features, to assess the impact of site selection. We further inspect the key features of dams that compose the best configurations to maximize energy output while minimizing emissions. The results show that, in such configurations, the most efficient dams are located in the upland zones of Peru, while inefficient dams are located on Brazilian territory, whose geographic conformation allows the construction of only downland dams that have a greater environmental impact due to a larger reservoir to satisfy a determined energy need. Finally, it seems that some existing dams are completely inefficient from the optimization viewpoint
Fixed points and attractors of additive reaction systems
Full text linkReaction systems are discrete dynamical systems that simulate biological processes within living cells through finite sets of
reactants, inhibitors, and products. In this paper, we study the computational complexity of deciding on the existence of
fixed points and attractors in the restricted class of additive reaction systems, in which each reaction involves at most one
reactant and no inhibitors. We prove that all the considered problems, that are known to be hard for other classes of
reaction systems, are polynomially solvable in additive systems. To arrive at these results, we provide several non-trivial
reductions to problems on a polynomially computable graph representation of reaction systems that might prove useful for
addressing other related problems in the future
A General Purpose Representation and Adaptive EA for Evolving Graphs
Full text linkGraphs are a way to describe complex entities and their relations that apply to many practically relevant domains. However, domains often differ not only in the properties of nodes and edges, but also in the constraints imposed to the overall structure. This makes hard to define a general representation and genetic operators for graphs that permit the evolutionary optimization over many domains. In this paper, we tackle this challenge. We first propose a representation template that can be customized by users for specific domains: the constraints and the genetic operators are given in Prolog, a declarative programming language for operating with logic. Then, we define an adaptive evolutionary algorithm that can work with a large number of genetic operators by modifying their usage probability during the evolution: in this way, we relieve the user from the burden of selecting in advance only operators that are “good enough”. We experimentally evaluate our proposal on two radically different domains to demonstrate its applicability and effectiveness: symbolic regression with trees and text extraction with finite-state automata. The results are promising: our approach does not trade effectiveness for versatility and is not worse than other domain-tailored approaches
Computing issues of asynchronous CA
No full textThis work studies some aspects of the computational power of fully asynchronous cellular automata (ACA). We deal with some notions of simulation between ACA and Turing Machines. In particular, we characterize the updating sequences specifying which are “universal”, i.e., allowing a (specific family of) ACA to simulate any Turing machine on any input. We also consider the computational cost of such simulations. Finally, we deal with ACA equipped with peculiar updating sequences, namely those generated by random walks
The Influence of Local Search on Genetic Algorithms with Balanced Representations
No full textCertain combinatorial optimization problems with binary representation require the candidate solutions to satisfy a balancedness constraint (e.g., being composed of the same number of 0s and 1s). A common strategy when using Genetic Algorithms (GA) to solve these problems is to use crossoveer and mutation operators that preserve balancedness in the offspring. However, it has been observed that the reduction of the search space size granted by such tailored variation operators does not usually translate to a substantial improvement of the GA performance. There is still no clear explanation of this phenomenon, although it is suspected that a balanced representation might yield a more irregular fitness landscape, where it could be more difficult for GA to converge to a global optimum. In this paper, we investigate this issue by adding a local search step to a GA with balanced operators, and use it to evolve highly nonlinear balanced Boolean functions. We organize our experiments around two research questions, namely if local search (1) improves the convergence speed of GA, and (2) decreases the population diversity. Surprisingly, while our results answer affirmatively the first question, they also show that adding local search actually increases the diversity among the individuals. We link these findings to some recent results on fitness landscape analysis for problems on Boolean functions
- …
