|   | 
Details
   web
Records
Author Goles, E.; Montalva-Medel, M.; MacLean, S.; Mortveit, H.
Title Block Invariance in a Family of Elementary Cellular Automata Type
Year 2018 Publication Journal Of Cellular Automata Abbreviated Journal J. Cell. Autom.
Volume 13 Issue 1-2 Pages 15-32
Keywords Elementary cellular automata; block updates; periodic configurations; block invariance
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].
Address [Goles, Eric; Montalva-Medel, Marco; MacLean, Stephanie] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Santiago, Chile, Email: eric.chacc@uai.cl;
Corporate Author Thesis
Publisher Old City Publishing Inc Place of Publication Editor
Language English 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:000410888100002 Approved
Call Number UAI @ eduardo.moreno @ Serial 782
Permanent link to this record
 

 
Author Goles, E.; Montalva-Medel, M.; Mortveit, H.; Ramirez-Flandes, S.
Title Block Invariance in Elementary Cellular Automata Type
Year 2015 Publication Journal Of Cellular Automata Abbreviated Journal J. Cell. Autom.
Volume 10 Issue 1-2 Pages 119-135
Keywords Elementary cellular automata; block updates; periodic points; block invariance
Abstract Consider an elementary cellular automaton (ECA) under periodic boundary conditions. Given an arbitrary partition of the set of vertices we consider the block updating, i.e. the automaton's local function is applied from the first to the last set of the partition such that vertices belonging to the same set are updated synchronously. The automaton is said block-invariant if the set of periodic configurations is independent of the choice of the block updating. When the sets of the partition are singletons we have the sequential updating: vertices are updated one by one following a permutation pi. In [5] the authors analyzed the pi-invariance of the 2(8) = 256 possible ECA rules (or the 88 non-redundant rules subset). Their main result was that for all n > 3, exactly 41 of these non-redundant rules are pi-invariant. In this paper we determine the subset of these 41 rules that are block invariant. More precisely, for all n > 3, exactly 15 of these rules are block invariant. Moreover, we deduce that block invariance also implies that the attractor structure itself is independent of the choice of the block update.
Address [Goles, Eric; Montalva-Medel, Marco; Ramirez-Flandes, Salvador] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Penalolen, Chile, Email: eric.chacc@uai.cl;
Corporate Author Thesis
Publisher Old City Publishing Inc Place of Publication Editor
Language English 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:000350183000006 Approved
Call Number UAI @ eduardo.moreno @ Serial 461
Permanent link to this record
 

 
Author MacLean, S.; Montalva-Medel, M.; Goles, E.
Title Block invariance and reversibility of one dimensional linear cellular automata Type
Year 2019 Publication Advances In Applied Mathematics Abbreviated Journal Adv. Appl. Math.
Volume 105 Issue Pages 83-101
Keywords Cellular automata; Linear cellular automata; Block invariance; Reversibility
Abstract Consider a one-dimensional, 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.
Address [MacLean, Stephanie; Montalva-Medel, Marco; Goles, Eric] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Diagonal Torres 2640, Penalolen, Chile, Email: stephanie.macleank@edu.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 0196-8858 ISBN Medium
Area Expedition Conference
Notes WOS:000459528000004 Approved
Call Number UAI @ eduardo.moreno @ Serial 983
Permanent link to this record
 

 
Author Montalva-Medel, M.; de Oliveira, P.P.B.; Goles, E.
Title A portfolio of classification problems by one-dimensional cellular automata, over cyclic binary configurations and parallel update Type
Year 2018 Publication Natural Computing Abbreviated Journal Nat. Comput.
Volume 17 Issue 3 Pages 663-671
Keywords One-dimensional cellular automata; Classification problem; Decision problem; Language recognition; Density; Parity; Emergent computation
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 (two-way) 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 one-dimensional, 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.
Address [Montalva-Medel, Marco; Goles, Eric] Univ Adolfo Ibanez, Ave Diagonal Torres 2640, Santiago, Chile, Email: marco.montalva@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:000441986000016 Approved
Call Number UAI @ eduardo.moreno @ Serial 908
Permanent link to this record
 

 
Author Montalva-Medel, M.; Ledger, T.; Ruz, G.A.; Goles, E.
Title Lac Operon Boolean Models: Dynamical Robustness and Alternative Improvements Type
Year 2021 Publication Mathematics Abbreviated Journal Mathematics
Volume 9 Issue 6 Pages 600
Keywords ELEMENTARY CELLULAR-AUTOMATA; CARBON CATABOLITE REPRESSION; GLUCOSE-LACTOSE DIAUXIE; ESCHERICHIA-COLI; BLOCK INVARIANCE; MAXIMUM SENSITIVITY; BETA-GALACTOSIDASE; BISTABLE BEHAVIOR; BISTABILITY; NETWORK
Abstract In Veliz-Cuba and Stigler 2011, Boolean models were proposed for the lac operon in Escherichia coli capable of reproducing the operon being OFF, ON and bistable for three (low, medium and high) and two (low and high) parameters, representing the concentration ranges of lactose and glucose, respectively. Of these 6 possible combinations of parameters, 5 produce results that match with the biological experiments of Ozbudak et al., 2004. In the remaining one, the models predict the operon being OFF while biological experiments show a bistable behavior. In this paper, we first explore the robustness of two such models in the sense of how much its attractors change against any deterministic update schedule. We prove mathematically that, in cases where there is no bistability, all the dynamics in both models lack limit cycles while, when bistability appears, one model presents 30% of its dynamics with limit cycles while the other only 23%. Secondly, we propose two alternative improvements consisting of biologically supported modifications; one in which both models match with Ozbudak et al., 2004 in all 6 combinations of parameters and, the other one, where we increase the number of parameters to 9, matching in all these cases with the biological experiments of Ozbudak et al., 2004.
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 ISBN Medium
Area Expedition Conference
Notes WOS:000645324300001 Approved
Call Number UAI @ alexi.delcanto @ Serial 1374
Permanent link to this record
 

 
Author Montalva-Medel, M.; Rica, S.; Urbina, F.
Title Phase space classification of an Ising cellular automaton: The Q2R model Type
Year 2020 Publication Chaos Solitons & Fractals Abbreviated Journal Chaos Solitons Fractals
Volume 133 Issue Pages 14 pp
Keywords
Abstract An exact classification of the different dynamical behaviors that exhibits the phase space of a reversible and conservative cellular automaton, the so-called Q2R model, is shown in this paper. Q2R is a cellular automaton which is a dynamical variation of the Ising model in statistical physics and whose space of configurations grows exponentially with the system size. As a consequence of the intrinsic reversibility of the model, the phase space is composed only by configurations that belong to a fixed point or a cycle. In this work, we classify them in four types accordingly to well differentiated topological characteristics. Three of them -which we call of type S-I, S-II, and S-III- share a symmetry property, while the fourth, which we call of type AS does not. Specifically, we prove that any configuration of Q2R belongs to one of the four previous types of cycles. Moreover, at a combinatorial level, we can determine the number of cycles for some small periods which are almost always present in the Q2R. Finally, we provide a general overview of the resulting decomposition of the arbitrary size Q2R phase space and, in addition, we realize an exhaustive study of a small Ising system (4 x 4) which is thoroughly analyzed under this new framework, and where simple mathematical tools are introduced in order to have a more direct understanding of the Q2R dynamics and to rediscover known properties like the energy conservation. (C) 2020 Elsevier Ltd. All rights reserved.
Address [Montalva-Medel, Marco; Rica, Sergio] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Avda Diagonal Torres 2640, Santiago, Chile
Corporate Author Thesis
Publisher Pergamon-Elsevier Science Ltd Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0960-0779 ISBN Medium
Area Expedition Conference
Notes WOS:000520892300040 Approved
Call Number UAI @ eduardo.moreno @ Serial 1130
Permanent link to this record
 

 
Author Perrot, K.; Montalva-Medel, M.; de Oliveira, P.P.B.; Ruivo, E.L.P.
Title Maximum sensitivity to update schedules of elementary cellular automata over periodic configurations Type
Year 2020 Publication Natural Computing Abbreviated Journal Nat. Comput.
Volume 19 Issue 1 Pages 51-90
Keywords Synchronism sensitivity; Elementary cellular automata; Update digraph
Abstract This work is a thoughtful extension of the ideas sketched in Montalva et al. (AUTOMATA 2017 exploratory papers proceedings, 2017), aiming at classifying elementary cellular automata (ECA) according to their maximal one-step sensitivity to changes in the schedule of cells update. It provides a complete classification of the ECA rule space for all period sizes n[ 9 and, together with the classification for all period sizes n <= 9 presented in Montalva et al. (Chaos Solitons Fractals 113:209-220, 2018), closes this problem and opens further questionings. Most of the 256 ECA rule's sensitivity is proved or disproved to be maximum thanks to an automatic application of basic methods. We formalize meticulous case disjunctions that lead to the results, and patch failing cases for some rules with simple arguments. This gives new insights on the dynamics of ECA rules depending on the proof method employed, as for the last rules 45 and 105 requiring o0011THORN induction patterns.
Address [Perrot, Kevin] Univ, Aix Marseille Univ.,Toulon,CNRS,UMR 7020, Marseille, France, Email: kevin.perrot@lis-lab.fr
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:000517129300006 Approved
Call Number UAI @ eduardo.moreno @ Serial 1162
Permanent link to this record
 

 
Author Ruivo, E.L.P.; de Oliveira, P.P.B.; Montalva-Medel, M.; Perrot, K.
Title Maximum sensitivity to update schedules of elementary cellular automata over infinite configurations Type
Year 2020 Publication Information and Computation Abbreviated Journal Inf. Comput.
Volume 274 Issue SI Pages 104538
Keywords
Abstract Cellular automata are discrete dynamical systems with locally defined behaviour, well known as simple models of complex systems. Classically, their dynamics derive from synchronously iterated rules over finite or infinite configurations; however, since for many natural systems to be modelled, asynchrony seems more plausible, asynchronous iteration of the rules has gained a considerable attention in recent years. One question in this context is how changing the update schedule of rule applications affects the global behaviour of the system. In particular, previous works addressed the notion of maximum sensitivity to changes in the update schemes for finite lattices. Here, we extend the notion to infinite lattices, and classify elementary cellular automata space according to such a property.
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 Expedition Conference
Notes Approved
Call Number UAI @ eduardo.moreno @ Serial 1122
Permanent link to this record
 

 
Author Ruivo, E.L.P.; Montalva-Medel, M.; de Oliveira, P.P.B.; Perrot, K.
Title Characterisation of the elementary cellular automata in terms of their maximum sensitivity to all possible asynchronous updates Type
Year 2018 Publication Chaos Solitons & Fractals Abbreviated Journal Chaos Solitons Fractals
Volume 113 Issue Pages 209-220
Keywords Cellular automaton; Asynchronous update; Update digraph; Discrete dynamics; One-step maximum sensitivity
Abstract Cellular automata are fully-discrete dynamical systems with global behaviour depending upon their locally specified state transitions. They have been extensively studied as models of complex systems as well as objects of mathematical and computational interest. Classically, the local rule of a cellular automaton is iterated synchronously over the entire configuration. However, the question of how asynchronous updates change the behaviour of a cellular automaton has become a major issue in recent years. Here, we analyse the elementary cellular automata rule space in terms of how many different one-step trajectories a rule would entail when taking into account all possible deterministic ways of updating the rule, for one time step, over all possible initial configurations. More precisely, we provide a characterisation of the elementary cellular automata, by means of their one-step maximum sensitivity to all possible update schedules, that is, the property that any change in the update schedule causes the rule's one-step trajectories also to change after one iteration. Although the one-step maximum sensitivity does not imply that the remainder of the time-evolutions will be distinct, it is a necessary condition for that. (C) 2018 Elsevier Ltd. All rights reserved.
Address [Ruivo, Eurico L. P.; de Oliveira, Pedro P. B.] Univ Presbiteriana Mackenzie, Fac Comp & Informat, Sao Paulo, SP, Brazil, Email: eurico.ruivo@mackenzie.br
Corporate Author Thesis
Publisher Pergamon-Elsevier Science Ltd Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0960-0779 ISBN Medium
Area Expedition Conference
Notes WOS:000442101600024 Approved
Call Number UAI @ eduardo.moreno @ Serial 910
Permanent link to this record