| |
Records |
Links |
|
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 |
Montalva-Medel, M.; de Oliveira, P.P.B.; Goles, E. |
|
| |
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. |
|
| |
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 |
| |
|
| |
|
Author |
Ruivo, E.L.P.; de Oliveira, P.P.B.; Lobos, F.; Goles, E. |
|
| |
Title |
Shift-equivalence of k-ary, one-dimensional 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 |
280-291 |
|
| |
Keywords |
One-dimensional cellular automata; Dynamical behaviour; Dynamical equivalence; Shift equivalence |
|
| |
Abstract |
Cellular automata are locally-defined, 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 time-evolution, 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 shift-equivalence 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 shift-equivalent 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 k-ary, one-dimensional 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, BR-01302907 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 |
1007-5704 |
ISBN |
|
Medium |
|
|
| |
Area |
|
Expedition |
|
Conference |
|
|
| |
Notes |
WOS:000432822500022 |
Approved |
|
|
| |
Call Number |
UAI @ eduardo.moreno @ |
Serial |
870 |
|
| Permanent link to this record |
| |
|
| |
|
Author |
Ruivo, E.L.P.; de Oliveira, P.P.B.; Montalva-Medel, M.; Perrot, K. |
|
| |
Title |
Maximum sensitivity to update schedules of elementary cellular automata over infinite configurations |
Type |
|
| |
Year |
2020 |
Publication |
Information and Computation |
Abbreviated Journal |
Inf. Comput. |
|
| |
Volume |
274 |
Issue |
SI |
Pages |
104538 |
|
| |
Keywords |
|
|
| |
Abstract |
Cellular automata are discrete dynamical systems with locally defined behaviour, well known as simple models of complex systems. Classically, their dynamics derive from synchronously iterated rules over finite or infinite configurations; however, since for many natural systems to be modelled, asynchrony seems more plausible, asynchronous iteration of the rules has gained a considerable attention in recent years. One question in this context is how changing the update schedule of rule applications affects the global behaviour of the system. In particular, previous works addressed the notion of maximum sensitivity to changes in the update schemes for finite lattices. Here, we extend the notion to infinite lattices, and classify elementary cellular automata space according to such a property. |
|
| |
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 |
1122 |
|
| Permanent link to this record |
| |
|
| |
|
Author |
Ruivo, E.L.P.; Montalva-Medel, M.; de Oliveira, P.P.B.; Perrot, K. |
|
| |
Title |
Characterisation of the elementary cellular automata in terms of their maximum sensitivity to all possible asynchronous updates |
Type |
|
| |
Year |
2018 |
Publication |
Chaos Solitons & Fractals |
Abbreviated Journal |
Chaos Solitons Fractals |
|
| |
Volume |
113 |
Issue |
|
Pages |
209-220 |
|
| |
Keywords |
Cellular automaton; Asynchronous update; Update digraph; Discrete dynamics; One-step maximum sensitivity |
|
| |
Abstract |
Cellular automata are fully-discrete dynamical systems with global behaviour depending upon their locally specified state transitions. They have been extensively studied as models of complex systems as well as objects of mathematical and computational interest. Classically, the local rule of a cellular automaton is iterated synchronously over the entire configuration. However, the question of how asynchronous updates change the behaviour of a cellular automaton has become a major issue in recent years. Here, we analyse the elementary cellular automata rule space in terms of how many different one-step trajectories a rule would entail when taking into account all possible deterministic ways of updating the rule, for one time step, over all possible initial configurations. More precisely, we provide a characterisation of the elementary cellular automata, by means of their one-step maximum sensitivity to all possible update schedules, that is, the property that any change in the update schedule causes the rule's one-step trajectories also to change after one iteration. Although the one-step maximum sensitivity does not imply that the remainder of the time-evolutions will be distinct, it is a necessary condition for that. (C) 2018 Elsevier Ltd. All rights reserved. |
|
| |
Address |
[Ruivo, Eurico L. P.; de Oliveira, Pedro P. B.] Univ Presbiteriana Mackenzie, Fac Comp & Informat, Sao Paulo, SP, Brazil, Email: eurico.ruivo@mackenzie.br |
|
| |
Corporate Author |
|
Thesis |
|
|
| |
Publisher |
Pergamon-Elsevier Science Ltd |
Place of Publication |
|
Editor |
|
|
| |
Language |
English |
Summary Language |
|
Original Title |
|
|
| |
Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
|
| |
Series Volume |
|
Series Issue |
|
Edition |
|
|
| |
ISSN |
0960-0779 |
ISBN |
|
Medium |
|
|
| |
Area |
|
Expedition |
|
Conference |
|
|
| |
Notes |
WOS:000442101600024 |
Approved |
|
|
| |
Call Number |
UAI @ eduardo.moreno @ |
Serial |
910 |
|
| Permanent link to this record |
