Reachability problem in non-uniform cellular automata

DOI10.1016/J.INS.2020.07.034MaRDI QIDQ2053879zbMATH OpenOpenAlexFDO

Authors Sumit Adak, Sukanya Mukherjee, Sukanta Das

Publication date 30 November 2021

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.08246

zbMATH Keywords

non-uniform cellular automatareachability treerule min-term (RMT)

Mathematics Subject Classification ID

Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80)

Abstract: This paper deals with the CREP (Configuration REachability Problem) for non-uniform cellular automata (CAs). The cells of non-uniform CAs, we have considered here, can use different Wolfram's rules to generate their next states. We report an algorithm which decides whether or not a configuration of a given (non-uniform) cellular automaton is reachable from another configuration. A characterization tool, named Reachability tree, is used to develop theories and the decision algorithm for the CREP. Though the worst case complexity of the algorithm is exponential in time and space, but the average performance is very good.

Recommendations

• The reachability problem for finite cellular automata
• Characterization of Reachable/Nonreachable Cellular Automata States
• Non-uniform cellular automata: classes, dynamics, and decidability
• On synthesis of non-uniform cellular automata having only point attractors
• Characterization of Non-reachable States in Irreversible CA State Space

Cites work

• Algebraic properties of cellular automata
• Co-evolving non-uniform cellular automata to perform computations
• Computational complexity of rule distributions of non-uniform cellular automata
• scientific article; zbMATH DE number 3896307 (Why is no real title available?)
• scientific article; zbMATH DE number 3549966 (Why is no real title available?)
• scientific article; zbMATH DE number 1070886 (Why is no real title available?)
• scientific article; zbMATH DE number 1956212 (Why is no real title available?)
• scientific article; zbMATH DE number 778215 (Why is no real title available?)
• Introduction to algorithms
• On synthesis of non-uniform cellular automata having only point attractors
• On the computational complexity of finite cellular automata
• Statistical mechanics of cellular automata
• The reachability problem for finite cellular automata

Cited in

(6)

• Random expansion method for the generation of complex cellular automata
• Characterization of Reachable/Nonreachable Cellular Automata States
• Non-uniform number-conserving elementary cellular automata
• A comprehensive taxonomy of cellular automata
• The reachability problem for finite cellular automata
• A new method of reachable sets estimation for the nonlinear switched singular system with impulsive performance and time-delay

This page was built for publication: Reachability problem in non-uniform cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2053879)