Papers, chapters, and beyond

Papers, chapters, and beyond

All papers are available in PDF format.

Title: Research Frontier in Chaos Theory and Complex Networks

Journal: Entropy 20(10), 734, 2018. [PDF soon]

Authors: Guanrong Chen, Marius-F. Danca, Xiaosong Yang, Genaro J. Martínez, Hai Yu

URL: https://www.mdpi.com/1099-4300/20/10/734

Abstract: In recent years, as natural and social sciences are rapidly evolving, classical chaos theory and modern complex networks studies are gradually interacting each other with a great joined development. In particular, the notion of complex networks is becoming a self-contained interdiscipline. Network science as a whole has merged with the basic research and real-world applications of chaos theory, forming one of the most active fields in cognitive science, data science, cloud computing, social sciences, artificial intelligence, and the like. The theme of this special Issue is on the current research efforts and progress in the promising field of chaos theory as well as complex networks. It comprises 17 selected manuscripts primarily involving four types of subjects, namely theoretical and characteristic analysis of chaotic dynamics, control systems and synchronization, complex networks, and chaos-based applications.

Title: Conservative Computing in a One-dimensional Cellular Automaton with Memory

Journal: Journal of Cellular Automata 13(4), 325-346, 2018. [PDF]

Authors: Genaro J. Martínez, Kenichi Morita

Abstract: We propose a scheme to simulate Fredkin gates in a one-dimensional cellular automaton with memory by collision of particles, which is a moving pattern in this cellular space. Operations by collisions are confined in a black box with ballistic interaction, solitons and other collisions. We made a systematic analysis of binary collisions, i.e., collisions of two particles with different phases. They are used for handling these particles and obtaining the final outputs.

Title: Recognizing complex behavior emerging from chaos in cellular automata

Book: Unifying Themes in Complex Systems IX. In: Morales, A., Gershenson, C., Braha, D., Minai, A., Bar-Yam, Y. (eds.). Springer Proceedings in Complexity, pp. 82-90, 2018. [PDF]

Authors: Gabriela M. González, Genaro J. Martínez, M.A. Aziz Alaoui, Fangyue Chen

URL: https://link.springer.com/chapter/10.1007/978-3-319-96661-8_8

Abstract: In this research, we explain and show how a chaotic system displays non-trivial behavior as a complex system. This result is reached modifying the chaotic system using a memory function, which leads to a new system with elements of the original function which are not evident in a first step. We proof that this phenomenology can be apprehended selecting a typical chaotic function in the domain of elementary cellular automata to discover complex dynamics. By numerical simulations, we demonstrate how a number of gliders emerge in this automaton and how some controlled subsystems can be designed within this complex system.

Title: Logical Gates via Gliders Collisions

Book: Reversibility and Universality: Essays Presented to Kenichi Morita on the Occasion of his 70th Birthday, Springer, (A. Adamatzky Ed.), chapter 9, pages 199-220, 2018. [PDF]

Authors: Genaro J. Martínez, Andrew Adamatzky, Kenichi Morita

URL: https://link.springer.com/chapter/10.1007%2F978-3-319-73216-9_9

Abstract: An elementary cellular automaton with memory is a chain of finite state machines (cells) updating their state simultaneously and by the same rule. Each cell updates its current state depending on current states of its immediate neighbours and a certain number of its own past states. Some cell-state transition rules support gliders, compact patterns of non-quiescent states translating along the chain. We present designs of logical gates, including reversible Fredkin gate and controlled NOT gate, implemented via collisions between gliders.

Title: Simple networks on complex cellular automata: From de Bruijn diagrams to jump-graphs

Book: Swarm Dynamics as a Complex Network, Springer, (I. Zelinka and G. Chen Eds.), chapter 12, pages 241-264, 2018. [PDF]

Authors: Genaro J. Martínez, Andrew Adamatzky, Bo Chen, Fangyue Chen, Juan C.S.T. Mora

URL: https://link.springer.com/chapter/10.1007/978-3-662-55663-4_12

Abstract: We overview networks which characterise dynamics in cellular automata. These networks are derived from one-dimensional cellular automaton rules and global states of the automaton evolution: de Bruijn diagrams, subsystem diagrams, basins of attraction, and jump-graphs. These networks are used to understand properties of spatially-extended dynamical systems: emergence of non-trivial patterns, self-organisation, reversibility and chaos. Particular attention is paid to networks determined by travelling self-localisations, or gliders.

Title: Meet the Editors: Genaro J. Martínez

Journal: Journal of Cellular Automata 13(1), 179-180, 2017. [PDF]

Authors: Genaro J. Martínez

URL: http://www.oldcitypublishing.com/journals/jca-home/jca-issue-contents/jca-volume-13-number-1-2-2018/

Title: Glider Collisions in Hybrid Cellular Automaton with Memory Rule (43,74)

Journal: International Journal of Bifurcation and Chaos 27(6), 1750082-32, 2017. [PDF soon]

Authors: Bo Chen, Fangyue Chen, Genaro J. Martínez

URL: http://www.worldscientific.com/doi/abs/10.1142/S0218127417500821

Abstract: In the case of one-dimensional cellular automata (CA), a hybrid CA (HCA) is the member whose evolution of the cells is dependent on non-unique global functions. The HCAs exhibit a wide range of traveling and stationary localisations in their evolution. We focus on HCA with memory (HCAM) because they produce a host of gliders and complicated glider collisions by introducing the hybrid mechanism. In particular, we undertake an exhaustive search of gliders and describe their collisions using quantitative approach in HCAM(43,74). By introducing the symbol vector space and exploiting the mathematical definition of HCAM, we present an analytical method of complex asymptotic dynamics of the gliders.

Title: East-West paths to unconventional computing

Journal: Progress in Biophysics and Molecular Biology 131, 469-493, 2017. [PDF soon]

Authors: Andrew Adamatzky, Selim Akl, Mark Burgin, Cristian S. Calude, José Félix Costa, Mohammad Mahdi Dehshibi, Yukio-Pegio Gunji, Zoran Konkoli, Bruce MacLennan, Bruno Marchal, Maurice Margenstern, Genaro J. Martínez, Richard Mayne, Kenichi Morita, Andrew Schumann, Yaroslav D. Sergeyev, Georgios Ch. Sirakoulis, Susan Stepney, Karl Svozil, Hector Zenil

URL: http://www.sciencedirect.com/science/article/pii/S0079610717301177

Abstract: Unconventional computing is about breaking boundaries in thinking, acting and computing. Typical topics of this non-typical field include, but are not limited to physics of computation, non-classical logics, new complexity measures, novel hardware, mechanical, chemical and quantum computing. Unconventional computing encourages a new style of thinking while practical applications are obtained from uncovering and exploiting principles and mechanisms of information processing in and functional properties of, physical, chemical and living systems; in particular, efficient algorithms are developed, (almost) optimal architectures are designed and working prototypes of future computing devices are manufactured. This article includes idiosyncratic accounts of ‘unconventional computing’ scientists reflecting on their personal experiences, what attracted them to the field, their inspirations and discoveries.

Title: A Computation in a Cellular Automaton Collider Rule 110

Book: Advances in Unconventional Computing: Volume I Theory, Springer, (A. Adamatzky, Ed.), chapter 15, pages 391-428, 2017. [PDF]

Authors: Genaro J. Martínez, Andrew Adamatzky, Harold V. McIntosh

Videos: https://www.youtube.com/watch?v=i5af0tQiVd4, https://www.youtube.com/watch?v=kciEa6cF1QQ&t=30s, https://www.youtube.com/watch?v=HFJlbz7qATg, https://www.youtube.com/watch?v=JElxQt32Odc&t=6s

Abstract: A cellular automaton collider is a finite state machine build of rings of one-dimensional cellular automata. We show how a computation can be performed on the collider by exploiting interactions between gliders (particles, localisations). The constructions proposed are based on universality of elementary cellular automaton rule 110, cyclic tag systems, supercolliders, and computing on rings.

Title: 1/f Noise in the Computation Process by Rule 110

Journal: Journal of Cellular Automata 12(1-2), 47-61, 2017. [PDF soon]

Authors: Shigeru Ninagawa, Genaro J. Martínez

Abstract: An elementary cellular automaton rule 110 supports universal computation by emulating cyclic tag system and its evolution starting from random initial configuration exhibits 1/f noise. In this research we investigate the power spectra of the computation process of rule 110 emulating cyclic tag system. As a result, 1/f-type power spectra are observed in the most actively interacting area among the whole array, while in the less active area the power spectra exhibit Lorentzian, Brownian or periodic types. These results suggest a possibility that the dynamics ac- companied with 1/f noise and the one capable of performing computation overlap each other in cellular automaton rule space.

Title: On plant roots logical gates

Journal: Information Sciences 382(383), 81-95, 2017. [PDF]

Authors: Andrew Adamatzky, Georgios Ch. Sirakoulis, Genaro J. Martínez, Frantisek Baluska, Stefano Mancuso

URL: http://www.sciencedirect.com/science/article/pii/S0303264716302374

Abstract: Theoretical constructs of logical gates implemented with plant roots are morphological computing asynchronous devices. Values of Boolean variables are represented by plant roots. A presence of a plant root at a given site symbolises the logical True, an absence the logical False. Logical functions are calculated via interaction between roots. Two types of two-inputs–two-outputs gates are proposed: a gate ⟨x,y⟩ → ⟨xy,x+y⟩ where root apexes are guided by gravity and a gate ⟨x,y⟩ → ⟨~xy,x⟩ where root apexes are guided by humidity. We propose a design of binary half-adder based on the gates.

Title: Welch sets for random generation and representation of reversible one-dimensional cellular automata

Journal: Information Sciences 382(383), 81-95, 2017. [PDF soon]

Authors: Juan C.S.T. Mora, Joselito M. Marina, Norberto H. Romero, Genaro J. Martínez, Irving B. Vite

URL: http://www.sciencedirect.com/science/article/pii/S0020025516319193

Abstract: Reversible one-dimensional cellular automata are studied from the perspective of Welch Sets. This paper presents an algorithm to generate random Welch sets that define a reversible cellular automaton. Then, properties of Welch sets are used in order to establish two bipartite graphs describing the evolution rule of reversible cellular automata. The first graph gives an alternative representation for the dynamics of these systems as block mappings and shifts. The second graph offers a compact representation for the evolution rule of reversible cellular automata. Both graphs and their matrix representations are illustrated by the generation of random reversible cellular automata with 6 and 18 states.

Title: Block Transformation of Hybrid Cellular Automata

Journal: Journal of Applied Analysis and Computation 6(4), 1164-1179, 2016. [PDF]

Authors: Bo Chen, Fangyue Chen, Junbiao Guan, Genaro J. Martínez

URL: http://jaac.ijournal.cn/ch/reader/view_abstract.aspx?file_no=JAAC-6-4-fangyuechen

Abstract: By introducing a sequence-block transformation and vector-block transformation, we explore the dynamical properties of hybrid cellular automation (HCA) and hybrid cellular automation with memory (HCAM) in the framework of symbolic dynamics. As the local evolution rules of HCA and HCAM are not-uniform, the new uniform cellular automata (CAs) with multiple states are constructed by specific the block transformations. Furthermore, because the new CA rules are topologically conjugate with the originals, the complex dynamics of the HCA and HCAM rules can be investigated via the new CA rules.

Title: Gliders in One-Dimensional Cellular Automata

Book: Designing Beauty: The Art of Cellular Automata, Springer, (A. Adamatzky, G. Martínez, Eds.), chapter 29, pages 167-172, 2016. [PDF soon]

Author: Genaro J. Martínez

URL: http://link.springer.com/chapter/10.1007/978-3-319-27270-2_29

Abstract: Gliders are non-trivial complex patterns emerging typically in complex cellular automata (CA). The most famous glider (mobile self-localizations, particles, waves) is the five-live cells glider moving diagonally in five steps in the two-dimensional CA Conway’s Game of Life. Pictures shown here are space-time configurations of elementary CA rule 110. Rule 110 CA is universal because it simulates a cyclic tag system. The cyclic tag system if programmed into an initial configuration of CA. The processing of just four values on the tape of this machine requires over three millions of cells.

Title: A Symbolic Dynamics Perspective of The Game of Three-Dimensional Life

Journal: Complex Systems 25(1), 51-77, 2016. [PDF]

Authors: Bo Chen, Fangyue Chen, Genaro J. Martínez, Danli Tong

URL: http://www.complex-systems.com/abstracts/v25_i01_a04.html

Abstract: The games of three-dimensional life are the extension models of Con- way’s game of life. Under the framework of symbolic dynamics, we undertake an analysis of the complexity of gliders in three-dimensional life rules by the directed graph representation and transition matrix. More specifically, the gliders here are topologically mixing and possess the positive topological entropy on their concrete subsystems. Finally, the method presented in this paper is also applicable to other gliders in different D-dimensions.

Title: A Symbolic Dynamics Perspective of Rock-Paper-Scissor Game

Journal: Journal of Nonlinear Systems and Applications 5(1), 35-46, 2016. [PDF]

Authors: Danli Tong, Bo Chen, Fangyue Chen, Genaro J. Martínez

URL: http://jnsaonline.watsci.org/contents2016/v5n1.html

Abstract: The Rock-Paper-Scissor (RPS) games are investigated under the framework of symbolic dynamics. It is of interest that several Chua’s nonlinear dynamics analytical methods are appropriate for the RPS game rule. And a series of dynamical properties on the its subsystems are explored by the directed graph and transition matrix. Moreover, the method presented in this paper is also applicable to other game rules.

Title: Obituary: Prof. Harold V. McIntosh

Journal: Journal of Cellular Automata 11(2-2), 265-269, 2016. [PDF]

Author: Genaro J. Martínez

Abstract: Professor Harold V. McIntosh was a prominent researcher who dedicated his life to Science. He was a big promoter of educating young students in several scientific fields simultaneously, such as physics, history, mathematics, biology, chemistry, and computer science. McIntosh was born in Colorado, USA in 1929 and died last November in Puebla, Mexico. McIntosh's legacy in different scientific fields is an example of dedication, passion and principles, in order to investigate problems from the easiest perspective, with didactic and visual interpretations, to establish later a formal solution. He was a great mentor and inspiration for many generations of students and researchers, and will be always remembered and honoured as a brilliant scientist and an exceptional person.

Title: Recolonisation of USA: Slime Mould on 3D Terrains

Book: Advances in Physarum Machines: Sensing and Computing with Slime Mould, Springer, (A. Adamatzky, Ed.), chapter 16, pages 337-348, 2016. [PDF soon]

Authors: Andrew Adamatzky, Genaro J. Martínez

URL: http://www.springer.com/kr/book/9783319266619

Abstract: P. polycephalum imitates development of man-made transport networks of a country when configuration of nutrients represents major urban areas. We employ this feature of the slime mould to imitate Mexican migration to USA, which is the Worlds’s largest migration system. In laboratory experiments with 3D Nylon terrains of USA we analyse development of migratory routes from Mexico-USA border to ten urban areas with high concentration of Mexican migrants. From results of laboratory experiments we extract topologies of migratory routes, and highlight a role of elevations in shaping the human movement networks.

Title: Describing Complex Dynamics in Life-Like Rules with de Bruijn Diagrams on Complex and Chaotic Cellular Automata

Journal: Journal of Cellular Automata 11(1), 91-112, 2016. [PDF soon]

Author: Paulina A. León, Genaro J. Martínez

Abstract: De Bruijn diagrams are useful tools for a systematic analysis of one-dimensional cellular automata (CA), i.e. calculating particular kinds of configurations, ancestors, complex patterns, cycles, Garden of Eden configurations, and formal languages. The de Brujin diagrams are barely employed in two-dimensions because complexity of their calculation increases exponentially.We apply de Bruijn diagrams for analysis of two evolution rules in two dimensions: the Conway’s Game of Life and the quasi-chaotic Diffusion Rule.

Title: Computing with Virtual Cellular Automata Collider

Book: Proceedings of IEEE Technically Co-Sponsored Science and Information Conference, London, UK, pages 62-68, 2015. DOI: 10.1109/SAI.2015.7237127. [PDF]

Authors: Genaro J. Martínez, Andrew Adamatzky, Harold V. McIntosh

Abstract: We present computer models of nano-scale computing circuits based on propagation of localised excitations or defects in complexes of polymer chain rings. A cyclotron automata are sets of rings of one-dimensional array of finite states (cellular automata) which exhibits a wide range of travelling localisations (gliders). When information (e.g. values of logical variables) is encoded in the initial positions and velocity vectors of the gliders the cyclotron automata are becoming power abstract machines which execute high-performance computing. The computing is based on collisions between the mobile localisations. We present collisions that emulate basic types of interactions between localisations typical for spatially-extended non-linear media: fusion, particles, elastic collision, and soliton-like collision, all they implement basic computing primitives. Mobile localisations in complex one-dimensional cellular automata are compact sets of non-quiescent patterns translating along evolution space. These non-trivial patterns can be coded as binary strings (regular expressions) or symbols travelling along a one-dimensional ring, interacting with each other and changing their states, or symbolic values, as a result of interactions and computation.

Title: Majority Gates and Circular Computation in Slime Mould

Book: Proceedings of the European Conference on Artificial Life 2015, p. 18-24, York, UK, 2015. [PDF]

Authors: Genaro J. Martínez, Andrew Adamatzky, Richard Mayne, Fangyue Chen, Qinbin He

URL: https://www.cs.york.ac.uk/nature/ecal2015/paper-16.html

Abstract: Slime mould has been proven to be a fruitful living substrate for implementing a wide range of computing circuits from computational geometry to collision-based logical circuits to robot control. It is apparent, however, that constructing work-ing real-time universal processors from the slime mould is non-trivial task. We explore here similarities between development of slime mould protoplasmic tubes, transportation of cytoplasm inside the tubes and dynamics of propagating patterns in cellular automata. Based on these analogies we will propose computing devices realisable in the living slime mould.

Title: On the Dynamics of Cellular Automata with Memory

Journal: Fundamenta Informaticae 137, 1-16, 2015. [PDF soon]

Authors: Genaro J. Martínez, Andrew Adamatzky, Ramon Alonso-Sanz

URL: http://content.iospress.com/articles/fundamenta-informaticae/fi138-1-2-02

Abstract: Elementary cellular automata (ECA) are linear arrays of finite-state machines (cells) which take binary states, and update their states simultaneously depending on states of their closest neighbours. We design and study ECA with memory (ECAM), where every cell remembers its states during some fixed period of evolution. We characterize complexity of ECAM in a case study of rule 126, and then provide detailed behavioural classification of ECAM. We show that by enriching ECA with memory we can achieve transitions between the classes of behavioural complexity. We also show that memory helps to ‘discover’ hidden information and behaviour on trivial (uniform, periodic), and non-trivial (chaotic, complex) dynamical systems.

Title: Complete Characterization of Structure of Rule 54

Journal: Complex Systems 23(3), 259-293, 2014. [PDF]

Authors: Genaro J. Martínez, Andrew Adamatzky, Harold V. McIntosh

URL: http://www.complex-systems.com/abstracts/v23_i03_a04.html

Abstract: The dynamics of the rule 54 one-dimensional, two-state cellular automaton (CA) are a discrete analog of a space-time dynamics of excitations in a nonlinear active medium with mutual inhibition. A cell switches its state 0 to state 1 if one of its two neighbors is in state 1 (propagation of a perturbation), and a cell remains in state 1 only if its two neighbors are in state 0. A lateral inhibition is because a 1-state neighbor causes a 1-state cell to switch to state 0. The rule produces a rich spectrum of space-time dynamics, including gliders and glider guns just from four primitive gliders. We construct a catalog of gliders and describe them by tiles. We calculate a subset of regular expressions \Phi_{R54} to encode gliders. The regular expressions are derived from de Bruijn diagrams, tile- based representation of gliders, and cycle diagrams sometimes. We con- struct an abstract machine that recognizes regular expressions of gliders in rule 54 and validate \Phi_{R54}. We also propose a way to code initial con- figurations of gliders to depict any type of collision between the gliders and explore self-organization of gliders, formation of larger tiles, and soliton-like interactions of gliders and computable devices.

Title: Compression-Based Analysis of Cyclic Tag System Emulated by Rule 110

Journal: Journal of Cellular Automata 9(1), 23-35, 2014. [PDF]

Authors: Shigeru Ninagawa, Genaro J. Martínez

Abstract: An elementary cellular automaton rule 110 supports universal computation by emulating cyclic tag system. We employ Lempel-Ziv (LZ) complexity as a measure of compressibility and calculate it during the cyclic tag system emulation process by rule 110. We observe the stepwise decline of LZ complexity during the process. That is caused by the conversion of appendants, symbols added onto the end of the tape, into moving data and the elimination of appendants. These phenomena occur if a cyclic tag system emulation process is solving a problem described by a recursive language.

Title: Designing Complex Dynamics in Cellular Automata with Memory

Journal: International Journal of Bifurcation and Chaos 23(10), 1330035-131, 2013. [PDF]

Authors: Genaro J. Martínez, Andrew Adamatzky, Ramon Alonso-Sanz

URL: http://www.worldscientific.com/doi/abs/10.1142/S0218127413300358

Abstract: Since their inception at `Macy conferences’ in later 1940s complex systems remain the most controversial topic of inter-disciplinary sciences. The term `complex system' is the most vague and liberally used scientific term. Using elementary cellular automata (ECA), and exploiting the CA classification, we demonstrate elusiveness of `complexity' by shifting space-time dynamics of the automata from simple to complex by enriching cells with `memory’. This way, we can transform any ECA class to another ECA class -- without changing skeleton of cell-state transition function --- and vice versa by just selecting a right kind of memory. A systematic analysis display that memory helps `discover' hidden information and behaviour on trivial -- uniform, periodic, and non-trivial -- chaotic, complex -- dynamical systems.

Title: A Note on Elementary Cellular Automata Classification

Journal: Journal of Cellular Automata 8(3-4), 233-259, 2013. [PDF]

Author: Genaro J. Martínez

Abstract: We overview and compare classifications of elementary cellular automata, including Wolfram's, Wuensche's, Li and Packard, communication complexity, power spectral, topological, surface, compression, lattices, and morphological diversity classifications. This paper summarises several classifications of elementary cellular automata (ECA) and compares them with a newly proposed one, that induced by endowing rules with memory.

Title: Logic gates and complex dynamics in a hexagonal cellular automaton: the Spiral rule

Journal: Journal of Cellular Automata 8(1-2), 53-71, 2013. [PDF]

Authors: Rogelio Basurto, Paulina A. León, Genaro J. Martínez, Juan C. Seck-Tuoh-Mora

Abstract: In previous works, hexagonal cellular automata (CA) have been studied as a variation of the famous Game of Life CA, mainly for spiral phenomena simulations; where the most interesting constructions are related to the Belousov-Zhabotinsky reaction. In this paper, we analyse a special kind of hexagonal CA, {\it Spiral rule}. Such automaton shows a non-trivial complex behaviour related to discrete models of reaction-diffusion chemical media, dominated by spiral guns which easily emerge from random initial conditions. The computing capabilities of this automaton are shown by means of logic gates. These are defined by collisions between mobile localizations. Also, an extended classification of complex self-localisation patterns is presented, including some self-organised patterns.

Title: Bio-Imitation of Mexican Migration Routes to the USA with Slime Mould on 3D Terrains

Journal: Journal of Bionic Engineering 10(2), 242-250, 2013. [PDF]

Authors: Andrew Adamatzky, Genaro J. Martínez

URL: http://www.sciencedirect.com/science/article/pii/S1672652913602206

Abstract: Plasmodium of Physarum polycephalum (P. polycephalum) is a large single cell visible by an unaided eye. It shows sophisticated behavioural traits in foraging for nutrients and developing an optimal transport network of protoplasmic tubes spanning sources of nutrients. When placed in an environment with distributed sources of nutrients the cell ‘computes’ an optimal graph spanning the nutrients by growing a network of protoplasmic tubes. P. polycephalum imitates development of man-made transport networks of a country when configuration of nutrients represents major urban areas. We employed this feature of the slime mould to imitate mexican migration to USA. The Mexican migration to USA is the World's largest migration system. We bio-physically imitated the migration using slime mould P. polycephalum. In laboratory experiments with 3D Nylon terrains of USA we imitated development of migratory routes from Mexico-USA border to ten urban areas with high concentration of Mexican migrants. From results of laboratory experiments we extracted topologies of migratory routes, and highlighted a role of elevations in shaping the human movement networks.

Title: Computation and Universality: Class IV versus Class III Cellular Automata

Journal: Journal of Cellular Automata 7(5-6), 393-430, 2013. [PDF]

Authors: Genaro J. Martínez, Juan C. Seck-Tuoh-Mora, Hector Zenil

Abstract: This paper examines the claim that cellular automata (CA) belonging to Class III (in Wolfram’s classification) are capable of (Turing universal) computation. We explore some chaotic CA (believed to belong to Class III) reported over the course of the CA history, that may be candidates for universal computation, hence spurring the discussion on Turing universality on both Wolfram’s classes III and IV.

Title: Emergence of density dynamics by surface interpolation in elementary cellular automata

Journal: Communications in Nonlinear Science and Numerical Simulation 19(4), 941-966, 2013. [PDF soon]

Authors: Juan C. Seck-Tuoh-Mora, Joselito Medina Marin, Genaro J. Martínez, Norberto Hernández Romero

URL: http://www.sciencedirect.com/science/article/pii/S1007570413003638

Abstract: A classic problem in elementary cellular automata (ECAs) is the specification of numerical tools to represent and study their dynamical behaviour. Mean field theory and basins of attraction have been commonly used; however, although the first case gives the long term estimation of density, frequently it does not show an adequate approximation for the step-by-step temporal behaviour; mainly for non-trivial behaviour. In the second case, basins of attraction display a complete representation of the evolution of an ECA, but they are limited up to configurations of 32 cells; and for the same ECA, one can obtain tens of basins to analyse. This paper is devoted to represent the dynamics of density in ECAs for hundreds of cells using only two surfaces calculated by the nearest-neighbour interpolation. A diversity of surfaces emerges in this analysis. Consequently, we propose a surface and histogram based classification for periodic, chaotic and complex ECA.

Title: Expressiveness of Elementary Cellular Automata

Journal: International Journal of Modern Physics C 24(3), 1350010-14, 2013. [PDF]

Authors: Markus Redeker, Andrew Adamatzky, Genaro J. Martínez

URL: http://www.worldscientific.com/doi/abs/10.1142/S0129183113500101

Abstract: We investigate expressiveness, a parameter of one-dimensional cellular automata, in the context of simulated biological systems. The development of elementary cellular automata is interpreted in terms of biological systems, and biologically inspired parameters for biodiversity are applied to the configurations of cellular automata. This article contains a survey of the Elementary Cellular Automata in terms of their expressiveness and an evaluation whether expressiveness is a meaningful term in the context of simulated biology.

Title: Wolfram's Classification and Computation in Cellular Automata Classes III and IV

Book: Irreducibility and Computational Equivalence: 10 Years After Wolfram's A New Kind of Science (Hector Zenil Ed.), Springer Verlag, chapter 17, pages 237-259, 2013. [PDF]

Authors: Genaro J. Martínez, Juan C. Seck-Tuoh-Mora, Hector Zenil

URL: http://www.springer.com/physics/complexity/book/978-3-642-35481-6

Abstract: We conduct a brief survey on Wolfram's classification, in particular related to the computing capabilities of Cellular Automata (CA) in Wolfram's classes III and IV. We formulate and shed light on the question of whether Class III systems are capable of Turing universality or may turn out to be "too hot" in practice to be controlled and programmed. We show that systems in Class III are indeed capable of computation and that there is no reason to believe that they are unable, in principle, to reach Turing-completness.

Title: On Soliton Collisions between Localizations in Complex Elementary Cellular Automata: Rules 54 and 110 and Beyond

Journal: Complex Systems 21(2), 117-142, 2012. [PDF]

Authors: Genaro J. Martínez, Andrew Adamatzky, Fangyue Chen, Leon Chua

Review: Complexity Can Come from Simplicity, New Kind of Science - Homologus, Homologus: Frontier in Bioinformatics, November 20th, 2013.

URL: http://www.complex-systems.com/abstracts/v21_i02_a02.html

Abstract: In this paper, a single-soliton two-component cellular automaton (CA) model of waves is presented as mobile self-localizations, also known as particles, waves, or gliders, in addition to its version with memory. The model is based on coding sets of strings where each chain represents a unique mobile self-localization. The original soliton models in CAs proposed with filter automata are briefly discussed, followed by solutions in elementary CAs (ECAs) domain with the famous universal ECA rule 110, and reporting a number of new solitonic collisions in ECA rule 54. A mobile self-localization in this study is equivalent to a single soliton because the collisions of the mobile self-localizations studied in this pa- per satisfy the property of solitonic collisions. A specific ECA with memory (ECAM), the ECAM rule \phi_{R9maj:4}, is also presented; it displays single-soliton solutions from any initial codification (including random initial conditions) for a kind of mobile self-localization because such an automaton is able to adjust any initial condition to soliton structures.

Title: Book Review “Exploring Discrete Dynamics (by Andrew Wuensche)”, Luniver Press, 2011.

Journal: Artificial Life, MIT Press, 18(3), 325-328, 2012. [PDF]

Author: Genaro J. Martínez

URL: http://www.mitpressjournals.org/doi/abs/10.1162/artl_r_00068

Abstract: Exploring Discrete Dynamics is a very extended computational and analytic exploration of discrete dynamical systems. The book makes a summary of more than 19 years of results, programming, and research by Andrew Wuensche. In 1992, at the Santa Fe Institute, Wuensche together with Mike Lesser published the celebrated book in cellular automata theory The Global Dynamics of Cellular Automata. This book introduced a reverse algorithm for cellular automata, and presented an Atlas of basin of attraction fields computed by means of the algorithm. Motivated by these results and Kauffman's model of genetic regulatory networks, Wuensche subsequently developed new algorithms for random Boolean networks and discrete dynamical networks in general. His achievements have had a great influence on outstanding researchers such as Stuart Kauffman, Harold V. McIntosh, Andrew Adamatzky, and Christopher Langton, among many others; and hundreds of references in books and research papers.

Title: Physarum Narcotráficum: Mexican Highways and Slime Mould

Book: Bioevaluation of World Transport Networks (Andrew Adamatzky Ed.), World Scientific Press, chapter 12, pages 195-211, 2012. [PDF soon]

Authors: Andrew Adamatzky, Genaro J. Martínez, Sergio V. C. Vergara, René A. Palacio, Christopher R. Stephens

URL: http://www.worldscientific.com/worldscibooks/10.1142/8482

Abstract: We analyse the results of our experimental laboratory approximation of motorways networks with slime mould Physarum polycephalum. Motorway networks of fourteen geographical areas are considered: Australia, Africa, Belgium, Brazil, Canada, China, Germany, Iberia, Italy, Malaysia, Mexico, The Netherlands, UK, USA. For each geographical entity we represented major urban areas by oat flakes and inoculated the slime mould in a capital. After slime mould spanned all urban areas with a network of its protoplasmic tubes we extracted a generalised Physarum graph from the network and compared the graphs with an abstract motorway graph using most common measures. The measures employed are the number of independent cycles, cohesion, shortest paths lengths, diameter, the Harary index and the Randic index. We obtained a series of intriguing results, and found that the slime mould approximates best of all the motorway graphs of Belgium, Canada and China, and that for all entities studied the best match between Physarum and motorway graphs is detected by the Randic index (molecular branching index).

Title: Computing on rings

Book: A computable Universe: Understanding and Exploring Nature as Computation (Hector Zenil Ed.), World Scientific Press, chapter 14, pages 283-302, 2012. [PDF]

Authors: Genaro J. Martínez, Andrew Adamatzky, Harold V. McIntosh

Review: Computers Made Out of DNA, Slime and Other Strange Stuff: Particle Collisions, WIRED, Science, April 3, 2013.

URL: http://www.worldscibooks.com/compsci/8306.html

Abstract: In this paper, we will review the features of develop computations based on rings. Particularly, we will analyse what kinds of interaction occur between gliders travelling on a cellular automaton `cyclotron' derived from a catalog of collisions. We will demonstrate that collisions between gliders emulate the basic types of interaction that occur between localizations in non-linear media: fusion, elastic collision, and soliton-like collision. Computational outcomes of a swarm of gliders circling on a one-dimensional torus are analysed via implementation some easy computing models. Gliders in one-dimensional cellular automata are compact groups of non-quiescent patterns translating along automaton lattice. They are cellular-automaton analogous of localizations or quasi-local collective excitations travelling in a spatially extended non-linear medium. So, they can be represented as binary strings or symbols travelling along a one-dimensional ring, interacting with each other and changing their states, or symbolic values, as a result of interactions. We present a number of complex one-dimensional cellular automata with such features.

Title: Complex Dynamics in Life-like Rules Described with de Bruijn Diagrams: Complex and Chaotic Cellular Automata

Journal: Proceedings of the 2012 International Conference on High Performance Computing & Simulation (HPCS 2012), IEEE Xplore 10.1109/HPCSim.2012.6266919, 245-251, 2012. [PDF]

Authors: Paulina A. León, Genaro J. Martínez, Sergio V. C. Vergara

URL: http://ieeexplore.ieee.org/xpl/abstractKeywords.jsp?arnumber=6266919

Abstract: De Bruijn diagrams have been used as a useful tool for the systematic analysis of one-dimensional cellular automata (CA). They can be used to calculate particular kind of con- figurations, ancestors, complex patterns, cycles, Garden of Eden configurations and formal languages. However, there is few progress in two dimensions because its complexity increases exponentially. In this paper, we will offer a way to explore systematically such patterns by de Bruijn diagrams from initial configurations. Such analysis is concentrated mainly in two evolution rules: the famous Game of Life (complex CA) and the Diffusion Rule (chaotic CA ). We will display some preliminary results and benefits to use de Bruijn diagrams in these CA.

Title: Are motorways rational from slime mould's point of view?

Journal: International Journal of Parallel, Emergent and Distributed Systems 28(3), 1-19, 2012. [PDF]

URL: http://www.tandfonline.com/doi/abs/10.1080/17445760.2012.685884

Book: Bioevaluation of World Transport Networks (Andrew Adamatzky Ed.), World Scientific Press, chapter 18, pages 309-339, 2012.

URL: http://www.worldscientific.com/worldscibooks/10.1142/8482

CERN: http://cds.cern.ch/record/1431780?ln=en

Authors: Andrew Adamatzky, Selim Akl, Ramon Alonso-Sanz, Wesley van Dessel, Zuwairie Ibrahim, Andrew Ilachinski, Jeff Jones, Anne V. D. M. Kayem, Genaro J. Martínez, Pedro de Oliveira, Mikhail Prokopenko, Theresa Schubert, Peter Sloot, Emanuele Strano, Xin-She Yang

Abstract: We analyse the results of our experimental laboratory approximation of motorways networks with slime mould Physarum polycephalum. Motorway networks of fourteen geographical areas are considered: Australia, Africa, Belgium, Brazil, Canada, China, Germany, Iberia, Italy, Malaysia, Mexico, The Netherlands, UK, USA. For each geographical entity we represented major urban areas by oat flakes and inoculated the slime mould in a capital. After slime mould spanned all urban areas with a network of its protoplasmic tubes we extracted a generalised Physarum graph from the network and compared the graphs with an abstract motorway graph using most common measures. The measures employed are the number of independent cycles, cohesion, shortest paths lengths, diameter, the Harary index and the Randic index. We obtained a series of intriguing results, and found that the slime mould approximates best of all the motorway graphs of Belgium, Canada and China, and that for all entities studied the best match between Physarum and motorway graphs is detected by the Randic index (molecular branching index).

Title: Complex dynamics of elementary cellular automata emerging in chaotic rules

Journal: International Journal of Bifurcation and Chaos 22(2), 1250023-13, 2012. [PDF]

Authors: Genaro J. Martínez, Andrew Adamatzky, Ramon Alonso-Sanz

URL: http://www.worldscinet.com/ijbc/22/2202/S021812741250023X.html

Abstract: We show novel techniques of analysing complex dynamics of cellular automata (CA) with chaotic behaviour. CA are well known computational substrates for studying emergent collective behaviour, complexity, randomness and interaction between order and disorder. A number of attempts have been made to classify CA functions on their spatio-temporal dynamics and to predict behavior of any given function. Examples include mechanical computation, lambda and Z-parameters, mean field theory, differential equations and number conserving features. We propose to classify CA based on their behaviour when they act in a historical mode, i.e. as CA with memory. We demonstrate that cell-state transition rules enriched with memory quickly transform a chaotic system converging to a complex global behaviour from almost any initial condition. Thus just in few steps we can select chaotic rules without exhaustive computational experiments or recurring to additional parameters. We provide analysis of well-known chaotic functions in one-dimensional CA, and decompose dynamics of the automata using majority memory.

Title: Invertible behavior in elementary cellular automata with memory

Journal: Information Sciences 199, 125-132, 2012. [PDF]

Authors: Juan C. Seck-Tuoh-Mora, Genaro J. Martínez, Ramon Alonso-Sanz, Norberto H. Romero

URL: http://www.sciencedirect.com/science/article/pii/S0020025512001910

Abstract: Elementary cellular automata (ECAs) have been studied for their ability to generate complex global behavior, despite their simplicity. One variation of ECAs is obtained by adding memory to each cell in a neighborhood. This process generates a provisional configuration in which the application of an evolution rule establishes the dynamics of the system. This version is known as an ECA with memory (ECAM). Most previous work on ECAMs analyzed the complex behavior taking chaotic ECAs. However, the present paper investigates reversible ECAMs as obtained from reversible and permutative ECAs. These ECAs have at least one ancestor for every configuration; thus, the correct permutation of states may specify the memory function to obtain reversible ECAMs. For permutative ECAs, which are often irreversible, we demonstrate that the use of a quiescent state and the correct manipulation of de Bruijn blocks produce reversible ECAMs.

Title: Cellular automaton supercolliders

Journal: International Journal of Modern Physics C 22(4), 419-439, 2011. [PDF]

Review: Computer Scientists Build Cellular Automaton Supercollider, Technology Review, Published by MIT, May 25, 2011.

Authors: Genaro J. Martínez, Andrew Adamatzky, Christopher R. Stephens, Alejandro F. Hoeflich

URL: http://www.worldscientific.com/doi/abs/10.1142/S0129183111016348

Abstract: Gliders in one-dimensional cellular automata are compact groups of non-quiescent and non-ether patterns (ether represents a periodic background) translating along automaton lattice. They are cellular-automaton analogous of localizations or quasi-local collective excitations travelling in a spatially extended non-linear medium. They can be considered as binary strings or symbols travelling along a one-dimensional ring, interacting with each other and changing their states, or symbolic values, as a result of interactions. We analyse what types of interaction occur between gliders travelling on a cellular automaton `cyclotron' and build a catalog of the most common reactions. We demonstrate that collisions between gliders emulate the basic types of interaction that occur between localizations in non-linear media: fusion, elastic collision, and soliton-like collision. Computational outcomes of a swarm of gliders circling on a one-dimensional torus are analysed via implementation of cyclic tag systems.

Title: Reproducing the cyclic tag system developed by Matthew Cook with Rule 110 using the phases f1_1

Journal: Journal of Cellular Automata 6(2-3), 121-161, 2011. [PDF]

Authors: Genaro J. Martínez, Harold V. McIntosh, Juan C. Seck-Tuoh-Mora, Sergio V. C. Vergara

Abstract: This paper implements the cyclic tag system (CTS) in Rule 110 developed by Cook in [1, 2] using regular expressions denominated phases fi_1 [3]. The main problem in CTS is coding the initial condition based in a system of gliders. In this way, we develop a method to control the periodic phases of the strings representing all gliders until now known in Rule 110, including glider guns. These strings form a subset of regular expressions implemented in a computational system to facilitate the construction of CTS. Thus, these phases are useful to establish distances and positions for every glider and then to delineate more sophisticated components or packages of gliders. In this manuscript, it is possible to find differences with the results exposed in Wolfram's book [2], inclusively some mistakes which avoid to obtain an appropriated realization of CTS in Rule 110; fortunately, these irregularities were discussed and clarified by Cook.

Title: Approximating Mexican highways with slime mould

Journal: Natural Computing 10(3), 1195-1214, 2011. [PDF]

Authors: Andrew Adamatzky, Genaro J. Martínez, Sergio V. C. Vergara, René A. Palacio, Christopher R. Stephens

URL: http://www.springerlink.com/content/2rqx07812136kh8v/

Review: New Scientist TV: Slime mould takes over Mexican highway system, published by New Scientist TV, November 5, 2010.

CERN: http://cds.cern.ch/record/1297546?ln=en

