Factorisation in the semiring of finite dynamical systems

Naquin, Émile; Gadouleau, Maximilien

Abstract

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 𝐴 is cancellative if one can divide by it unambiguously, i.e. 𝐴𝑋 = 𝐴𝑌 implies 𝑋 = 𝑌 . We prove that an FDS 𝐴 is cancellative if and only if it has a fixed point. Secondly, we prove that if an FDS 𝐴 has a 𝑘-th root (i.e. 𝐵 such that 𝐵𝑘 = 𝐴), 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.

Citation

Naquin, É., & Gadouleau, M. (2024). Factorisation in the semiring of finite dynamical systems. Theoretical Computer Science, 998, Article 114509. https://doi.org/10.1016/j.tcs.2024.114509

• Journal Article Type: Article
• Acceptance Date: Mar 13, 2024
• Online Publication Date: Mar 28, 2024
• Publication Date: 2024-06
• Deposit Date: May 9, 2024
• Publicly Available Date: May 9, 2024
• Journal: Theoretical Computer Science
• Print ISSN: 0304-3975
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 998
• Article Number: 114509
• DOI: https://doi.org/10.1016/j.tcs.2024.114509
• Public URL: https://durham-repository.worktribe.com/output/2435886