| Records |
| 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.; Lobos, F.; Ruz, G.A.; Sene, S. |
| Title |
Attractor landscapes in Boolean networks with firing memory: a theoretical study applied to genetic networks |
Type |
|
| Year |
2020 |
Publication |
Natural Computing |
Abbreviated Journal |
Nat. Comput. |
| Volume |
19 |
Issue |
2 |
Pages |
295-319 |
| Keywords |
Discrete dynamical systems; Boolean networks; Biological network modeling |
| Abstract |
In this paper we study the dynamical behavior of Boolean networks with firing memory, namely Boolean networks whose vertices are updated synchronously depending on their proper Boolean local transition functions so that each vertex remains at its firing state a finite number of steps. We prove in particular that these networks have the same computational power than the classical ones, i.e. any Boolean network with firing memory composed of m vertices can be simulated by a Boolean network by adding vertices. We also prove general results on specific classes of networks. For instance, we show that the existence of at least one delay greater than 1 in disjunctive networks makes such networks have only fixed points as attractors. Moreover, for arbitrary networks composed of two vertices, we characterize the delay phase space, i.e. the delay values such that networks admits limit cycles or fixed points. Finally, we analyze two classical biological models by introducing delays: the model of the immune control of the lambda\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda $$\end{document}-phage and that of the genetic control of the floral morphogenesis of the plant Arabidopsis thaliana. |
| Address |
[Goles, Eric; Lobos, Fabiola; Ruz, Gonzalo A.] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Santiago, Chile, Email: eric.chacc@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:000531210800001 |
Approved |
|
| Call Number |
UAI @ eduardo.moreno @ |
Serial |
1139 |
| 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 |
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 |
