Unconventional Computation

DOI10.1007/11560319MaRDI QIDQ5479212zbMATH OpenOpenAlexFDO

Authors Predrag T. Tosic, Gul A. Agha

Publication date 7 July 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11560319

zbMATH Keywords

computational complexitycellular automata\#P-completenessgraph automataconfiguration space propertiessequential and synchronous dynamical systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Cellular automata (computational aspects) (68Q80)

Recommendations

• ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS
• On the complexity of enumerating possible dynamics of sparsely connected Boolean network automata with simple update rules
• Dichotomy results for fixed point counting in Boolean dynamical systems
• scientific article; zbMATH DE number 1741013
• Dichotomy results for fixed-point existence problems for Boolean dynamical systems

Cited in

(14)

• Predecessor existence problems for finite discrete dynamical systems
• Fixed points in generalized parallel and sequential dynamical systems induced by a minterm or maxterm Boolean functions
• Maximum number of periodic orbits in parallel dynamical systems
• Existence, coexistence and uniqueness of fixed points in parallel and sequential dynamical systems over directed graphs
• Complexity of fixed point counting problems in Boolean networks
• ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS
• Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs
• On periods and equilibria of computational sequential systems
• Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems
• Counting and hardness-of-finding fixed points in cellular automata on random graphs
• Enumerating periodic orbits in sequential dynamical systems over graphs
• On the complexity of enumerating possible dynamics of sparsely connected Boolean network automata with simple update rules
• Dichotomy results for fixed point counting in Boolean dynamical systems
• Counting fixed points and pure 2-cycles of tree cellular automata

This page was built for publication: Unconventional Computation

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