Profiles of dynamical systems and their algebra

08/03/2020
βˆ™
by   Caroline Gaze-Maillot, et al.
βˆ™
0
βˆ™

The commutative semiring 𝐃 of finite, discrete-time dynamical systems was introduced in order to study their (de)composition from an algebraic point of view. However, many decision problems related to solving polynomial equations over 𝐃 are intractable (or conjectured to be so), and sometimes even undecidable. In order to take a more abstract look at those problems, we introduce the notion of β€œtopographic” profile of a dynamical system (A,f) with state transition function f A β†’ A as the sequence prof A = (|A|_i)_i βˆˆβ„•, where |A|_i is the number of states having distance i, in terms of number of applications of f, from a limit cycle of (A,f). We prove that the set of profiles is also a commutative semiring (𝐏,+,Γ—) with respect to operations compatible with those of 𝐃 (namely, disjoint union and tensor product), and investigate its algebraic properties, such as its irreducible elements and factorisations, as well as the computability and complexity of solving polynomial equations over 𝐏.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset