toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
Details
   print
  Records Links
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 (up) 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 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 (up) 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 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 (up) 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
Select All    Deselect All
 |   | 
Details
   print

Save Citations:
Export Records: