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

Juan Carlos Seck-Tuoh-Mora; Joselito Medina-Marin; Norberto Hernandez-Romero; Genaro J. Martinez; Irving Barragan-Vite

doi:10.1016/j.ins.2016.12.009

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

Juan Carlos Seck-Tuoh-Mora, Joselito Medina-Marin, Norberto Hernandez-Romero, Genaro J. Martinez, Irving Barragan-Vite

Escuela Superior de Cómputo (ESCOM)

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

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.

Original language	English
Pages (from-to)	81-95
Number of pages	15
Journal	Information Sciences
Volume	382-383
DOIs	https://doi.org/10.1016/j.ins.2016.12.009
State	Published - 1 Mar 2017

Keywords

Bipartite graph
Block mapping
Cellular automata
Reversibility
Welch indices

Access to Document

10.1016/j.ins.2016.12.009

Cite this

@article{4fd78b2c1c54497f9a9fd6d8f1ab0da1,

title = "Welch sets for random generation and representation of reversible one-dimensional cellular automata",

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.",

keywords = "Bipartite graph, Block mapping, Cellular automata, Reversibility, Welch indices",

author = "Seck-Tuoh-Mora, {Juan Carlos} and Joselito Medina-Marin and Norberto Hernandez-Romero and Martinez, {Genaro J.} and Irving Barragan-Vite",

note = "Publisher Copyright: {\textcopyright} 2016 Elsevier Inc.",

year = "2017",

month = mar,

day = "1",

doi = "10.1016/j.ins.2016.12.009",

language = "Ingl{\'e}s",

volume = "382-383",

pages = "81--95",

journal = "Information Sciences",

issn = "0020-0255",

}

TY - JOUR

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

AU - Seck-Tuoh-Mora, Juan Carlos

AU - Medina-Marin, Joselito

AU - Hernandez-Romero, Norberto

AU - Martinez, Genaro J.

AU - Barragan-Vite, Irving

PY - 2017/3/1

Y1 - 2017/3/1

N2 - 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.

AB - 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.

KW - Bipartite graph

KW - Block mapping

KW - Cellular automata

KW - Reversibility

KW - Welch indices

UR - http://www.scopus.com/inward/record.url?scp=85004097205&partnerID=8YFLogxK

U2 - 10.1016/j.ins.2016.12.009

DO - 10.1016/j.ins.2016.12.009

M3 - Artículo

AN - SCOPUS:85004097205

SN - 0020-0255

VL - 382-383

SP - 81

EP - 95

JO - Information Sciences

JF - Information Sciences

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this