|   | 
Details
   web
Records
Author (up) Adamatzky, A.; Goles, E.; Martinez, GJ.; Tsompanas, MA.; Tegelaar, M.; Wosten, HAB.
Title Fungal Automata Type
Year 2020 Publication Complex Systems Abbreviated Journal Complex Syst.
Volume 29 Issue 4 Pages 759-778
Keywords fungi; ascomycete; Woronin body; cellular automata
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 one-dimensional fungal automaton is a binary-state 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 cell-state transition and pore-state transition rules and the complexity of fungal automata with just a few Woronin bodies, and exemplify several important local events in the automaton dynamics.
Address
Corporate Author Thesis
Publisher Place of Publication Editor
Language Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0891-2513 ISBN Medium
Area Expedition Conference
Notes WOS:000604844500002 Approved
Call Number UAI @ alexi.delcanto @ Serial 1319
Permanent link to this record
 

 
Author (up) Aracena, J.; Goles, E.; Moreira, A.; Salinas, L.
Title On the robustness of update schedules in Boolean networks Type
Year 2009 Publication Biosystems Abbreviated Journal Biosystems
Volume 97 Issue 1 Pages 1-8
Keywords Boolean network; Update schedule; Robustness; Attractor; Dynamical cycle
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, block-sequential, 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.
Address [Aracena, J.] Univ Concepcion, Dept Ingn Matemat, Concepcion, Chile, Email: jaracena@ing-mat.udec.cl
Corporate Author Thesis
Publisher Elsevier Sci Ltd Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0303-2647 ISBN Medium
Area Expedition Conference
Notes WOS:000267528900001 Approved
Call Number UAI @ eduardo.moreno @ Serial 29
Permanent link to this record
 

 
Author (up) Bitar, N.; Goles, E.; Montealegre, P.
Title COMPUTATIONAL COMPLEXITY OF BIASED DIFFUSION-LIMITED AGGREGATION Type
Year 2022 Publication Siam Journal On Discrete Mathematics Abbreviated Journal SIAM Discret. Math.
Volume 36 Issue 1 Pages 823-866
Keywords diffusion-limited aggregation; computational complexity; space complexity; NL-completeness; P-completeness
Abstract Diffusion-Limited Aggregation (DLA) is a cluster-growth model that consists in a set of particles that are sequentially aggregated over a two-dimensional 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 k-DLA 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 P-Complete for 2-DLA (thus for 3-DLA). Later, we show that Prediction can be solved much more efficiently for 1-DLA. In fact, we show that in that case the problem is NL-Complete. With respect to Realization, we show that restricted to 2-DLA the problem is in P, while in the 1-DLA case, the problem is in L.
Address
Corporate Author Thesis
Publisher Place of Publication Editor
Language Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0895-4801 ISBN Medium
Area Expedition Conference
Notes WOS:000778502000037 Approved
Call Number UAI @ alexi.delcanto @ Serial 1558
Permanent link to this record
 

 
Author (up) Bottcher, L.; Montealegre, P.; Goles, E.; Gersbach, H.
Title Competing activists-Political polarization Type
Year 2020 Publication Physica A-Statistical Mechanics And Its Applications Abbreviated Journal Physica A
Volume 545 Issue Pages 13 pp
Keywords Political polarization; Opinion formation; Activists; Markov chains; Game theory
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.
Address [Boettcher, Lucas] Swiss Fed Inst Technol, Inst Theoret Phys, CH-8093 Zurich, Switzerland, Email: lucasb@ethz.ch
Corporate Author Thesis
Publisher Elsevier Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0378-4371 ISBN Medium
Area Expedition Conference
Notes WOS:000526845600034 Approved
Call Number UAI @ eduardo.moreno @ Serial 1147
Permanent link to this record
 

 
Author (up) Bottcher, L.; Woolley-Meza, O.; Goles, E.; Helbing, D.; Herrmann, H.J.
Title Connectivity disruption sparks explosive epidemic spreading Type
Year 2016 Publication Physical Review E Abbreviated Journal Phys. Rev. E
Volume 93 Issue 4 Pages 8 pp
Keywords
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 susceptible-infected-susceptible 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.
Address [Bottcher, L.] ETH, Wolfgang Pauli Str 27, CH-8093 Zurich, Switzerland, Email: lucasb@ethz.ch
Corporate Author Thesis
Publisher Amer Physical Soc Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 2470-0045 ISBN Medium
Area Expedition Conference
Notes WOS:000374962100010 Approved
Call Number UAI @ eduardo.moreno @ Serial 615
Permanent link to this record
 

 
Author (up) Canals, C.; Goles, E.; Mascareno, A.; Rica, S.; Ruz, G.A.
Title School Choice in a Market Environment: Individual versus Social Expectations Type
Year 2018 Publication Complexity Abbreviated Journal Complexity
Volume 3793095 Issue Pages 11 pp
Keywords
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.
Address [Canals, Catalina; Goles, Eric; Rica, Sergio; Ruz, Gonzalo A.] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Av Diagonal Las Torres 2640, Santiago, Chile, Email: gonzalo.ruz@uai.cl
Corporate Author Thesis
Publisher Wiley-Hindawi Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 1076-2787 ISBN Medium
Area Expedition Conference
Notes WOS:000454095100001 Approved
Call Number UAI @ eduardo.moreno @ Serial 955
Permanent link to this record
 

 
Author (up) Concha-Vega, P.; Goles, E.; Montealegre, P.; Rios-Wilson, M
Title On the Complexity of Stable and Biased Majority Type
Year 2022 Publication Mathematics Abbreviated Journal Mathematics
Volume 10 Issue 18 Pages 3408
Keywords cellular automata; majority rule; prediction problem
Abstract A majority automata is a two-state 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 time-step. 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 P-Complete as a consequence of the capability of the system of simulating Boolean circuits.
Address
Corporate Author Thesis
Publisher Place of Publication Editor
Language Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 2227-7390 ISBN Medium
Area Expedition Conference
Notes WOS:000856736200001 Approved
Call Number UAI @ alexi.delcanto @ Serial 1642
Permanent link to this record
 

 
Author (up) Concha-Vega, P.; Goles, E.; Montealegre, P.; Rios-Wilson, M.; Santivanez, J.
Title Introducing the activity parameter for elementary cellular automata Type
Year 2022 Publication International Journal Of Modern Physics C Abbreviated Journal Int. J. Mod Phys. C
Volume 33 Issue 09 Pages 2250121
Keywords Discrete dynamical systems; elementary cellular automata; rule space
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 R-1 is called a sub-rule of R-2 if the set of active transitions of R-1 is a subset of the active transitions of R-2.

In this paper, the notion of sub-rule for elementary cellular automata is introduced and explored: first, we consider a lattice that illustrates relations of nonequivalent elementary cellular automata according to nearby sub-rules. Then, we introduce statistical measures that allow us to compare rules and sub-rules. Finally, we explore the possible similarities in the dynamics of a rule with respect to its sub-rules, obtaining both empirical and theoretical results.
Address
Corporate Author Thesis
Publisher Place of Publication Editor
Language Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0129-1831 ISBN Medium
Area Expedition Conference
Notes WOS:000840726100005 Approved
Call Number UAI @ alexi.delcanto @ Serial 1630
Permanent link to this record
 

 
Author (up) Cortez, V.; Medina, P.; Goles, E.; Zarama, R.; Rica, S.
Title Attractors, statistics and fluctuations of the dynamics of the Schelling's model for social segregation Type
Year 2015 Publication European Physical Journal B Abbreviated Journal Eur. Phys. J. B
Volume 88 Issue 1 Pages 12 pp
Keywords
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.
Address [Cortez, Vasco; Goles, Eric; Rica, Sergio] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Santiago, Chile, Email: sergio.rica@gmail.com
Corporate Author Thesis
Publisher Springer Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 1434-6028 ISBN Medium
Area Expedition Conference
Notes WOS:000348059300001 Approved
Call Number UAI @ eduardo.moreno @ Serial 436
Permanent link to this record
 

 
Author (up) Demongeot, J.; Goles, E.; Morvan, M.; Noual, M.; Sene, S.
Title Attraction Basins as Gauges of Robustness against Boundary Conditions in Biological Complex Systems Type
Year 2010 Publication Plos One Abbreviated Journal PLoS One
Volume 5 Issue 8 Pages 18 pp
Keywords
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, micro-RNAs 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.
Address [Demongeot, Jacques] Univ Grenoble 1, TIMC IMAG, CNRS, UMR 5525, La Tronche, France, Email: Sylvain.Sene@ibisc.univ-evry.fr
Corporate Author Thesis
Publisher Public Library Science Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 1932-6203 ISBN Medium
Area Expedition Conference
Notes WOS:000280605400002 Approved
Call Number UAI @ eduardo.moreno @ Serial 92
Permanent link to this record
 

 
Author (up) Domic, N.G.; Goles, E.; Rica, S.
Title Dynamics and complexity of the Schelling segregation model Type
Year 2011 Publication Physical Review E Abbreviated Journal Phys. Rev. E
Volume 83 Issue 5 Pages 13 pp
Keywords
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 non-strictly-decreasing energy functional, the system may segregate very efficiently.
Address [Goles Domic, Nicolas] Univ Tecn Federico Santa Maria, Dept Informat, Santiago, Chile
Corporate Author Thesis
Publisher Amer Physical Soc Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 1539-3755 ISBN Medium
Area Expedition Conference
Notes WOS:000290725800001 Approved
Call Number UAI @ eduardo.moreno @ Serial 146
Permanent link to this record
 

 
Author (up) Formenti, E.; Goles, E.; Martin, B.
Title Computational Complexity of Avalanches in the Kadanoff Sandpile Model Type
Year 2012 Publication Fundamenta Informaticae Abbreviated Journal Fundam. Inform.
Volume 115 Issue 1 Pages 107-124
Keywords Kadanoff Sandpile Model; Bak Sandpile Model; Sandpiles Models; Complexity; Discrete Dynamical Systems; Self-Organized Criticality (SOC)
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 P-complete 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 one-dimensional sandpiles and P-complete for dimension 3 or higher. The computational complexity of the prediction problem remains open for the Bak's model of two-dimensional sandpiles.
Address [Formenti, Enrico] Univ Nice Sophia Antipolis, I3S, UMR CNRS 6070, F-06903 Sophia Antipolis, France, Email: enrico.formenti@unice.fr
Corporate Author Thesis
Publisher Ios Press Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0169-2968 ISBN Medium
Area Expedition Conference
Notes WOS:000302777200008 Approved
Call Number UAI @ eduardo.moreno @ Serial 208
Permanent link to this record
 

 
Author (up) Gajardo, A.; Goles, E.
Title Crossing information in two-dimensional Sandpiles Type
Year 2006 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.
Volume 369 Issue 1-3 Pages 463-469
Keywords Sandpile; discrete dynamical system; cellular automata; calculability; complexity
Abstract We prove that in a two-dimensional 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 non-planar neighborhood of Moore. Nevertheless, we also show that it is possible to compute logical circuits with a two-dimensional 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 P-complete and Turing universal. (c) 2006 Elsevier B.V. All rights reserved.
Address Univ Adolfo Ibanez, Santiago, Chile, Email: anahi@ing-mat.udec.cl
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0304-3975 ISBN Medium
Area Expedition Conference
Notes WOS:000242765000035 Approved
Call Number UAI @ eduardo.moreno @ Serial 34
Permanent link to this record
 

 
Author (up) Goles, E.; Adamatzky, A.; Montealegre, P.; Rios-Wilson, M.
Title Generating Boolean Functions on Totalistic Automata Networks Type
Year 2021 Publication International Journal of Unconventional Computing Abbreviated Journal Int. J. Unconv. Comput.
Volume 16 Issue 4 Pages 343-391
Keywords UNIVERSALITY; PROPAGATION; COMPLEXITY
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.
Address
Corporate Author Thesis
Publisher Place of Publication Editor
Language Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 1548-7199 ISBN Medium
Area Expedition Conference
Notes WOS:000654165700002 Approved
Call Number UAI @ alexi.delcanto @ Serial 1393
Permanent link to this record
 

 
Author (up) Goles, E.; Gomez, L.
Title Combinatorial game associated to the one dimensional Schelling's model of social segregation Type
Year 2018 Publication Natural Computing Abbreviated Journal Nat. Comput.
Volume 17 Issue 2 Pages 427-436
Keywords Combinatorial game; Schelling's social segregation model; Draw strategy; Energy
Abstract In this paper we consider a finite one-dimensional 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 one-dimensional case (line and cycle graphs).
Address [Goles, Eric; Gomez, Luis] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Santiago 2640, Chile, Email: eric.chacc@uai.cl;
Corporate Author Thesis
Publisher Springer Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 1567-7818 ISBN Medium
Area Expedition Conference
Notes WOS:000432329500016 Approved
Call Number UAI @ eduardo.moreno @ Serial 869
Permanent link to this record
 

 
Author (up) Goles, E.; Guillon, P.; Rapaport, I.
Title Traced communication complexity of cellular automata Type
Year 2011 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.
Volume 412 Issue 30 Pages 3906-3916
Keywords Cellular automata; Communication complexity
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.
Address [Guillon, P; Rapaport, I] Univ Chile, DIM CMM, CNRS, UMI 2807, Santiago, Chile, Email: eric.chacc@uai.cl
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0304-3975 ISBN Medium
Area Expedition Conference
Notes WOS:000292589800009 Approved
Call Number UAI @ eduardo.moreno @ Serial 152
Permanent link to this record
 

 
Author (up) Goles, E.; Lobos, F.; Montealegre, P.; Ruivo, ELP.; de Oliveira, PPB.
Title Computational Complexity of the Stability Problem for Elementary Cellular Automata Type
Year 2020 Publication Journal of Cellular Automata Abbreviated Journal J. Cell. Autom.
Volume 15 Issue 4 Pages 261-304
Keywords One-dimensional cellular automata; elementary cellular automata; computational complexity; stability problem; decision problem
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.
Address
Corporate Author Thesis
Publisher Place of Publication Editor
Language Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 1557-5969 ISBN Medium
Area Expedition Conference
Notes WOS:000613086900002 Approved
Call Number UAI @ alexi.delcanto @ Serial 1329
Permanent link to this record
 

 
Author (up) Goles, E.; Lobos, F.; Ruz, G.A.; Sene, S.
Title Attractor landscapes in Boolean networks with firing memory: a theoretical study applied to genetic networks Type
Year 2020 Publication Natural Computing Abbreviated Journal Nat. Comput.
Volume 19 Issue 2 Pages 295-319
Keywords Discrete dynamical systems; Boolean networks; Biological network modeling
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.
Address [Goles, Eric; Lobos, Fabiola; Ruz, Gonzalo A.] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Santiago, Chile, Email: eric.chacc@uai.cl;
Corporate Author Thesis
Publisher Springer Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 1567-7818 ISBN Medium
Area Expedition Conference
Notes WOS:000531210800001 Approved
Call Number UAI @ eduardo.moreno @ Serial 1139
Permanent link to this record
 

 
Author (up) Goles, E.; Maldonado, D.; Montealecre, P.
Title On the complexity of asynchronous freezing cellular automata Type
Year 2021 Publication Information and Computation Abbreviated Journal Inf. Comput.
Volume 281 Issue Pages 104764
Keywords Cellular automata; Computational complexity; Freezing dynamics
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 time-step 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 one-dimensional FCA. Then we focus on the family of life-like 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 NP-Complete. (C) 2021 Elsevier Inc. All rights reserved.
Address
Corporate Author Thesis
Publisher Place of Publication Editor
Language Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0890-5401 ISBN Medium
Area 0890-5401 Expedition Conference
Notes WOS:000721215200020 Approved
Call Number UAI @ alexi.delcanto @ Serial 1490
Permanent link to this record
 

 
Author (up) Goles, E.; Maldonado, D.; Montealegre, P.; Ollinger, N.
Title On the complexity of the stability problem of binary freezing totalistic cellular automata Type
Year 2020 Publication Information And Computation Abbreviated Journal Inf. Comput.
Volume 274 Issue Pages 21 pp
Keywords Cellular automata; Computational complexity; Freezing cellular automata; Totalistic cellular automata; Fast parallel algorithms; P-Complete
Abstract In this paper we study the family of two-state 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 P-Complete. (C) 2020 Elsevier Inc. All rights reserved.
Address [Goles, Eric; Montealegre, Pedro] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Santiago, Chile, Email: eric.chacc@uai.cl;
Corporate Author Thesis
Publisher Academic Press Inc Elsevier Science Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0890-5401 ISBN Medium
Area Expedition Conference
Notes WOS:000573267700008 Approved
Call Number UAI @ alexi.delcanto @ Serial 1238
Permanent link to this record