
Goles, E., Tsompanas, M. A., Adamatzky, A., Tegelaar, M., Wosten, H. A. B., & Martinez, G. J. (2020). Computational universality of fungal sandpile automata. Phys. Lett. A, 384(22), 8 pp.
Abstract: Hyphae within the mycelia of the ascomycetous fungi are compartmentalised by septa. Each septum has a pore that allows for intercompartmental and interhyphal streaming of cytosol and even organelles. The compartments, however, have special organelles, Woronin bodies, that can plug the pores. When the pores are blocked, no flow of cytoplasm takes place. Inspired by the controllable compartmentalisation within the mycelium of the ascomycetous fungi we designed twodimensional fungal automata. A fungal automaton is a cellular automaton where communication between neighbouring cells can be blocked on demand. We demonstrate computational universality of the fungal automata by implementing sandpile cellular automata circuits there. We reduce the Monotone Circuit Value Problem to the Fungal Automaton Prediction Problem. We construct families of wires, crossovers and gates to prove that the fungal automata are Pcomplete. (C) 2020 Elsevier B.V. All rights reserved.



Goles, E., Montealegre, P., & RiosWilson, M. (2020). On The Effects Of Firing Memory In The Dynamics Of Conjunctive Networks. Discret. Contin. Dyn. Syst., 40(10), 5765–5793.
Abstract: A boolean network is a map F : {0, 1}(n) > {0, 1}(n) that defines a discrete dynamical system by the subsequent iterations of F. Nevertheless, it is thought that this definition is not always reliable in the context of applications, especially in biology. Concerning this issue, models based in the concept of adding asynchronicity to the dynamics were propose. Particularly, we are interested in a approach based in the concept of delay. We focus in a specific type of delay called firing memory and it effects in the dynamics of symmetric (nondirected) conjunctive networks. We find, in the caseis in which the implementation of the delay is not uniform, that all the complexity of the dynamics is somehow encapsulated in the component in which the delay has effect. Thus, we show, in the homogeneous case, that it is possible to exhibit attractors of nonpolynomial period. In addition, we study the prediction problem consisting in, given an initial condition, determinate if a fixed coordinate will eventually change its state. We find again that in the nonhomogeneous case all the complexity is determined by the component that is affected by the delay and we conclude in the homogeneous case that this problem is PSPACEcomplete.



Travisany, D., Goles, E., Latorre, M., Cort?s, M. P., & Maass, A. (2020). Generation and robustness of Boolean networks to model Clostridium difficile infection. Nat. Comput., 19(1), 111–134.
Abstract: One of the more common healthcare associated infection is Chronic diarrhea. This disease is caused by the bacterium Clostridium difficile which alters the normal composition of the human gut flora. The most successful therapy against this infection is the fecal microbial transplant (FMT). They displace C. difficile and contribute to gut microbiome resilience, stability and prevent further episodes of diarrhea. The microorganisms in the FMT their interactions and inner dynamics reshape the gut microbiome to a healthy state. Even though microbial interactions play a key role in the development of the disease, currently, little is known about their dynamics and properties. In this context, a Boolean network model for C. difficile infection (CDI) describing one set of possible interactions was recently presented. To further explore the space of possible microbial interactions, we propose the construction of a neutral space conformed by a set of models that differ in their interactions, but share the final community states of the gut microbiome under antibiotic perturbation and CDI. To begin with the analysis, we use the previously described Boolean network model and we demonstrate that this model is in fact a threshold Boolean network (TBN). Once the TBN model is set, we generate and use an evolutionary algorithm to explore to identify alternative TBNs. We organize the resulting TBNs into clusters that share similar dynamic behaviors. For each cluster, the associated neutral graph is constructed and the most relevant interactions are identified. Finally, we discuss how these interactions can either affect or prevent CDI.



