toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
Details
   print
  Records Links
Author Adamatzky, A.; Goles, E.; Martinez, GJ.; Tsompanas, MA.; Tegelaar, M.; Wosten, HAB. doi  openurl
  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 Concha-Vega, P.; Goles, E.; Montealegre, P.; Rios-Wilson, M.; Santivanez, J. doi  openurl
  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 Gajardo, A.; Goles, E. pdf  doi
openurl 
  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 Goles, E.; Montealegre, P. doi  openurl
  Title The complexity of the asynchronous prediction of the majority automata Type
  Year 2020 Publication Information and Computation Abbreviated Journal Inf. Comput.  
  Volume 274 Issue SI Pages  
  Keywords Majority automata; Cellular automata; Prediction problem; Asynchronous updating; Computational complexity; Parallel algorithms; Bootstrap percolation; NP-Completeness  
  Abstract We consider the asynchronous prediction problem for some automaton as the one consisting in determining, given an initial configuration, if there exists a non-zero 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 two-dimensional lattice with von Neumann neighborhood. Later, we show that in three or more dimensions the problem is NP-Complete.  
  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 1124  
Permanent link to this record
 

 
Author Goles, E.; Moreira, A. pdf  url
openurl 
  Title Number-Conserving Cellular Automata and Communication Complexity: A Numerical Exploration Beyond Elementary CAs Type
  Year 2012 Publication Journal Of Cellular Automata Abbreviated Journal J. Cell. Autom.  
  Volume 7 Issue 2 Pages 151-165  
  Keywords Number-Conserving; Communication Complexity; One-dimensional Cellular Automata  
  Abstract We perform a numerical exploration of number-conserving cellular automata (NCCA) beyond the class of elementary CAs, in search of examples with high communication complexity. We consider some possible generalizations of the elementary rule 184 (a minimal model of traffic, which is the only non-trivial elementary NCCA). as well as the classes of NCCAs which minimally extend either the radius or the state set (with respect to the 2 states and radius 1 of the elementary case). Both for 3 states and radius 1, and for 2 stales and radius 2, NCCA appear that are conjectured to have maximal (exponential) communication complexity. Examples are given also for (conjectured) linear and quadratic behaviour.  
  Address [Goles, Eric] Univ Adolfo Ibanez, Santiago, Chile, Email: andres.moreira@usm.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:000302978700004 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 210  
Permanent link to this record
 

 
Author Goles, E.; Palacios, A.G. pdf  doi
openurl 
  Title Dynamical complexity in cognitive neural networks Type
  Year 2007 Publication Biological Research Abbreviated Journal Biol. Res.  
  Volume 40 Issue 4 Pages 479-485  
  Keywords artificial; neural net; brain; dynamical complexity; computational Neurosciences; cellular automata  
  Abstract In the last twenty years an important effort in brain sciences, especially in cognitive science, has been the development of mathematical tool that can deal with the complexity of extensive recordings corresponding to the neuronal activity obtained from hundreds of neurons. We discuss here along with some historical issues, advantages and limitations of Artificial Neural Networks (ANN) that can help to understand how simple brain circuits work and whether ANN can be helpful to understand brain neural complexity.  
  Address [Goles, Eric] Univ Adolfo Ibanez, Fac Ciencias, Santiago, Chile, Email: eric.chacc@uai.cl  
  Corporate Author Thesis  
  Publisher Soc Biolgia Chile Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0716-9760 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000256072000009 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 33  
Permanent link to this record
 

 
Author Goles, E.; Guillon, P.; Rapaport, I. pdf  doi
openurl 
  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 Goles, E.; Lobos, F.; Montealegre, P.; Ruivo, ELP.; de Oliveira, PPB. openurl 
  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 Goles, E.; Maldonado, D.; Montealecre, P. doi  openurl
  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 Goles, E.; Maldonado, D.; Montealegre, P.; Ollinger, N. doi  openurl
  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
 

 
Author Goles, E.; Meunier, P.E.; Rapaport, I.; Theyssier, G. pdf  doi
openurl 
  Title Communication complexity and intrinsic universality in cellular automata Type
  Year 2011 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.  
  Volume 412 Issue 1-2 Pages 2-21  
  Keywords Cellular automata; Communication complexity; Intrinsic universality  
  Abstract The notions of universality and completeness are central in the theories of computation and computational complexity. However, proving lower bounds and necessary conditions remains hard in most cases. In this article, we introduce necessary conditions for a cellular automaton to be “universal”, according to a precise notion of simulation, related both to the dynamics of cellular automata and to their computational power. This notion of simulation relies on simple operations of space-time rescaling and it is intrinsic to the model of cellular automata. intrinsic universality, the derived notion, is stronger than Turing universality, but more uniform, and easier to define and study. Our approach builds upon the notion of communication complexity, which was primarily designed to study parallel programs, and thus is, as we show in this article, particulary well suited to the study of cellular automata: it allowed us to show, by studying natural problems on the dynamics of cellular automata, that several classes of cellular automata, as well as many natural (elementary) examples, were not intrinsically universal. (C) 2010 Elsevier B.V. All rights reserved.  
  Address [Meunier, P. -E.; Theyssier, G.] Univ Savoie, CNRS, LAMA, F-73376 Le Bourget Du Lac, France, Email: guillaume.theyssier@univ-savoie.fr  
  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:000285952400002 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 118  
