Complexity of Local, Global and Universality Properties in Finite Dynamical Systems

Description

In this paper we study the complexity of the decision problems about generic properties on the dynamics of finite discrete dynamical systems (fDDS). Properties are grouped into two main classes : local and global. Local properties are at most in , while global ones are at most in PSPACE. We also investigate universality (w.r.t. simulation) and we provide a constructive example of universal fDDS for the family of additive fDDS having a unique global attractor. The question of the complexity of deciding universality for a given family of fDDS is left open.

Abstract

International audience

Additional details