Vieira, A. P., Goles, E., & Herrmann, H. J. (2020). Dynamics of extended Schelling models. J. Stat. Mech.Theory Exp., 2020(1), 17 pp.
Abstract: We explore extensions of Schelling's model of social dynamics, in which two types of agents live on a checkerboard lattice and move in order to optimize their own satisfaction, which depends on how many agents among their neighbors are of their same type. For each number n of sametype nearest neighbors we independently assign a binary satisfaction variable s(k) which is equal to one only if the agent is satisfied with that condition, and is equal to zero otherwise. This defines 32 different satisfaction rules, which we investigate in detail, focusing on pattern formation and measuring segregation with the help of an 'energy' function which is related to the number of neighboring agents of different types and plays no role in the dynamics. We consider the checkerboard lattice to be fully occupied and the dynamics consist of switching the locations of randomly selected unsatisfied agents of opposite types. We show that, starting from a random distribution of agents, only a small number of rules lead to (nearly) fully segregated patterns in the long run, with many rules leading to chaotic steadystate behavior. Nevertheless, other interesting patterns may also be dynamically generated, such as 'antisegregated' patterns as well as patterns resembling sponges.



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.



Goles, E., Lobos, F., Ruz, G. A., & Sene, S. (2020). Attractor landscapes in Boolean networks with firing memory: a theoretical study applied to genetic networks. Nat. Comput., to appear, 25 pp.
Abstract: In this paper we study the dynamical behavior of Boolean networks with firing memory, namely Boolean networks whose vertices are updated synchronously depending on their proper Boolean local transition functions so that each vertex remains at its firing state a finite number of steps. We prove in particular that these networks have the same computational power than the classical ones, i.e. any Boolean network with firing memory composed of m vertices can be simulated by a Boolean network by adding vertices. We also prove general results on specific classes of networks. For instance, we show that the existence of at least one delay greater than 1 in disjunctive networks makes such networks have only fixed points as attractors. Moreover, for arbitrary networks composed of two vertices, we characterize the delay phase space, i.e. the delay values such that networks admits limit cycles or fixed points. Finally, we analyze two classical biological models by introducing delays: the model of the immune control of the lambda\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{69pt} \begin{document}$$\lambda $$\end{document}phage and that of the genetic control of the floral morphogenesis of the plant Arabidopsis thaliana.



Goles, E., & Montealegre, P. (2020). The complexity of the asynchronous prediction of the majority automata. Inform. Comput., to appear.
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.



MacLean, S., MontalvaMedel, M., & Goles, E. (2019). Block invariance and reversibility of one dimensional linear cellular automata. Adv. Appl. Math., 105, 83–101.
Abstract: Consider a onedimensional, binary cellular automaton f (the CA rule), where its n nodes are updated according to a deterministic block update (blocks that group all the nodes and such that its order is given by the order of the blocks from left to right and nodes inside a block are updated synchronously). A CA rule is block invariant over a family F of block updates if its set of periodic points does not change, whatever the block update of F is considered. In this work, we study the block invariance of linear CA rules by means of the property of reversibility of the automaton because such a property implies that every configuration has a unique predecessor, so, it is periodic. Specifically, we extend the study of reversibility done for the Wolfram elementary CA rules 90 and 150 as well as, we analyze the reversibility of linear rules with neighbourhood radius 2 by using matrix algebra techniques. (C) 2019 Elsevier Inc. All rights reserved.



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.



Ruz, G. A., Zuniga, A., & Goles, E. (2018). A Boolean network model of bacterial quorumsensing systems. Int. J. Data Min. Bioinform., 21(2), 123–144.
Abstract: There are several mathematical models to represent gene regulatory networks, one of the simplest is the Boolean network paradigm. In this paper, we reconstruct a regulatory network of bacterial quorumsensing systems, in particular, we consider Paraburkholderia phytofirmans PsJN which is a plant growth promoting bacteria that produces positive effects in horticultural crops like tomato, potato and grape. To learn the regulatory network from temporal expression pattern of quorumsensing genes at root plants, we present a methodology that considers the training of perceptrons for each gene and then the integration into one Boolean regulatory network. Using the proposed approach, we were able to infer a regulatory network model whose topology and dynamic exhibited was helpful to gain insight on the quorumsensing systems regulation mechanism. We compared our results with REVEAL and BestFit extension algorithm, showing that the proposed neural network approach obtained a more biologically meaningful network and dynamics, demonstrating the effectiveness of the proposed method.



