论文标题
在有限动力学系统的半段中进行分解
Factorisation in the semiring of finite dynamical systems
论文作者
论文摘要
有限的动态系统（FDSS）通常用于建模具有有限数量的确定性和离散时间步骤的有限状态的系统。考虑到同构，它们对应于功能图。因此，FDS具有总和和产品操作，对应于其各自图的直接总和和直接乘积；然后，使用这些操作的FDS的集合形成了半度。 FDSS产品的代数结构特别有趣。例如，只有当它由两个并行运行的子系统组成时，才可以分解FD。在这项工作中，我们进一步理解了FDS的分解，分裂和根系发现问题。首先，如果一个人可以明确划分，即$ ax = ay $表示$ x = y $。我们证明，只有当它具有fixpoint时，FDS $ a $才具有取消性。其次，我们证明，如果fds $ a $具有$ k $ - th root（即$ b $，则$ b^k = a $），那么它是唯一的。第三，与整数不同，FDS产品的单型物体没有将独特的分解为不可减数。相反，我们表现出大量具有独特分解的FDS的单型FDS。为了获得我们的主要结果，我们介绍了FD的展开，可以将其视为系统的时空扩展。这使我们可以与（可能是无限的）树一起工作，在该树木中，该产品比其FDSs更容易处理。
Finite dynamical systems (FDSs) are commonly used to model systems with a finite number of states that evolve deterministically and at discrete time steps. Considered up to isomorphism, those correspond to functional graphs. As such, FDSs have a sum and product operation, which correspond to the direct sum and direct product of their respective graphs; the collection of FDSs endowed with these operations then forms a semiring. The algebraic structure of the product of FDSs is particularly interesting. For instance, an FDS can be factorised if and only if it is composed of two sub-systems running in parallel. In this work, we further the understanding of the factorisation, division, and root finding problems for FDSs. Firstly, an FDS $A$ is cancellative if one can divide by it unambiguously, i.e. $AX = AY$ implies $X = Y$. We prove that an FDS $A$ is cancellative if and only if it has a fixpoint. Secondly, we prove that if an FDS $A$ has a $k$-th root (i.e. $B$ such that $B^k = A$), then it is unique. Thirdly, unlike integers, the monoid of FDS product does not have unique factorisation into irreducibles. We instead exhibit a large class of monoids of FDSs with unique factorisation. To obtain our main results, we introduce the unrolling of an FDS, which can be viewed as a space-time expansion of the system. This allows us to work with (possibly infinite) trees, where the product is easier to handle than its counterpart for FDSs.
