Reversibility of d-State Finite Cellular Automata Article Swipe

View

Related Concepts

Reachability Cellular automaton De Bruijn graph Finite-state machine Automaton Computer science Graph De Bruijn sequence Tree (set theory) Timed automaton Asynchronous cellular automaton Set (abstract data type) Algorithm Discrete mathematics Combinatorics Mathematics Theoretical computer science Mobile automaton Automata theory Programming language

Kamalika Bhattacharjee , Sukanta Das ·

YOU? · · 2015 · Open Access · · OA: W2963489713

This paper investigates reversibility properties of 1-dimensional 3-neighborhood d-state finite cellular automata (CAs) of length n under periodic boundary condition. A tool named reachability tree has been developed from de Bruijn graph which represents all possible reachable configurations of an n-cell CA. This tool has been used to test reversibility of CAs. We have identified a large set of reversible CAs using this tool by following some greedy strategies.