The predecessor-existence problem for k-reversible processes

DOI10.1016/J.TCS.2014.10.018zbMATH Open1303.68094OpenAlexW1986767049MaRDI QIDQ476889FDOQ476889

Authors 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)

Abstract: For k>=1, we consider the graph dynamical system known as a k-reversible process. In such process, each vertex in the graph has one of two possible states at each discrete time. Each vertex changes its state between the present time and the next if and only if it currently has at least k neighbors in a state different than its own. Given a k-reversible process and a configuration of states assigned to the vertices, the Predecessor Existence problem consists of determining whether this configuration can be generated by the process from another configuration within exactly one time step. We can also extend the problem by asking for the number of configurations from which a given configuration is reachable within one time step. Predecessor Existence can be solved in polynomial time for k=1, but for k>1 we show that it is NP-complete. When the graph in question is a tree we show how to solve it in O(n) time and how to count the number of predecessor configurations in O(n^2) time. We also solve Predecessor Existence efficiently for the specific case of 2-reversible processes when the maximum degree of a vertex in the graph is no greater than 3. For this case we present an algorithm that runs in O(n) time.

Recommendations

• scientific article; zbMATH DE number 1536236
• scientific article; zbMATH DE number 2046041
• Criterion for the existence of reversibleQ-processes
• On \(f\)-reversible processes on graphs
• A reversibility problem for Fleming-Viot processes
• Predecessor existence problems for finite discrete dynamical systems
• On reversible semi-Markov processes
• On strong reversibility in P systems and related problems
• Generalized predecessor existence problems for Boolean finite dynamical systems
• Predecessors existence problems and Gardens of Eden in sequential dynamical systems

Cites Work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1741013 (Why is no real title available?)
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Comportement périodique des fonctions à seuil binaires et applications
• Introduction to algorithms.
• MODELING INFECTIOUS DISEASES USING GLOBAL STOCHASTIC CELLULAR AUTOMATA
• Neural networks and physical systems with emergent collective computational abilities
• On the computational complexity of finite cellular automata
• Reaching a Consensus
• Reversible iterative graph processes
• Size bounds for dynamic monopolies
• The convergence of symmetric threshold automata

Cited In (2)

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

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

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