Representing Reversible Cellular Automata with Reversible Block Cellular Automata
Copyright policy )Representing Reversible Cellular Automata with Reversible Block Cellular Automata
Cellular automata are mappings over infinite lattices such that each cell is updated according tothe states around it and a unique local function.Block permutations are mappings that generalize a given permutation of blocks (finite arrays of fixed size) to a given partition of the lattice in blocks.We prove that any d-dimensional reversible cellular automaton can be exp ressed as thecomposition of d+1 block permutations.We built a simulation in linear time of reversible cellular automata by reversible block cellular automata (also known as partitioning CA and CA with the Margolus neighborhood) which is valid for both finite and infinite configurations. This proves a 1990 conjecture by Toffoli and Margolus <i>(Physica D 45)</i> improved by Kari in 1996 <i>(Mathematical System Theory 29)</i>.
Cellular automata, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], Cellular Automata, [INFO] Computer Science [cs], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], Partitioning Cellular Automata, reversibility, [info.info-cg] computer science [cs]/computational geometry [cs.cg], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], QA1-939, partitioning cellular automata, Reversible Cellular Automata, [INFO]Computer Science [cs], [math.math-co] mathematics [math]/combinatorics [math.co], [INFO.INFO-FL] Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], cellular automata, [info] computer science [cs], [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], Block Cellular Automata, block cellular automata, Mathematics
Cellular automata, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], Cellular Automata, [INFO] Computer Science [cs], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], Partitioning Cellular Automata, reversibility, [info.info-cg] computer science [cs]/computational geometry [cs.cg], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], QA1-939, partitioning cellular automata, Reversible Cellular Automata, [INFO]Computer Science [cs], [math.math-co] mathematics [math]/combinatorics [math.co], [INFO.INFO-FL] Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], cellular automata, [info] computer science [cs], [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], Block Cellular Automata, block cellular automata, Mathematics
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).15 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!