
Adamatzky, A., Goles, E., Martinez, G. J., Tsompanas, M. A., Tegelaar, M., & Wosten, H. A. B. (2020). Fungal Automata. Complex Syst., 29(4), 759–778.
Abstract: We study a cellular automaton (CA) model of information dynamics on a single hypha of a fungal mycelium. Such a filament is divided in compartments (here also called cells) by septa. These septa are invaginations of the cell wall and their pores allow for the flow of cytoplasm between compartments and hyphae. The septal pores of the fungal phylum of the Ascomycota can be closed by organelles called Woronin bodies. Septal closure is increased when the septa become older and when exposed to stress conditions. Thus, Woronin bodies act as informational flow valves. The onedimensional fungal automaton is a binarystate ternary neighborhood CA, where every compartment follows one of the elementary cellular automaton (ECA) rules if its pores are open and either remains in state 0 (first species of fungal automata) or its previous state (second species of fungal automata) if its pores are closed. The Woronin bodies closing the pores are also governed by ECA rules. We analyze a structure of the composition space of cellstate transition and porestate transition rules and the complexity of fungal automata with just a few Woronin bodies, and exemplify several important local events in the automaton dynamics.



Aledo, J. A., Goles, E., MontalvaMedel, M., Montealegre, P., & Valverde, J. C. (2023). Symmetrizable Boolean networks. Inf. Sci., 626, 787–804.
Abstract: In this work, we provide a procedure that allows us to transform certain kinds of deterministic Boolean networks on minterm or maxterm functions into symmetric ones, so inferring that such symmetrizable networks can present only periodic points of periods 1 or 2. In particular, we deal with generalized parallel (or synchronous) dynamical systems (GPDS) over undirected graphs, i. e., discrete parallel dynamical systems over undirected graphs where some of the selfloops may not appear. We also study the class of antisymmetric GPDS (which are nonsymmetrizable), proving that their periodic orbits have period 4. In addition, we introduce a class of nonsymmetrizable systems which admit periodic orbits with arbitrary large periods.



Aracena, J., Goles, E., Moreira, A., & Salinas, L. (2009). On the robustness of update schedules in Boolean networks. Biosystems, 97(1), 1–8.
Abstract: Deterministic Boolean networks have been used as models of gene regulation and other biological networks. One key element in these models is the update schedule, which indicates the order in which states are to be updated. We study the robustness of the dynamical behavior of a Boolean network with respect to different update schedules (synchronous, blocksequential, sequential), which can provide modelers with a better understanding of the consequences of changes in this aspect of the model. For a given Boolean network, we define equivalence classes of update schedules with the same dynamical behavior, introducing a labeled graph which helps to understand the dependence of the dynamics with respect to the update, and to identify interactions whose timing may be crucial for the presence of a particular attractor of the system. Several other results on the robustness of update schedules and of dynamical cycles with respect to update schedules are presented. Finally, we prove that our equivalence classes generalize those found in sequential dynamical systems. (C) 2009 Elsevier Ireland Ltd. All rights reserved.



Bitar, N., Goles, E., & Montealegre, P. (2022). COMPUTATIONAL COMPLEXITY OF BIASED DIFFUSIONLIMITED AGGREGATION. SIAM Discret. Math., 36(1), 823–866.
Abstract: DiffusionLimited Aggregation (DLA) is a clustergrowth model that consists in a set of particles that are sequentially aggregated over a twodimensional grid. In this paper, we introduce a biased version of the DLA model, in which particles are limited to move in a subset of possible directions. We denote by kDLA the model where the particles move only in k possible directions. We study the biased DLA model from the perspective of Computational Complexity, defining two decision problems The first problem is Prediction, whose input is a site of the grid c and a sequence S of walks, representing the trajectories of a set of particles. The question is whether a particle stops at site c when sequence S is realized. The second problem is Realization, where the input is a set of positions of the grid, P. The question is whether there exists a sequence S that realizes P, i.e. all particles of S exactly occupy the positions in P. Our aim is to classify the Prediciton and Realization problems for the different versions of DLA. We first show that Prediction is PComplete for 2DLA (thus for 3DLA). Later, we show that Prediction can be solved much more efficiently for 1DLA. In fact, we show that in that case the problem is NLComplete. With respect to Realization, we show that restricted to 2DLA the problem is in P, while in the 1DLA case, the problem is in L.



