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

详细信息    查看全文

• 作者：Juan Carlos Seck-Tuoh-Mora ; ^a ; ^{jseck@uaeh.edu.mx} ; Joselito Medina-Marin^a ; ^{jmedina@uaeh.edu.mx} ; Norberto Hernandez-Romero^a ; ^{nhromero@uaeh.edu.mx} ; Genaro J. Martinez^b ; ^c ; ^{genaro.martinez@uwe.ac.uk} ; Irving Barragan-Vite^a ; ^{ibarragan@uaeh.edu.mx}
• 关键词：Cellular automata ; Reversibility ; Welch indices ; Bipartite graph ; Block mapping
• 刊名：Information Sciences
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：382-383
• 期：Complete
• 页码：81-95
• 全文大小：6860 K
• 卷排序：382

文摘

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.