Abstract: Plasmodium of Physarum polycephalum is a single cell visible by unaided eye. During its foraging behavior the cell spans spatially distributed sources of nutrients with a protoplasmic network. Geometrical structure of the protoplasmic networks allows the plasmodium to optimize transport of nutrients between remote parts of its body. Assuming major Mexican cities are sources of nutrients how much structure of Physarum protoplasmic network correspond to structure of Mexican Federal highway network? To find an answer undertook a series of laboratory experiments with living Physarum polycephalum. We represent geographical locations of major cities by oat flakes, place a piece of plasmodium in Mexico city area, record the plasmodium's foraging behavior and extract topology of nutrient transport networks. Results of our experiments show that the protoplasmic network formed by Physarum is isomorphic, subject to limitations imposed, to a network of principle highways. Ideas and results of the paper may contribute towards future developments in bio-inspired road planning.

Title: Complex Dynamics in a Hexagonal Cellular Automaton

Journal: Proceedings of the 2011 International Conference on High Performance Computing & Simulation (HPCS 2011), IEEE Xplore 10.1109/HPCSim.2011.5999904, 750-756, 2011. [PDF]

Authors: Paulina A. León, Rogelio Basurto, Genaro J. Martínez, Juan C. Seck-Tuoh-Mora

Abstract: Hexagonal cellular automata (CA) were studied with interest as a variation of the famous Game of Life CA, mainly for spiral phenomena simulations; where the most interesting constructions are related to the Belousov-Zhabotinsky reaction. In this paper, we study a special kind of hexagonal CA known as the Spiral rule. Such automaton displays a non-trivial complex behaviour related to discrete models of reaction-diffusion chemical media, dominated by spiral guns that easily emerge from random initial conditions. Computing abilities of Spiral rule automata are shown by means of logic gates, defined by collisions between mobile self-localizations. Also, a more extended classification of complex self-localization patterns is presented, including some self-organized patterns.

Title: How to make dull cellular automata complex by adding memory: Rule 126 case study

Journal: Complexity 15(6), 34-49, 2010. [PDF]

Authors: Genaro J. Martínez, Andrew Adamatzky, Juan C. Seck-Tuoh-Mora, Ramon Alonso-Sanz

URL: http://onlinelibrary.wiley.com/doi/10.1002/cplx.20311/abstract

Abstract: Using Rule 126 elementary cellular automaton (ECA) we demonstrate that a chaotic discrete system --- when enriched with memory -- hence exhibits complex dynamics where such space exploits on an ample universe of periodic patterns induced from original information of the ahistorical system. First we analyse classic ECA Rule 126 to identify basic characteristics with mean field theory, basins, and de Bruijn diagrams. In order to derive this complex dynamics, we use a kind of memory on Rule 126; from here interactions between gliders are studied for detecting stationary patterns, glider guns and simulating specific simple computable functions produced by glider collisions.

Title: Computation with competing patterns in Life-like automaton

Book: Game of Life Automata (Andrew Adamatzky Ed.), Springer, chapter 27, pages 547-572, 2010. [PDF]

Authors: Genaro J. Martínez, Andrew Adamatzky, Kenichi Morita, Maurice Margenstern

URL: http://www.springer.com/computer/theoretical+computer+science/book/978-1-84996-216-2

Abstract: We study a Life-like cellular automaton rule B2/S2345 where a cell in state `0' takes state `1' if it has exactly two neighbors in state `1' and the cell remains in the state `1' if it has between two and five neighbors in state `1.' This automaton is a discrete analog spatially extended chemical media, combining both properties of sub-excitable and precipitating chemical media. When started from random initial configuration B2/S2345 automaton exhibits chaotic behavior. Configurations with low density of state `1' show emergence of localized propagating patterns and stationary localizations. We construct basic logical gates and elementary arithmetical circuits by simulating logical signals with mobile localizations reaction propagating geometrically restricted by stationary non-destructible localizations. Values of Boolean variables are encoded into two types of patterns --- symmetric False and asymmetric True patterns -- which compete for the `empty' space when propagate in the channels. Implementations of logical gates and binary adders are illustrated explicitly.

Title: Localization dynamics in a binary two-dimensional cellular automaton: the Diffusion Rule

Journal: Journal of Cellular Automata 5(4-5), 289-313, 2010. [PDF]

Book: Game of Life Automata (Andrew Adamatzky Ed.), Springer, chapter 17, pages 291-315, 2010.

URL: http://www.springer.com/computer/theoretical+computer+science/book/978-1-84996-216-2

CERN: http://cds.cern.ch/record/1198124?ln=en

Authors: Genaro J. Martínez, Andrew Adamatzky, Harold V. McIntosh

Abstract: We study a two-dimensional cellular automaton (CA), called Diffusion Rule (DR), which exhibits diffusion-like dynamics of propagating patterns. In computational experiments we discover a wide range of mobile and stationary localizations (gliders, oscillators, glider guns, puffer trains, etc), analyze spatio-temporal dynamics of collisions between localizations, and discuss possible applications in unconventional computing.

Title: Elementary cellular automaton Rule 110 explained as a block substitution system

Journal: Computing 88, 193-205, Springer-Verlag, 2010. [PDF]

Authors: Juan C. Seck-Tuoh-Mora, Genaro J. Martínez, Norberto H. Romero, Joselito M. Marín

URL: http://www.springerlink.com/content/c883338q3j470377/

Abstract: This paper presents the characterization of Rule 110 as a block substitution system of three symbols. Firstly, it is proved that the dynamics of Rule 110 is equivalent to cover the evolution space with triangles formed by the cells of the

automaton. It is hence demonstrated that every finite configuration can be partitioned in several blocks of symbols and, that the dynamics of Rule 110 can be reproduced by a set of production rules applied to them. The shape of the blocks in the current

configuration can be used for knowing the number of them in the next one; with this, the evolution of random configurations, ether and gliders can be modeled.

Title: Majority adder implementation by competing patterns in Life-like rule B2/S2345

Journal: Lecture Notes in Computer Science 6079, 93-104, 2010. [PDF]

Authors: Genaro J. Martínez, Kenichi Morita, Andrew Adamatzky, Maurice Margenstern

URL: http://www.springerlink.com/content/q38873422m4774x4/

Abstract: In this paper we present a two-dimensional chaotic cellular automaton, the Life rule B2/S2345, able to simulate the action of an adder with majority gates, stimulated by gliders collisions transformed as competing patterns. Values of Boolean variables are encoded into two types of patterns --- symmetric (FALSE) and asymmetric (TRUE) patterns -- which compete for the `empty' space when propagate in the channels. We construct basic logical gates and elementary arithmetical circuits by simulating logical signals with gliders reaction propagating geometrically restricted by stationary non-destructible still life. Therefore an implementation of universal logical gates and a majority binary adder is constructed.

Title: Operating binary strings using gliders and eaters in reaction-diffusion cellular automaton

Journal: Mathematical and Computer Modeling 52, 177-190, 2010. [PDF]

Authors: Andrew Adamatzky, Genaro J. Martínez, Liang Zhang, Andrew Wuensche

URL: http://www.sciencedirect.com/science/article/pii/S0895717710000580

Abstract: We study transformations of 2-, 4- and 6-bit numbers in interactions between traveling and stationary localizations in the Spiral Rule reaction-diffusion cellular automaton. The Spiral Rule automaton is a hexagonal ternary-state two-dimensional cellular automaton -- a finite-state machine imitation of an activator-inhibitor reaction-diffusion system. The activator is self-inhibited in certain concentrations. The inhibitor dissociates in the absence of the activator. The Spiral Rule cellular automaton has rich spatio-temporal dynamics of traveling (glider) and stationary (eater) patterns. When a glider brushes an eater the eater may slightly change its configuration, which is updated once more every next hit. We encode binary strings in the states of eaters and sequences of gliders. We study what types of binary compositions of binary strings are implementable by sequences of gliders brushing an eater. The models developed will be used in future laboratory designs of reaction-diffusion chemical computers.

Title: Complex dynamics emerging in Rule 30 with majority memory

Journal: Complex Systems 18(3), 345-365, 2010. [PDF]

Authors: Genaro J. Martínez, Andrew Adamatzky, Ramon Alonso-Sanz, Juan C. Seck-Tuoh-Mora

URL: http://www.complex-systems.com/abstracts/v18_i03_a05.html

Abstract: In cellular automata with memory, the unchanged maps of the conventional cellular automata are applied to cells endowed with memory of their past states in some speciﬁed interval. We implement Rule 30 automata with a majority memory and show that using the memory function we can transform quasi-chaotic dynamics of classical Rule 30 into domains of travelling structures with predictable behaviour. We analyse morphological complexity of the automata and classify dynamics of gliders (particle, self-localizations) in memory-enriched Rule 30. We provide formal ways of encoding and classifying glider dynamics using de Bruijn diagrams, soliton reactions and quasi-chemical representations.

