The predecessor-existence problem for k-reversible processes

DOI10.1016/J.TCS.2014.10.018zbMATH Open1303.68094arXiv1307.7259OpenAlexW1986767049MaRDI 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)

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.

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

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

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)

Cites Work

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

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)