Scholarlink

<p>Functional digraphs are unlabelled finite digraphs where each vertex has exactly one out-neighbor. They are isomorphic classes of finite discrete-time dynamical systems. Endowed with the direct sum and product, functional digraphs form a semiring with an interesting multiplicative structure. For instance, we do not know if the following division problem can be solved in polynomial time: given two functional digraphs <i>A</i> and <i>B</i>, does <i>A</i> divide <i>B</i>? That <i>A</i> divides <i>B</i> means that there exists a functional digraph <i>X</i> such that <i>AX</i> is isomorphic to <i>B</i>, and many such <i>X</i> can exist. We can thus ask for the number of solutions <i>X</i>. In this paper, we focus on the case where <i>B</i> is a sum of cycles (a disjoint union of cycles, corresponding to the limit behavior of finite discrete-time dynamical systems). There is then a naïve sub-exponential algorithm to compute the non-isomorphic solutions <i>X</i>, and our main result is an improvement of this algorithm which has the property to be polynomial when <i>A</i> is fixed. It uses a divide-and-conquer technique that should be useful for further developments on the division problem.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Dividing sum of cycles in the semiring of functional digraphs

  • 期刊论文

  • 发表日期：

    2026年2月19日

查看全文
  • Florian Bridoux,
  • Christophe Crespelle,
  • Thi Ha Duong Phan,
  • Adrien Richard

摘要

Functional digraphs are unlabelled finite digraphs where each vertex has exactly one out-neighbor. They are isomorphic classes of finite discrete-time dynamical systems. Endowed with the direct sum and product, functional digraphs form a semiring with an interesting multiplicative structure. For instance, we do not know if the following division problem can be solved in polynomial time: given two functional digraphs A and B, does A divide B? That A divides B means that there exists a functional digraph X such that AX is isomorphic to B, and many such X can exist. We can thus ask for the number of solutions X. In this paper, we focus on the case where B is a sum of cycles (a disjoint union of cycles, corresponding to the limit behavior of finite discrete-time dynamical systems). There is then a naïve sub-exponential algorithm to compute the non-isomorphic solutions X, and our main result is an improvement of this algorithm which has the property to be polynomial when A is fixed. It uses a divide-and-conquer technique that should be useful for further developments on the division problem.