Bottcher, L., Montealegre, P., Goles, E., & Gersbach, H. (2020). Competing activistsPolitical polarization. Physica A, 545, 13 pp.
Abstract: Recent empirical findings suggest that societies have become more polarized in various countries. That is, the median voter of today represents a smaller fraction of society compared to two decades ago and yet, the mechanisms underlying this phenomenon are not fully understood. Since interactions between influential actors ("activists'') and voters play a major role in opinion formation, e.g. through social media, we develop a macroscopic opinion model in which competing activists spread their political ideas in specific groups of society. These ideas spread further to other groups in declining strength. While unilateral spreading shifts the opinion distribution, competition of activists leads to additional phenomena: Small heterogeneities among competing activists cause them to target different groups in society, which amplifies polarization. For moderate heterogeneities, we obtain target cycles and further amplification of polarization. In such cycles, the stronger activist differentiates himself from the weaker one, while the latter aims to imitate the stronger activist. (C) 2019 Elsevier B.V. All rights reserved.



Bottcher, L., WoolleyMeza, O., Goles, E., Helbing, D., & Herrmann, H. J. (2016). Connectivity disruption sparks explosive epidemic spreading. Phys. Rev. E, 93(4), 8 pp.
Abstract: We investigate the spread of an infection or other malfunction of cascading nature when a system component can recover only if it remains reachable from a functioning central component. We consider the susceptibleinfectedsusceptible model, typical of mathematical epidemiology, on a network. Infection spreads from infected to healthy nodes, with the addition that infected nodes can only recover when they remain connected to a predefined central node, through a path that contains only healthy nodes. In this system, clusters of infected nodes will absorb their noninfected interior because no path exists between the central node and encapsulated nodes. This gives rise to the simultaneous infection of multiple nodes. Interestingly, the system converges to only one of two stationary states: either the whole population is healthy or it becomes completely infected. This simultaneous cluster infection can give rise to discontinuous jumps of different sizes in the number of failed nodes. Larger jumps emerge at lower infection rates. The network topology has an important effect on the nature of the transition: we observed hysteresis for networks with dominating local interactions. Our model shows how local spread can abruptly turn uncontrollable when it disrupts connectivity at a larger spatial scale.



Canals, C., Goles, E., Mascareno, A., Rica, S., & Ruz, G. A. (2018). School Choice in a Market Environment: Individual versus Social Expectations. Complexity, 3793095, 11 pp.
Abstract: School choice is a key factor connecting personal preferences (beliefs, desires, and needs) and school offer in education markets. While it is assumed that preferences are highly individualistic forms of expectations by means of which parents select schools satisfying their internal moral standards, this paper argues that a better matching between parental preferences and school offer is achieved when individuals take into account their relevant network vicinity, thereby constructing social expectations regarding school choice. We develop two related models (individual expectations and social expectations) and prove that they are driven by a Lyapunov function, obtaining that both models converge to fixed points. Also, we assess their performance by conducting computational simulations. While the individual expectations model shows a probabilistic transition and a critical threshold below which preferences concentrate in a few schools and a significant amount of students is left unattended by the school offer, the social expectations model presents a smooth dynamics in which most of the schools have students all the time and no students are left out. We discuss our results considering key topics of the empirical research on school choice in educational market environments and conclude that social expectations contribute to improve information and lead to a better matching between school offer and parental preferences.



ConchaVega, P., Goles, E., Montealegre, P., & RiosWilson, M. (2022). On the Complexity of Stable and Biased Majority. Mathematics, 10(18), 3408.
Abstract: A majority automata is a twostate cellular automata, where each cell updates its state according to the most represented state in its neighborhood. A question that naturally arises in the study of these dynamical systems asks whether there exists an efficient algorithm that can be implemented in order to compute the state configuration reached by the system at a given timestep. This problem is called the prediction problem. In this work, we study the prediction problem for a more general setting in which the local functions can be different according to their behavior in tie cases. We define two types of local rules: the stable majority and biased majority. The first one remains invariant in tie cases, and the second one takes the value 1. We call this class the heterogeneous majority cellular automata (HMCA). For this latter class, we show that in one dimension, the prediction problem for HMCA is in NL as a consequence of the dynamics exhibiting a type of bounded change property, while in two or more dimensions, the problem is PComplete as a consequence of the capability of the system of simulating Boolean circuits.



ConchaVega, P., Goles, E., Montealegre, P., RiosWilson, M., & Santivanez, J. (2022). Introducing the activity parameter for elementary cellular automata. Int. J. Mod Phys. C, 33(09), 2250121.
Abstract: Given an elementary cellular automaton (ECA) with local transition rule R, two different types of local transitions are identified: the ones in which a cell remains in its current state, called inactive transitions, and the ones in which the cell changes its current state, which are called active transitions. The number of active transitions of a rule is called its activity value. Based on latter identification, a rule R1 is called a subrule of R2 if the set of active transitions of R1 is a subset of the active transitions of R2.
In this paper, the notion of subrule for elementary cellular automata is introduced and explored: first, we consider a lattice that illustrates relations of nonequivalent elementary cellular automata according to nearby subrules. Then, we introduce statistical measures that allow us to compare rules and subrules. Finally, we explore the possible similarities in the dynamics of a rule with respect to its subrules, obtaining both empirical and theoretical results.



Cortez, V., Medina, P., Goles, E., Zarama, R., & Rica, S. (2015). Attractors, statistics and fluctuations of the dynamics of the Schelling's model for social segregation. Eur. Phys. J. B, 88(1), 12 pp.
Abstract: Statistical properties, fluctuations and probabilistic arguments are shown to explain the robust dynamics of the Schelling's social segregation model. With the aid of probability density functions we characterize the attractors for multiple external parameters and conditions. We discuss the role of the initial states and we show that, indeed, the system evolves towards well defined attractors. Finally, we provide probabilistic arguments to explain quantitatively the observed behavior.



Demongeot, J., Goles, E., Morvan, M., Noual, M., & Sene, S. (2010). Attraction Basins as Gauges of Robustness against Boundary Conditions in Biological Complex Systems. PLoS One, 5(8), 18 pp.
Abstract: One fundamental concept in the context of biological systems on which researches have flourished in the past decade is that of the apparent robustness of these systems, i.e., their ability to resist to perturbations or constraints induced by external or boundary elements such as electromagnetic fields acting on neural networks, microRNAs acting on genetic networks and even hormone flows acting both on neural and genetic networks. Recent studies have shown the importance of addressing the question of the environmental robustness of biological networks such as neural and genetic networks. In some cases, external regulatory elements can be given a relevant formal representation by assimilating them to or modeling them by boundary conditions. This article presents a generic mathematical approach to understand the influence of boundary elements on the dynamics of regulation networks, considering their attraction basins as gauges of their robustness. The application of this method on a real genetic regulation network will point out a mathematical explanation of a biological phenomenon which has only been observed experimentally until now, namely the necessity of the presence of gibberellin for the flower of the plant Arabidopsis thaliana to develop normally.



Domic, N. G., Goles, E., & Rica, S. (2011). Dynamics and complexity of the Schelling segregation model. Phys. Rev. E, 83(5), 13 pp.
Abstract: In this paper we consider the Schelling social segregation model for two different populations. In Schelling's model, segregation appears as a consequence of discrimination, measured by the local difference between two populations. For that, the model defines a tolerance criterion on the neighborhood of an individual, indicating wether the individual is able to move to a new place or not. Next, the model chooses which of the available unhappy individuals really moves. In our work, we study the patterns generated by the dynamical evolution of the Schelling model in terms of various parameters or the initial condition, such as the size of the neighborhood of an inhabitant, the tolerance, and the initial number of individuals. As a general rule we observe that segregation patterns minimize the interface of zones of different people. In this context we introduce an energy functional associated with the configuration which is a strictly decreasing function for the tolerant people case. Moreover, as far as we know, we are the first to notice that in the case of a nonstrictlydecreasing energy functional, the system may segregate very efficiently.



Formenti, E., Goles, E., & Martin, B. (2012). Computational Complexity of Avalanches in the Kadanoff Sandpile Model. Fundam. Inform., 115(1), 107–124.
Abstract: This paper investigates the avalanche problem AP for the Kadanoff sandpile model (KSPM). We prove that (a slight restriction of) AP is in NC1 in dimension one, leaving the general case open. Moreover, we prove that AP is Pcomplete in dimension two. The proof of this latter result is based on a reduction from the monotone circuit value problem by building logic gates and wires which work with an initial sand distribution in KSPM. These results are also related to the known prediction problem for sandpiles which is in NC1 for onedimensional sandpiles and Pcomplete for dimension 3 or higher. The computational complexity of the prediction problem remains open for the Bak's model of twodimensional sandpiles.



Gajardo, A., & Goles, E. (2006). Crossing information in twodimensional Sandpiles. Theor. Comput. Sci., 369(13), 463–469.
Abstract: We prove that in a twodimensional Sandpile automaton, embedded in a regular infinite planar cellular space, it is impossible to cross information, if the bit of information is the presence (or absence) of an avalanche. This proves that it is impossible to embed arbitrary logical circuits in a Sandpile through quiescent configurations. Our result applies also for the nonplanar neighborhood of Moore. Nevertheless, we also show that it is possible to compute logical circuits with a twodimensional Sandpile, if a neighborhood of radius two is used in Z(2); crossing information becomes possible in that case, and we conclude that for this neighborhood the Sandpde is Pcomplete and Turing universal. (c) 2006 Elsevier B.V. All rights reserved.



Goles, E., & Gomez, L. (2018). Combinatorial game associated to the one dimensional Schelling's model of social segregation. Nat. Comput., 17(2), 427–436.
Abstract: In this paper we consider a finite onedimensional lattice with sites such that one of them is empty and the others have a black or white token. There are two players (one for each color), such that step by step alternately they move one of their tokens to the empty site trying to obtain a connected configuration. This game is related with the Schelling's social segregation model, where colors represent two different populations such that each one tries to take up a position with more neighbors as itself (same color). In this work we study strategies to play the game as well as their relation with the associated Schelling's onedimensional case (line and cycle graphs).



Goles, E., & Montealegre, P. (2014). Computational complexity of threshold automata networks under different updating schemes. Theor. Comput. Sci., 559, 3–19.
Abstract: Given a threshold automata network, as well as an updating scheme over its vertices, we study the computational complexity associated with the prediction of the future state of a vertex. More precisely, we analyze two classes of local functions: the majority and the ANDOR rule (vertices take the AND or the OR logic functions over the state of its neighborhoods). Depending on the updating scheme, we determine the complexity class (NC, P, NP, PSPACE) where the prediction problem belongs. (C) 2014 Elsevier B.V. All rights reserved.



Goles, E., & Montealegre, P. (2015). The complexity of the majority rule on planar graphs. Adv. Appl. Math., 64, 111–123.
Abstract: We study the complexity of the majority rule on planar automata networks. We reduce a special case of the Monotone Circuit Value Problem to the prediction problem of determining if a vertex of a planar graph will change its state when the network is updated with the majority rule. (C) 2014 Elsevier Inc. All rights reserved.



Goles, E., & Montealegre, P. (2020). The complexity of the asynchronous prediction of the majority automata. Inf. Comput., 274(SI).
Abstract: We consider the asynchronous prediction problem for some automaton as the one consisting in determining, given an initial configuration, if there exists a nonzero probability that some selected site changes its state, when the network is updated picking one site at a time uniformly at random. We show that for the majority automaton, the asynchronous prediction problem is in NC in the twodimensional lattice with von Neumann neighborhood. Later, we show that in three or more dimensions the problem is NPComplete.



Goles, E., & Moreira, A. (2012). NumberConserving Cellular Automata and Communication Complexity: A Numerical Exploration Beyond Elementary CAs. J. Cell. Autom., 7(2), 151–165.
Abstract: We perform a numerical exploration of numberconserving cellular automata (NCCA) beyond the class of elementary CAs, in search of examples with high communication complexity. We consider some possible generalizations of the elementary rule 184 (a minimal model of traffic, which is the only nontrivial elementary NCCA). as well as the classes of NCCAs which minimally extend either the radius or the state set (with respect to the 2 states and radius 1 of the elementary case). Both for 3 states and radius 1, and for 2 stales and radius 2, NCCA appear that are conjectured to have maximal (exponential) communication complexity. Examples are given also for (conjectured) linear and quadratic behaviour.



Goles, E., & Noual, M. (2012). Disjunctive networks and update schedules. Adv. Appl. Math., 48(5), 646–662.
Abstract: In this paper, we present a study of the dynamics of disjunctive networks under all blocksequential update schedules. We also present an extension of this study to more general fair periodic update schedules, that is, periodic update schedules that do not update some elements much more often than some others. Our main aim is to classify disjunctive networks according to the robustness of their dynamics with respect to changes of their update schedules. To study this robustness, we focus on one property, that of being able to cycle dynamically. (C) 2012 Elsevier Inc. All rights reserved.

