论文标题
动态系统及其代数的轮廓
Profiles of dynamical systems and their algebra
论文作者
论文摘要
引入了有限的离散时间动力系统的交换性半\ mathbf {d} $，以便从代数的角度研究其（de）组成。但是，许多与$ \ mathbf {d} $求解多项式方程式有关的决策问题是棘手的（或猜想是如此），有时甚至是不可决定的。为了更抽象地看这些问题，我们介绍了动态系统$（a，f）$的“地形”概念，并带有状态过渡函数$ f \ colon a \ a $作为序列$ \ mathop {\ mathop {\ mathrm {prof}}从$ f $的申请数量（a，f）$的限制周期中，具有距离$ i $的状态数量。 We prove that the set of profiles is also a commutative semiring $(\mathbf{P},+,\times)$ with respect to operations compatible with those of $\mathbf{D}$ (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 $ \ mathbf {p} $的方程式。
The commutative semiring $\mathbf{D}$ 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 $\mathbf{D}$ 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 \colon A \to A$ as the sequence $\mathop{\mathrm{prof}} A = (|A|_i)_{i \in \mathbb{N}}$, 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 $(\mathbf{P},+,\times)$ with respect to operations compatible with those of $\mathbf{D}$ (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 $\mathbf{P}$.
