Complexity of inferring local transition functions of discrete dynamical systems

DOI10.1007/978-3-319-22360-5_3MaRDI QIDQ2947406zbMATH OpenOpenAlexFDO

Authors Abhijin Adiga, Chris J. Kuhlman, S. S. Ravi, R. E. Stearns, Madhav V. Marathe, Daniel J. Rosenkrantz

Publication date 23 September 2015

Published in Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-22360-5_3

Mathematics Subject Classification ID

Dynamical systems involving maps of trees and graphs (37E25) Analysis of algorithms and problem complexity (68Q25) Computational learning theory (68Q32) Formal languages and automata (68Q45)

Recommendations

• Inferring local transition functions of discrete dynamical systems from observations of system behavior
• Dichotomy results for fixed-point existence problems for Boolean dynamical systems
• Reachability problems for sequential dynamical systems with threshold functions.
• Computational complexity of threshold automata networks under different updating schemes
• Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs

Cites work

• A Random NP-complete problem for inversion of 2D cellular automata
• Complexity of inferring local transition functions of discrete dynamical systems
• Complexity of reachability problems for finite discrete dynamical systems
• Computational classification of cellular automata
• Dichotomy results for fixed point counting in Boolean dynamical systems
• scientific article; zbMATH DE number 4058875 (Why is no real title available?)
• scientific article; zbMATH DE number 45557 (Why is no real title available?)
• scientific article; zbMATH DE number 45867 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 1741013 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Introduction to algorithms.
• Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems
• Networks, crowds and markets. Reasoning about a highly connected world.
• Predecessor existence problems for finite discrete dynamical systems
• Recovering social networks from contagion information
• Rumors in a Network: Who's the Culprit?

Cited in

(2)

• Inferring local transition functions of discrete dynamical systems from observations of system behavior
• Complexity of inferring local transition functions of discrete dynamical systems

This page was built for publication: Complexity of inferring local transition functions of discrete dynamical systems

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