Home << 1 >>
List View
 | 
Citations
 | 
Details
   web
Records
Author (up) Goles, E.; Montalva-Medel, M.; Montealegre, P.; Rios-Wilson, M.
Title On the complexity of generalized Q2R automaton Type
Year 2022 Publication Advances In Applied Mathematics Abbreviated Journal Adv. Appl. Math.
Volume 138 Issue Pages 102355
Keywords Q2R networks; Computational complexity; Limit cycles; P-complete
Abstract We study the dynamic and complexity of the generalized Q2R automaton. We show the existence of non-polynomial cycles as well as its capability to simulate with the synchronous update the classical version of the automaton updated under a block sequential update scheme. Furthermore, we show that the decision problem consisting in determine if a given node in the network changes its state is P-Hard.
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 0196-8858 ISBN Medium
Area Expedition Conference
Notes WOS:000830087300008 Approved
Call Number UAI @ alexi.delcanto @ Serial 1610
Permanent link to this record
 
 
Author (up) Goles, E.; Montealegre, P.
Title The complexity of the majority rule on planar graphs Type
Year 2015 Publication Advances In Applied Mathematics Abbreviated Journal Adv. Appl. Math.
Volume 64 Issue Pages 111-123
Keywords Automata networks; Computational complexity; Majority; P-Completeness; NC; Planar graph
Abstract We study the complexity of the majority rule on planar automata networks. We reduce a special case of the Monotone Circuit Value Problem to the prediction problem of determining if a vertex of a planar graph will change its state when the network is updated with the majority rule. (C) 2014 Elsevier Inc. All rights reserved.
Address [Goles, Eric] Univ Adolfo Ibanez, Fac Ciencias & Tecnol, 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 0196-8858 ISBN Medium
Area Expedition Conference
Notes WOS:000348883400007 Approved
Call Number UAI @ eduardo.moreno @ Serial 445
Permanent link to this record
 
 
Author (up) Goles, E.; Montealegre, P.; Perrot, K.
Title Freezing sandpiles and Boolean threshold networks: Equivalence and complexity Type
Year 2021 Publication Advances In Applied Mathematics Abbreviated Journal Adv. Appl. Math.
Volume 125 Issue Pages 102161
Keywords
Abstract The NC versus P-hard classification of the prediction problem for sandpiles on the two dimensional grid with von Neumann neighborhood is a famous open problem. In this paper we make two kinds of progresses, by studying its freezing variant. First, it enables to establish strong connections with other well known prediction problems on networks of threshold Boolean functions such as majority. Second, we can highlight some necessary and sufficient elements to the dynamical complexity of sandpiles, with a surprisingly crucial role of cells with two grains. (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 0196-8858 ISBN Medium
Area Expedition Conference
Notes WOS:000614706400006 Approved
Call Number UAI @ alexi.delcanto @ Serial 1340
Permanent link to this record
 
 
Author (up) Goles, E.; Noual, M.
Title Disjunctive networks and update schedules Type
Year 2012 Publication Advances In Applied Mathematics Abbreviated Journal Adv. Appl. Math.
Volume 48 Issue 5 Pages 646-662
Keywords Regulation network; Linear Boolean network; Attractor; Limit cycle; Fixed point; Update schedule
Abstract In this paper, we present a study of the dynamics of disjunctive networks under all block-sequential update schedules. We also present an extension of this study to more general fair periodic update schedules, that is, periodic update schedules that do not update some elements much more often than some others. Our main aim is to classify disjunctive networks according to the robustness of their dynamics with respect to changes of their update schedules. To study this robustness, we focus on one property, that of being able to cycle dynamically. (C) 2012 Elsevier Inc. All rights reserved.
Address [Noual, Mathilde] Univ Lyon, Lab Informat Parallelisme, ENS Lyon, CNRS UMR5668, F-69342 Lyon 07, France, Email: mathilde.noual@ens-lyon.fr
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:000304682200004 Approved
Call Number UAI @ eduardo.moreno @ Serial 217
Permanent link to this record
 
 
Author (up) Goles, E.; Salinas, L.
Title Sequential operator for filtering cycles in Boolean networks Type
Year 2010 Publication Advances In Applied Mathematics Abbreviated Journal Adv. Appl. Math.
Volume 45 Issue 3 Pages 346-358
Keywords
Abstract Given a Boolean network without negative circuits, we propose a polynomial algorithm to build another network such that, when updated in parallel, it has the same fixed points than the original one, but it does not have any dynamical cycle. To achieve that, we apply a network transformation related to the sequential update. As a corollary, we can find a fixed point in polynomial time for this kind of networks. (C) 2010 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 0196-8858 ISBN Medium
Area Expedition Conference
Notes WOS:000281294000004 Approved
Call Number UAI @ eduardo.moreno @ Serial 94
Permanent link to this record
 
 
Author (up) 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