Title: On generative morphological diversity of elementary cellular automata

Journal: Kybernetes 39(1), 72-82, 2010. [PDF]

Authors: Andrew Adamatzky, Genaro J. Martínez

URL: http://www.emeraldinsight.com/journals.htm?articleid=1846948

Abstract: Studies in complexity of cellular automata do usually deal with measures taken on integral dynamics or statistical measures of space-time conﬁgurations. No one every tried to analyze a generative power of cellular-automaton machines. We aim to ﬁll the gap and develop a basis for future studies in generative complexity of large-scale spatially extended systems.

Title: A note about the regular language of Rule 110 and its general machine: the scalar subset diagram

Journal: Japan Society for Artificial Intelligence C3004, 39-49, Yokohama, Japan, 2008. [PDF]

Authors: Genaro J. Martínez, Harold V. McIntosh, Juan C. Seck-Tuoh-Mora, Sergio V. C. Vergara

URL: http://eprints.uwe.ac.uk/10576/

Abstract: As it was published in other papers, a regular language can be derived in the elemental cellular automaton (ECA) Rule 110 from a subset of regular expressions produced from its set of gliders. This way, a full description of this subset too is known and reported. This paper will discuss in detail a general machine able to validate completely the subset of regular expressions in Rule 110 and other characteristics, such as, the calculus of Garden of Eden conﬁgurations in Rule 110. Such machine is the subset diagram.

Title: On the representation of gliders in Rule 54 by de Bruijn and cycle diagrams

Journal: Lecture Notes in Computer Science 5191, 83-91, 2008. [PDF]

Authors: Genaro J. Martínez, Andrew Adamatzky, Harold V. McIntosh

URL: http://link.springer.com/chapter/10.1007/978-3-540-79992-4_11

Abstract: Rule 54, in Wolfram’s notation, is one of elementary yet complexly behaving one-dimensional cellular automata. The automaton supports gliders, glider guns and other non-trivial long transients. We show how to characterize gliders in Rule 54 by diagram representations as de Bruijn and cycle diagrams; offering a way to present each glider in Rule 54 with particular characteristics. This allows a compact encoding of initial conditions which can be used in implementing non-trivial collision-based computing in one-dimensional cellular automata.

Title: Computation by competing patterns: Life rule B2/S2345678

Book: Automata 2008: Theory and Applications of Cellular Automata, Luniver Press, chapter 26, pages 356-366, 2008. [PDF]

Authors: Genaro J. Martínez, Andrew Adamatzky, Harold V. McIntosh, Ben De Lacy Costello

URL: http://uncomp.uwe.ac.uk/genaro/Diffusion_Rule/B2-S2345678.html

Abstract: Patterns, originating from different sources of perturbations, propagating in a precipitating chemical medium do usually compete for the space. They sub-divide the medium onto the regions unique for an initial configuration of disturbances. This sub-division can be expressed in terms of computation. We adopt an analogy between precipitating chemical media and semi-totalistic binary two-dimensional cellular automata, with cell-state transition rule B2/S2...8. We demonstrate how to implement basic logic and arithmetical operations (computability) by patterns propagating in geometrically constrained Life rule B2/S2...8 medium.

Title: On logical gates in precipitating medium: cellular automaton model

Journal: Physics Letters A 1(48), 1-5, 2008. [PDF]

Authors: Genaro J. Martínez, Andrew Adamatzky, Ben De Lacy Costello

URL: http://www.sciencedirect.com/science/article/pii/S0375960108008736

Abstract: We study a two-dimensional semi-totalistic binary cell-state cellular automaton, which imitates a reversible precipitation in an abstract chemical medium. The systems exhibits a non-trivial growth and nucleation. We demonstrate how basic computational operation can be realized in the system when the propagation of the growing patterns is self-restricted by stationary localizations. We show that precipitating patterns of different morphology compete between each other and thus implement serial and non-serial logical gates.

Title: Determining a regular language by glider-based structures called phases fi_1 in Rule 110

Journal: Journal of Cellular Automata 3(3), 231-270, 2008. [PDF]

Authors: Genaro J. Martínez, Harold V. McIntosh, Juan C. Seck-Tuoh-Mora, Sergio V. C. Vergara

Abstract: Rule 110 is a complex elementary cellular automaton able of supporting universal computation and complicated collision-based reactions between gliders. We propose a representation for coding initial conditions by means of a finite subset of regular expressions. The sequences are extracted both from de Bruijn diagrams and tiles specifying a set of phases fi_1 for each glider in Rule 110. The subset of regular expressions is explained in detail.

Title: Unconventional invertible behaviors in reversible one-dimensional cellular automata

Journal: International Journal of Bifurcation and Chaos 18(12), 3625–3632, 2008. [PDF]

Authors: Juan C. Seck-Tuoh-Mora, Manuel G. Hernández, Genaro J. Martínez, Serigo V. C. Vergara, Harold V. McIntosh

URL: http://www.worldscientific.com/doi/abs/10.1142/S0218127408022597

Abstract: Reversible cellular automata are discrete invertible dynamical systems determined by local interactions among their components. For the one-dimensional case, there are classical references providing a complete characterization based on combinatorial properties. Using these results and the simulation of every automaton by another with neighborhood size 2, this paper describes other types of invertible behaviors embedded in these systems diﬀerent from the classical one observed in the temporal evolution. In particular spatial reversibility and diagonal surjectivity are studied, and the generation of macrocells in the evolution space is analyzed.

Title: Rule 110 objects and other constructions based-collisions

Journal: Journal of Cellular Automata 2(3), 219-242, 2007. [PDF]

Authors: Genaro J. Martínez, Harold V. McIntosh, Juan C. Seck-Tuoh-Mora, Sergio V. C. Vergara

Abstract: The one-dimensional cellular automaton Rule 110 shows a very ample and diversified glider dynamics. The huge number of collision-based reactions presented in its evolution space are useful to implement some specific (conventional and unconventional) computable process, hence Rule 110 may be used to implement any desired simulation. Therefore there is necessity of defining some interesting objects as: solitons, eaters, black holes, flip-flops, fuses and more. For example, this work explains the construction of meta-gliders; for these constructions, we specify a regular language in Rule 110 to code in detail initial conditions with a required behavior. The paper depicts as well several experimental collision-based constructions.

Title: Phenomenology of reaction-diffusion binary-state cellular automata

Authors: Andrew Adamatzky, Genaro J. Martínez, Juan C. Seck-Tuoh-Mora

Journal: International Journal of Bifurcation and Chaos 16(10), 1-21, 2006. [PDF]

URL: http://www.worldscientific.com/doi/abs/10.1142/S0218127406016598

Abstract: We study a binary-cell-states eight-cell neighborhood two-dimensional cellular automaton model of a quasi-chemical system with a substrate and a reagent. Reactions are represented by semi-totalistic transitions rules: every cell switches from state 0 to state 1 depending on if sum of neighbors in state 1 belongs to some specified interval, cell remains in state 1 if sum of neighbors in state 1 belong to another specified interval. We investigate space-time dynamics of 1296 automata, establish morphology-bases classification of the rules, explore precipitating and excitatory cases and scrutinize collisions between mobile and stationary localizations (gliders, cycle life and still life compact patterns). We explore reaction-diffusion like patterns produced in result of collisions between localizations. Also, we propose a set of rules with complex behavior called Life 2c22.

Title: The inverse behavior of a reversible one-dimensional cellular automaton obtained by a single welch diagram

Journal: Journal of Cellular Automata 1(1), 25-39, 2006. [PDF]

Authors: Juan C. Seck-Tuoh-Mora, Genaro J. Martínez, Harold V. McIntosh

Abstract: Reversible cellular automata are discrete dynamical systems based on local interactions which are able to produce an invertible global behavior. Reversible automata have been carefully analyzed by means of graph and matrix tools, in particular the extensions of the ancestors in these systems have a complete representation by Welch diagrams. This paper illustrates how the whole information of a reversible one-dimensional cellular automaton is conserved at both sides of the ancestors for sequences with an adequate length. We give this result implementing a procedure to obtain the inverse behavior by means of calculating and studying a single Welch diagram corresponding with the extensions of only one side of the ancestors. This work is a continuation of our study about reversible automata both in the local and global sense. An illustrative example is also presented.

Title: Phenomenology of glider collisions in cellular automaton Rule 54 and associated logical gates

