Predecessor and Permutation Existence Problems for Sequential Dynamical Systems.

Predecessor and Permutation Existence Problems for Sequential Dynamical Systems.

A class of finite discrete dynamical systems, called Sequential Dynamical Systems (SDSs), was introduced in [BR99] as a formal model for analyzing simulation systems. Here, we address the complexity of two basic problems and their generalizations for SDSs.Given an SDS $\mathcal{S}$ and a configurati...

Full description

Bibliographic Details
Main Authors: Christopher L. Barrett, Harry Hunt, Madhav V. Marathe, S. S. Ravi, Daniel J. Rosenkrantz, Richard E. Stearns
Format: Article
Language:English
Published: Discrete Mathematics & Theoretical Computer Science 2003-01-01
Series:Discrete Mathematics & Theoretical Computer Science
Subjects:
computational complexity
discrete dynamical systems
cellular automata
predecessor existence
permutation existence
[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
[math.math-co] mathematics [math]/combinatorics [math.co]
[nlin.nlin-cg] nonlinear sciences [physics]/cellular automata and lattice gases [nlin.cg]
Online Access:https://dmtcs.episciences.org/2314/pdf

Internet

https://dmtcs.episciences.org/2314/pdf

Similar Items