Records 
Author 
Goles, E.; Moreira, A. 
Title 
NumberConserving 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 
151165 
Keywords 
NumberConserving; Communication Complexity; Onedimensional Cellular Automata 
Abstract 
We perform a numerical exploration of numberconserving 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 nontrivial 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 
15575969 
ISBN 

Medium 

Area 

Expedition 

Conference 

Notes 
WOS:000302978700004 
Approved 

Call Number 
UAI @ eduardo.moreno @ 
Serial 
210 
Permanent link to this record 



Author 
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 
261304 
Keywords 
Onedimensional 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 
15575969 
ISBN 

Medium 

Area 

Expedition 

Conference 

Notes 
WOS:000613086900002 
Approved 

Call Number 
UAI @ alexi.delcanto @ 
Serial 
1329 
Permanent link to this record 



Author 
Lobos, F.; Goles, E.; Ruivo, E.L.P.; de Oliveira, P.P.B.; Montealegre, P. 
Title 
Mining a Class of Decision Problems for Onedimensional Cellular Automata 
Type 

Year 
2018 
Publication 
Journal Of Cellular Automata 
Abbreviated Journal 
J. Cell. Autom. 
Volume 
13 
Issue 
56 
Pages 
393405 
Keywords 
Onedimensional 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 onedimensional, 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 fixedpoint 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 
15575969 
ISBN 

Medium 

Area 

Expedition 

Conference 

Notes 
WOS:000449762900002 
Approved 

Call Number 
UAI @ eduardo.moreno @ 
Serial 
931 
Permanent link to this record 



Author 
MontalvaMedel, M.; de Oliveira, P.P.B.; Goles, E. 
Title 
A portfolio of classification problems by onedimensional cellular automata, over cyclic binary configurations and parallel update 
Type 

Year 
2018 
Publication 
Natural Computing 
Abbreviated Journal 
Nat. Comput. 
Volume 
17 
Issue 
3 
Pages 
663671 
Keywords 
Onedimensional 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 (twoway) 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 onedimensional, 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 
[MontalvaMedel, 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 
15677818 
ISBN 

Medium 

Area 

Expedition 

Conference 

Notes 
WOS:000441986000016 
Approved 

Call Number 
UAI @ eduardo.moreno @ 
Serial 
908 
Permanent link to this record 



Author 
Ruivo, E.L.P.; de Oliveira, P.P.B.; Lobos, F.; Goles, E. 
Title 
Shiftequivalence of kary, onedimensional cellular automata rules 
Type 

Year 
2018 
Publication 
Communications In Nonlinear Science And Numerical Simulation 
Abbreviated Journal 
Commun. Nonlinear Sci. Numer. Simul. 
Volume 
63 
Issue 

Pages 
280291 
Keywords 
Onedimensional cellular automata; Dynamical behaviour; Dynamical equivalence; Shift equivalence 
Abstract 
Cellular automata are locallydefined, synchronous, homogeneous, fully discrete dynamical systems. In spite of their typically simple local behaviour, many are capable of showing complex emergent behaviour. When looking at their timeevolution, one may be interested in studying their qualitative dynamical behaviour. One way to group rules that display the same qualitative behaviour is by defining symmetries that map rules to others, the simplest way being by means of permutations in the set of state variables and reflections in their neighbourhood definitions, therefore defining equivalence classes. Here, we introduce the notion of shiftequivalence as another kind of symmetry, now relative to the concept of translation. After defining the notion and showing it indeed defines an equivalence relation, we extend the usual characterisation of dynamical equivalence and use it to partition some specific binary cellular automata rule spaces. Finally, we give a characterisation of the class of shiftequivalent rules in terms of the local transition functions of the cellular automata in the class, by providing an algorithm to compute the members of the class, for any kary, onedimensional rule. (C) 2018 Elsevier B.V. All rights reserved. 
Address 
[Ruivo, Eurico L. P.; de Oliveira, Pedro P. B.] Univ Presbiteriana Mackenzie, Fac Comp & Informat, Rua Consolacao 896, BR01302907 Sao Paulo, SP, Brazil, Email: eurico.ruivo@mackenzie.br 
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 
10075704 
ISBN 

Medium 

Area 

Expedition 

Conference 

Notes 
WOS:000432822500022 
Approved 

Call Number 
UAI @ eduardo.moreno @ 
Serial 
870 
Permanent link to this record 