Permanent link to this record
 

 
Author Goles, E.; Montalva-Medel, M.; MacLean, S.; Mortveit, H. url  openurl
  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. url  openurl
  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 Goles, E.; Montealegre, P.; Perrot, K.; Theyssier, G. pdf  doi
openurl 
  Title On the complexity of two-dimensional signed majority cellular automata Type
  Year 2018 Publication Journal Of Computer And System Sciences Abbreviated Journal J. Comput. Syst. Sci.  
  Volume 91 Issue Pages 1-32  
  Keywords Cellular automata dynamics; Majority cellular automata; Signed two-dimensional lattice; Turing universal; Intrinsic universal; Computational complexity  
  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 non-uniform symmetric rules are Turing universal and have a P-complete prediction problem; the non-uniform asymmetric rule is intrinsically universal; no symmetric rule can be intrinsically universal. We also show that the uniform asymmetric rules exhibit cycles of super-polynomial length, whereas symmetric ones are known to have bounded cycle length. (C) 2017 Elsevier Inc. All rights reserved.  
  Address [Goles, Eric; Montealegre, Pedro] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Santiago, Chile, Email: p.montealegre@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 0022-0000 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000413130200001 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 779  
Permanent link to this record
 

 
Author Goles, E.; Montealegre, P.; Vera, J. url  openurl
  Title Naming Game Automata Networks Type
  Year 2016 Publication Journal Of Cellular Automata Abbreviated Journal J. Cell. Autom.  
  Volume 11 Issue 5-6 Pages 497-521  
  Keywords Automata networks; cellular automata; majority functions; energy operator; naming game; fixed points; limit cycles  
  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.  
  Address [Goles, Eric; Vera, Javier] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Avda Diagonal Las Torres 2640, 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:000382426500007 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 649  
Permanent link to this record
 

 
Author Goles, E.; Moreira, A.; Rapaport, I. pdf  doi
openurl 
  Title Communication complexity in number-conserving and monotone cellular automata Type
  Year 2011 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.  
  Volume 412 Issue 29 Pages 3616-3628  
  Keywords Cellular automata; Communication complexity; Elementary cellular automata; Number-conserving  
  Abstract One third of the elementary cellular automata (CAs) are either number-conserving (NCCAs) or monotone (increasing or decreasing). In this paper we prove that, for all of them, we can find linear or constant communication protocols for the prediction problem. In other words, we are able to give a succinct description for their dynamics. This is not necessarily true for general NCCAs. In fact, we also show how to explicitly construct, from any CA, a new NCCA which preserves the original communication complexity. (C) 2011 Elsevier B.V. All rights reserved.  
  Address [Moreira, A] Univ Tecn Federico Santa Maria, Dept Informat, Valparaiso, 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:000292077200019 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 153  
Permanent link to this record
 

 
Author Lobos, F.; Goles, E.; Ruivo, E.L.P.; de Oliveira, P.P.B.; Montealegre, P. url  openurl
  Title Mining a Class of Decision Problems for One-dimensional Cellular Automata Type
  Year 2018 Publication Journal Of Cellular Automata Abbreviated Journal J. Cell. Autom.  
  Volume 13 Issue 5-6 Pages 393-405  
  Keywords One-dimensional cellular automata; decision problems; density classification; parity problem  
  Abstract Cellular automata are locally defined, homogeneous dynamical systems, discrete in space, time and state variables. Within the context of one-dimensional, 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 fixed-point 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.  
  Address [Lobos, Fabiola; Goles, Eric; Montealegre, Pedro] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Ave Diagonal Torres 2640, Santiago, Chile, Email: pp.balbi@gmail.com  
  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:000449762900002 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 931  
Permanent link to this record
 

 
Author MacLean, S.; Montalva-Medel, M.; Goles, E. doi  openurl
  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. pdf  doi
openurl 
  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 Perrot, K.; Montalva-Medel, M.; de Oliveira, P.P.B.; Ruivo, E.L.P. doi  openurl
  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
Select All    Deselect All
 |   | 
Details
   print

Save Citations:
Export Records: