Linear Time Algorithm for Identifying the Invertibility of Null-Boundary Three Neighborhood Cellular Automata
Complex Systems2010Vol. 19(1), pp. 89–113
Citations Over TimeTop 21% of 2010 papers
Abstract
This paper reports an algorithm to check for the invertibility of nullboundary three neighborhood cellular automata (CAs). While the best known result for checking invertibility is quadratic [1, 2], the complexity of the proposed algorithm is linear. An efficient data structure called a rule vector graph (RVG) is proposed to represent the global functionality of a cellular automaton (CA) by its rule vector (RV). The RVG of a null-boundary invertible CA preserves the specific characteristics that can be checked in linear time. These results are shown in the more general case of hybrid CAs. This paper also lists the elementary rules [3] that are invertible.
Related Papers
- → Crowd Simulation for Evacuation Behaviors Based on Multi-agent System and Cellular Automaton(2014)21 cited
- → Evolution of Microstructure during the Shape Rolling Modeled by Cellular Automata(2012)8 cited
- → Study on the Evacuation Simulation Based on Cellular Automata(2009)4 cited
- Cellular Automaton Modeling and Its Applications in Computer Simulation of Microstructures(2000)
- → An Improved Algorithm of the Cellular Automata on the Evacuation Simulation(2008)