Lobos, F., Goles, E., Ruivo, E. L. P., de Oliveira, P. P. B., & Montealegre, P. (2018). Mining a Class of Decision Problems for Onedimensional Cellular Automata. J. Cell. Autom., 13(56), 393–405.
Abstract: Cellular automata are locally defined, homogeneous dynamical systems, discrete in space, time and state variables. Within the context of onedimensional, binary, cellular automata operating on cyclic configurations of odd length, we consider the general decision problem: if the initial configuration satisfies a given property, the lattice should converge to the fixedpoint of all 1s ((1) over right arrow), or to (0) over right arrow, otherwise. Two problems in this category have been widely studied in the literature, the parity problem [1] and the density classification task [4]. We are interested in determining all cellular automata rules with neighborhood sizes of 2, 3, 4 and 5 cells (i.e., radius r of 0.5, 1, 1.5 and 2.5) that solve decision problems of the previous type. We have demonstrated a theorem that, for any given rule in those spaces, ensures the non existence of fixed points other than (0) over right arrow and (1) over right arrow for configurations of size larger than 2(2r), provided that the rule does not support different fixed points for any configuration with size smaller than or equal to 2(2r). In addition, we have a proposition that ensures the convergence to only (0) over right arrow or (1) over right arrow of any initial configuration, if the rule complies with given conditions. By means of theoretical and computational approaches, we determined that: for the rule spaces defined by radius 0.5 and r = 1, only 1 and 2 rules, respectively, converge to (1) over right arrow or (0) over right arrow, to any initial configuration, and both recognize the same language, and for the rule space defined by radius r = 1.5, 40 rules satisfy this condition and recognize 4 different languages. Finally, for the radius 2 space, out of the 4,294,967,296 different rules, we were able to significantly filter it out, down to 40,941 candidate rules. We hope such an extensive mining should unveil new decision problems of the type widely studied in the literature.



MontalvaMedel, M., de Oliveira, P. P. B., & Goles, E. (2018). A portfolio of classification problems by onedimensional cellular automata, over cyclic binary configurations and parallel update. Nat. Comput., 17(3), 663–671.
Abstract: Decision problems addressed by cellular automata have been historically expressed either as determining whether initial configurations would belong to a given language, or as classifying the initial configurations according to a property in them. Unlike traditional approaches in language recognition, classification problems have typically relied upon cyclic configurations and fully paralell (twoway) update of the cells, which render the action of the cellular automaton relatively less controllable and difficult to analyse. Although the notion of cyclic languages have been studied in the wider realm of formal languages, only recently a more systematic attempt has come into play in respect to cellular automata with fully parallel update. With the goal of contributing to this effort, we propose a unified definition of classification problem for onedimensional, binary cellular automata, from which various known problems are couched in and novel ones are defined, and analyse the solvability of the new problems. Such a unified perspective aims at increasing existing knowledge about classification problems by cellular automata over cyclic configurations and parallel update.



Ruivo, E. L. P., de Oliveira, P. P. B., Lobos, F., & Goles, E. (2018). Shiftequivalence of kary, onedimensional cellular automata rules. Commun. Nonlinear Sci. Numer. Simul., 63, 280–291.
Abstract: Cellular automata are locallydefined, synchronous, homogeneous, fully discrete dynamical systems. In spite of their typically simple local behaviour, many are capable of showing complex emergent behaviour. When looking at their timeevolution, one may be interested in studying their qualitative dynamical behaviour. One way to group rules that display the same qualitative behaviour is by defining symmetries that map rules to others, the simplest way being by means of permutations in the set of state variables and reflections in their neighbourhood definitions, therefore defining equivalence classes. Here, we introduce the notion of shiftequivalence as another kind of symmetry, now relative to the concept of translation. After defining the notion and showing it indeed defines an equivalence relation, we extend the usual characterisation of dynamical equivalence and use it to partition some specific binary cellular automata rule spaces. Finally, we give a characterisation of the class of shiftequivalent rules in terms of the local transition functions of the cellular automata in the class, by providing an algorithm to compute the members of the class, for any kary, onedimensional rule. (C) 2018 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., Perrot, K., & Theyssier, G. (2018). On the complexity of twodimensional signed majority cellular automata. J. Comput. Syst. Sci., 91, 1–32.
Abstract: We study the complexity of signed majority cellular automata on the planar grid. We show that, depending on their symmetry and uniformity, they can simulate different types of logical circuitry under different modes. We use this to establish new bounds on their overall complexity, concretely: the uniform asymmetric and the nonuniform symmetric rules are Turing universal and have a Pcomplete prediction problem; the nonuniform asymmetric rule is intrinsically universal; no symmetric rule can be intrinsically universal. We also show that the uniform asymmetric rules exhibit cycles of superpolynomial length, whereas symmetric ones are known to have bounded cycle length. (C) 2017 Elsevier Inc. All rights reserved.



