Open AccessThe reversibility of one-dimensional cellular automata
Author(s) -
Alexey E. Zhukov,
Жуков Алексей Евгеньевич
Publication year - 2021
Publication title -
vestnik rossijskogo universiteta družby narodov. seriâ inženernye issledovaniâ
Language(s) - English
Resource type - Journals
eISSN - 2312-8151
pISSN - 2312-8143
DOI - 10.22363/2312-8143-2021-22-1-7-15
Subject(s) - cellular automaton , continuous spatial automaton , mobile automaton , stochastic cellular automaton , asynchronous cellular automaton , reversible cellular automaton , block cellular automaton , filter (signal processing) , computer science , timed automaton , quantum cellular automaton , dimension (graph theory) , continuous automaton , elementary cellular automaton , binary number , algorithm , quantum finite automata , theoretical computer science , automaton , mathematics , automata theory , combinatorics , arithmetic , computer vision
Recently the reversible cellular automata are increasingly used to build high-performance cryptographic algorithms. The paper establishes a connection between the reversibility of homogeneous one-dimensional binary cellular automata of a finite size and the properties of a structure called binary filter with input memory and such finite automata properties as the prohibitions in automata output and loss of information. We show that finding the preimage for an arbitrary configuration of a one-dimensional cellular automaton of length L with a local transition function f is associated with reversibility of a binary filter with input memory. As a fact, the nonlinear filter with an input memory corresponding to our cellular automaton does not depend on the number of memory cells of the cellular automaton. The results obtained make it possible to reduce the complexity of solving massive enumeration problems related to the issues of reversibility of cellular automata. All the results obtained can be transferred to cellular automata with non-binary cell filling and to cellular automata of dimension greater than 1.