The predecessor-existence problem for \(k\)-reversible processes

DOI10.1016/j.tcs.2014.10.018zbMath1303.68094arXiv1307.7259OpenAlexW1986767049MaRDI QIDQ476889

Leonardo I. L. Oliveira, Valmir C. Barbosa, Fábio Protti

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

graph dynamical systems\(k\)-reversible processesGarden-of-Eden configurationspredecessor-existence problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial dynamics (types of periodic orbits) (37E15) Dynamical systems involving maps of trees and graphs (37E25)

Related Items (1)

A computational study of \(f\)-reversible processes on graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reversible iterative graph processes
• Comportement périodique des fonctions à seuil binaires et applications
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Size bounds for dynamic monopolies
• On the computational complexity of finite cellular automata
• The convergence of symmetric threshold automata
• Reaching a Consensus
• Neural networks and physical systems with emergent collective computational abilities.
• MODELING INFECTIOUS DISEASES USING GLOBAL STOCHASTIC CELLULAR AUTOMATA

This page was built for publication: The predecessor-existence problem for \(k\)-reversible processes