Predecessor and Permutation Existence Problems for Sequential Dynamical Systems.

DMTCS Proceedings, Discrete Models for Complex Systems, DMCS'03

Predecessor and Permutation Existence Problems for Sequential Dynamical Systems.

Christopher L. Barrett, Harry B. HuntIII, Madhav V. Marathe, S. S. Ravi, Daniel J. Rosenkrantz, Richard E. Stearns

Abstract

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.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page