2022/08/27 by Xuan Kien Phung, Phung, Xuan Kien
Computer Science · #Cellular Automata and Applications #Cellular Automata and Lattice Gases (nlin.CG) #Discrete Mathematics (cs.DM) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Quantum-Dot Cellular Automata
paper · pdf · doi:10.48550/arxiv.2208.13069
openalex publication_date 2022/08/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For linear non-uniform cellular automata (NUCA) over an arbitrary universe, we introduce and investigate their dual linear NUCA. Generalizing results for linear CA, we show that dynamical properties namely pre-injectivity, resp. injectivity, resp. stably injectivity, resp. invertibility of a linear NUCA is equivalent to surjectivity, resp. post-surjectivity, resp. stably post-surjectivity, resp. invertibility of the dual linear NUCA. However, while bijectivity is a dual property for linear CA, it is no longer the case for linear NUCA. We prove that for linear NUCA, stable injectivity and stable post-surjectivity are precisely characterized respectively by left invertibility and right invertibility and that a linear NUCA is invertible if and only if it is pre-injective and stably post-surjective. Moreover, we show that linear NUCA satisfy the important shadowing property. Applications on the dual surjunctivity are also obtained.