Reachability problem in non-uniform cellular automata

DOI10.1016/J.INS.2020.07.034zbMATH Open1475.68197arXiv1901.08246OpenAlexW3044250431MaRDI QIDQ2053879FDOQ2053879

Authors: Sumit Adak, Sukanya Mukherjee, Sukanta Das 

Publication date: 30 November 2021

Published in: Information Sciences (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Introduction to algorithms
• Statistical mechanics of cellular automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Co-evolving non-uniform cellular automata to perform computations
• Algebraic properties of cellular automata
• On the computational complexity of finite cellular automata
• Computational complexity of rule distributions of non-uniform cellular automata
• The reachability problem for finite cellular automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• On synthesis of non-uniform cellular automata having only point attractors

Cited In (4)

• Characterization of Reachable/Nonreachable Cellular Automata States
• Random expansion method for the generation of complex cellular automata
• A comprehensive taxonomy of cellular automata
• Non-uniform number-conserving elementary cellular automata

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)