| |
Records |
Links |
|
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 |
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.; 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 |
Lobos, F.; Goles, E.; Ruivo, E.L.P.; de Oliveira, P.P.B.; Montealegre, P. |
|
| |
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 |
Goles, E.; Montealegre, P.; Vera, J. |
|
| |
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.; 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 |
Goles, E.; Moreira, A. |
|
| |
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 |
