Home  << 1 2 3 4 >> 
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.
Keywords: fungi; ascomycete; Woronin body; cellular automata

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.
Keywords: Boolean network; Update schedule; Robustness; Attractor; Dynamical cycle

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.
Keywords: Political polarization; Opinion formation; Activists; Markov chains; Game theory

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.
Keywords: cellular automata; majority rule; prediction problem

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., Adamatzky, A., Montealegre, P., & RiosWilson, M. (2021). Generating Boolean Functions on Totalistic Automata Networks. Int. J. Unconv. Comput., 16(4), 343–391.
Abstract: We consider the problem of studying the simulation capabilities of the dynamics of arbitrary networks of finite states machines. In these models, each node of the network takes two states 0 (passive) and 1 (active). The states of the nodes are updated in parallel following a local totalistic rule, i.e., depending only on the sum of active states. Four families of totalistic rules are considered: linear or matrix defined rules (a node takes state 1 if each of its neighbours is in state 1), threshold rules (a node takes state 1 if the sum of its neighbours exceed a threshold), isolated rules (a node takes state 1 if the sum of its neighbours equals to some single number) and interval rule (a node takes state 1 if the sum of its neighbours belong to some discrete interval). We focus in studying the simulation capabilities of the dynamics of each of the latter classes. In particular, we show that totalistic automata networks governed by matrix defined rules can only implement constant functions and other matrix defined functions. In addition, we show that t by threshold rules can generate any monotone Boolean functions. Finally, we show that networks driven by isolated and the interval rules exhibit a very rich spectrum of boolean functions as they can, in fact, implement any arbitrary Boolean functions. We complement this results by studying experimentally the set of different Boolean functions generated by totalistic rules on random graphs.
Keywords: UNIVERSALITY; PROPAGATION; COMPLEXITY

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., Guillon, P., & Rapaport, I. (2011). Traced communication complexity of cellular automata. Theor. Comput. Sci., 412(30), 3906–3916.
Abstract: We study cellular automata with respect to a new communication complexity problem: each of two players know half of some finite word, and must be able to tell whether the state of the central cell will follow a given evolution, by communicating as little as possible between each other. We present some links with classical dynamical concepts, especially equicontinuity, expansivity, entropy and give the asymptotic communication complexity of most elementary cellular automata. (C) 2011 Elsevier B.V. All rights reserved.
Keywords: Cellular automata; Communication complexity

Goles, E., Lobos, F., Montealegre, P., Ruivo, E. L. P., & de Oliveira, P. P. B. (2020). Computational Complexity of the Stability Problem for Elementary Cellular Automata. J. Cell. Autom., 15(4), 261–304.
Abstract: Given an elementary cellular automaton and a cell v, we define the stability decision problem as the determination of whether or not the state of cell v will ever change, at least once, during the time evolution of the rule, over a finite input configuration. Here, we perform the study of the entire elementary cellular automata rule space, for the two possible decision cases of the problem, namely, changes in v from state 0 to 1 (0 > 1), and the other way round (1 > 0). Out of the 256 elementary cellular automata, we show that for all of them, at least one of the two decision problems is in the NC complexity class.

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., 19(2), 295–319.
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., Maldonado, D., & Montealecre, P. (2021). On the complexity of asynchronous freezing cellular automata. Inf. Comput., 281, 104764.
Abstract: In this paper we study the family of freezing cellular automata (FCA) in the context of asynchronous updating schemes. A cellular automaton is called freezing if there exists an order of its states, and the transitions are only allowed to go from a lower to a higher state. A cellular automaton is asynchronous if at each timestep only one cell is updated. We define the problem ASYNCUNSTABILITY, which consists in deciding there exists a sequential updating scheme that changes the state of a given cell.
We begin showing that ASYNCUNSTABILITY is in NL for any onedimensional FCA. Then we focus on the family of lifelike freezing CA (LFCA). We study the complexity of ASYNCUNSTABILITY for all LFCA in the triangular and square grids, showing that almost all of them can be solved in NC, except for one rule for which the problem is NPComplete. (C) 2021 Elsevier Inc. All rights reserved. Area: 08905401

Goles, E., Maldonado, D., Montealegre, P., & Ollinger, N. (2020). On the complexity of the stability problem of binary freezing totalistic cellular automata. Inf. Comput., 274, 21 pp.
Abstract: In this paper we study the family of twostate Totalistic Freezing Cellular Automata (TFCA) defined over the triangular and square grids with von Neumann neighborhoods. We say that a Cellular Automaton is Freezing and Totalistic if the active cells remain unchanged, and the new value of an inactive cell depends only on the sum of its active neighbors. We classify all the Cellular Automata in the class of TFCA, grouping them in five different classes: the Trivial rules, Turing Universal rules, Algebraic rules, Topological rules and Fractal Growing rules. At the same time, we study in this family the STABILITY problem, consisting in deciding whether an inactive cell becomes active, given an initial configuration. We exploit the properties of the automata in each group to show that: For Algebraic and Topological Rules the STABILITY problem is in NC. For Turing Universal rules the STABILITY problem is PComplete. (C) 2020 Elsevier Inc. All rights reserved.