Journal: Chaos, Fractals and Solitons 28, 100-111, 2006. [PDF]

Authors: Genaro J. Martínez, Andrew Adamatzky, Harold V. McIntosh

URL: http://www.sciencedirect.com/science/article/pii/S0960077905004893

Abstract: Rule 54, a two state, three neighbor cellular automaton in Wolfram Rule 110, but nevertheless possess a rich and complex dynamics. We provide a systematic and exhaustive analysis of glider behavior and interactions, including a catalog of collisions. Many of them shows promise are computational elements.

Title: Gliders in Rule 110

Journal: International Journal of Unconventional Computing 2(1), 1-49, 2006. [PDF]

Authors: Genaro J. Martínez, Harold V. McIntosh, Juan C. Seck-Tuoh-Mora

URL: http://www.oldcitypublishing.com/IJUC/IJUCabstracts/IJUC2.1abstracts/IJUCv2n1p1-49Martinez.html

Abstract: The existence of several periodic structures (known as gliders) in the evolution space of the one-dimensional cellular automaton Rule 110, has important lines of investigation in cellular automata theory such as: complex behavior, universal computation and self-reproduction. We investigate the types of gliders, their properties and production through collisions in Rule 110 and their representation by tiles.

Title: Procedures for calculating reversible one-dimensional cellular automata

Journal: Physica D 202, 134-141, 2005. [PDF]

Authors: Juan C. Seck-Tuoh-Mora, Sergio V. C. Vergara, Genaro J. Martínez, Harold V. McIntosh

URL: http://www.sciencedirect.com/science/article/pii/S0167278905000540

Abstract: Two algorithms for calculating reversible one-dimensional cellular automata of neighborhood size 2 are presented. It is explained how this kind of automata represents all the rest. Using two basic properties of these systems such as the uniform multiplicity of ancestors and Welch indices, these algorithms only require matrix products and the transitive closure of binary relations to yield the calculation of reversible automata. The features, advantages and differences of these algorithms are described and results for reversible automata of 3, 4, 5 and 6 states are comprised.

Title: Un subconjunto de autómata celular con comportamiento complejo en dos dimensiones

Place: Escuela Superior de Cómputo, Instituto Politécnico Nacional, México, 2005. [PDF] spanish workpaper

Authors: Genaro Juárez Martínez, Adriana Menchaca Méndez, Miriam Mecate Zambrano

Abstract: Modelos matemáticos con la capacidad de soportar comportamiento complejo han sido formulados y análizados a través de la historia de las matemáticas. Nosotros estudiamos un modelo discreto en dos dimensiones conocido como autómata celular. Dentro de estos sistemas dinámicos existen funciones que pueden soportar comportamiento complejo, como el famoso “Juego de la Vida.” En este artículo presentamos un nuevo subconjunto de reglas que soportan partículas y que llamamos Life 2c22. Además calculamos sus mutaciones con la capacidad de soportar comportamientos del tipo reacción-difusión a través de choques entre partículas.

Title: Introduction to Rule 110

Place: Bielefeld, Germany, 2004. [HTML or PDF workpaper] (also available from Rule110.org)

Author: Genaro J. Martínez

Abstract: A brief introduction to the study of the cellular automaton Rule 110 is presented. We begin with a general historical background of cellular automata theory, discussing the most important stages of development. Later we show the antecedents in the study of Rule 110, making special emphasis in the conjecture of Stephen Wolfram and the results of Matthew Cook. Finally we develop a relation between the models of John von Neumann, John Horton Conway and Cook, discussing important problems in cellular automata theory.

Title: Introduction to OSXLCAU21 System

Place: Bielefeld, Germany, 2004. [HTML and PDF workpaper] (also available from Rule110.org)

Author: Genaro J. Martínez

Abstract: This paper describes each one of the parts of OSXLCAU21 system, the main feature of this application is the panel of gliders which allows to reproduce any binary collisions among them. The system is implemented with the idea of providing an useful and easy environment to the user for studying and realizing experimentation in the analysis of Rule 110.

Title: Calculating ancestors in one-dimensional cellular automata

Journal: International Journal of Modern Physics C 15(8), 1151-1169, 2004. [PDF]

Authors: Juan C. Seck-Tuoh-Mora, Genaro J. Martínez, Harold V. McIntosh

Abstract: One-dimensional cellular automata are dynamical systems characterized by discreteness (in space and time), determinism and local interaction. We present a procedure in order to calculate ancestors for a given sequence of states, this procedure is based on a special kind of graph called subset diagram. We use this diagram to specify subset tables for calculating ancestors which are not Garden-of-Eden sequences, hence the process is able to yield ancestors in several generations. Some examples are illustrated using the cellular automaton Rule 110 which is the most interesting automaton of two states and three neighbors.

Title: Correspondence between the temporal and spacial behavior in reversible one-dimensional cellular automata equivalent with the full shift

Place: DMCS Workshop, University of Turku, Finland, 2004. [PDF]

Authors: Juan C. Seck-Tuoh-Mora, Genaro J. Martínez, Harold V. McIntosh

Abstract: We present the basic properties of reversible one-dimensional cellular automata equivalent by permutations with the full shift, this work only takes reversible automata of neighborhood size 2. In these cases, we prove that the evolution rule defining the temporal behavior of the automaton may specify the spacial behavior as well. Based in this result we present a procedure for constructing configurations with a predefined dynamical behavior. Some examples of these results are presented.

Title: Production of gliders by collisions in Rule 110

Journal: Lecture Notes in Computer Science 2801, 175-182, 2003. [PDF]

Authors: Genaro J. Martínez, Harold V. McIntosh, Juan C. Seck-Tuoh-Mora

URL: http://link.springer.com/chapter/10.1007%2F978-3-540-39432-7_19

Abstract: We investigate the construction of all the periodic structures or “gliders” up to now known in the evolution space of the one-dimensional cellular automaton Rule 110. The production of these periodic structures is developed and presented by means of glider collisions. We provide a methodology based on the phases of each glider to establish the necessary conditions for controlling and displaying the collisions of gliders from the initial configuration.

Title: Spectral properties of reversible one-dimensional cellular automata

Journal: International Journal of Modern Physics C 14(3), 379-395, 2003. [PDF]

Authors: Juan C. Seck-Tuoh-Mora, Sergio V. C. Vergara, Genaro J. Martínez, Harold V. McIntosh

Abstract: Reversible cellular automata are invertible dynamical systems characterized by discreteness, determinism and local interaction. This article studies the local behavior of reversible one-dimensional cellular automata by means of the spectral properties of their connectivity matrices. We use the transformation from every one-dimensional cellular automaton to another of neighborhood size 2 to generalize the results exposed in this paper. In particular we prove that the connectivity matrices have a single positive eigenvalue equal to 1; based on this result we also prove the main result of this paper: the idempotent behavior of these matrices. This property is an important feature for detecting which one-dimensional cellular automata are reversible. Hence we present a procedure using the eigenvectors of these matrices to find the inverse rule for a given reversible one-dimensional cellular automaton. Finally illustrative examples are provided.

Title: Solitones en el autómata celular unidimensional regla 110

Publication: Workpaper.

Place: Sección Computación, CINVESTAV, 2002. [HTML or PDF] spanish workpaper

Author: Genaro J. Martínez

Abstract: Se estudia el fenómeno solitón en el autómata celular unidimensional regla 110. Se presentan las propiedades generales del espacio de evoluciones y sus estructuras periódicas, útiles para la generación de choques y solitones, mostrando el procedimiento para reproducir solitones bajo ciertas condiciones. Finalmente se presenta un caso especial donde un seudo-solitón puede cambiar su forma y regresar a su estado original conservando su velocidad.

Title: Encontrando solitones en el autómata celular regla 110

Publication: Workpaper.

Place: Sección Computación, CINVESTAV, 2002. [HTML from UNAM] spanish workpaper

Author: Genaro J. Martínez

Abstract: El fenómeno solitón es una área de la física bien fundamentada, es este reporte se muestra como un autómata celular en una dimensión puede simular este fenómeno. Una característica importante es que es un sistema dinámico discreto fácil implementar computacionalmente.

Title: ATLAS: Collisions of gliders as phases of ether in rule 110

Publication: Workpaper.

Place: Departamento de Microcomputadoras, Universidad Autónoma de Puebla, México, 2001. [HTML]

Authors: Genaro J. Martínez, Harold V. McIntosh