Goles, E., MontalvaMedel, M., MacLean, S., & Mortveit, H. (2018). Block Invariance in a Family of Elementary Cellular Automata. J. Cell. Autom., 13(12), 15–32.
Abstract: We study the steady state invariance of elementary cellular automata (ECA) under different deterministic updating schemes. Specifically, we study a family of eleven ECA whose steady state invariance were left under conjecture in [2].



Medina, P., Goles, E., Zarama, R., & Rica, S. (2017). SelfOrganized Societies: On the Sakoda Model of Social Interactions. Complexity, , 16 pp.
Abstract: We characterize the behavior and the social structures appearing from a model of general social interaction proposed by Sakoda. The model consists of two interacting populations in a twodimensional periodic lattice with empty sites. It contemplates a set of simple rules that combine attitudes, ranges of interactions, and movement decisions. We analyze the evolution of the 45 different interaction rules via a Pottslike energy function which drives the system irreversibly to an equilibriumor a steady state. We discuss the robustness of the social structures, dynamical behaviors, and the existence of spatial long range order in terms of the social interactions and the equilibrium energy.



Mascareno, A., Goles, E., & Ruz, G. A. (2016). Crisis in complex social systems: A social theory view illustrated with the chilean case. Complexity, 21(S2), 13–23.
Abstract: The article argues that crises are a distinctive feature of complex social systems. A quest for connectivity of communication leads to increase systems' own robustness by constantly producing further connections. When some of these connections have been successful in recent operations, the system tends to reproduce the emergent pattern, thereby engaging in a nonreflexive, repetitive escalation of more of the same communication. This compulsive growth of systemic communication in crisis processes, or logic of excess, resembles the dynamic of selforganized criticality. Accordingly, we first construct the conceptual foundations of our approach. Second, we present three core assumptions related to the generative mechanism of social crises, their temporal transitions (incubation, contagion, restructuring), and the suitable modeling techniques to represent them. Third, we illustrate the conceptual approach with a percolation model of the crisis in Chilean education system. (c) 2016 Wiley Periodicals, Inc. Complexity 21: 1323, 2016



Goles, E., Montealegre, P., & Vera, J. (2016). Naming Game Automata Networks. J. Cell. Autom., 11(56), 497–521.
Abstract: In this paper we introduce automata networks to model some features of the emergence of a vocabulary related with the naming game model. We study the dynamical behaviour (attractors and convergence) of extremal and majority local functions.



Vera, J., & Goles, E. (2016). Automata Networks for Memory Loss Effects in the Formation of Linguistic Conventions. Cogn. Comput., 8(3), 462–466.
Abstract: This work attempts to give new theoretical insights into the absence of intermediate stages in the evolution of language. In particular, a mathematical model, based on automata networks, is proposed with the purpose to answer a crucial question: How a population of language users can reach agreement on linguistic conventions? To describe the appearance of drastic transitions in the development of language, an extremely simple model of working memory is adopted: at each time step, language users simply lose part of their word memories according to a forgetfulness parameter. Through computer simulations on lowdimensional lattices, sharp transitions at critical values of the parameter are described.

