论文标题
＃计数更新Digraphs，仙人掌和串联平行分解方法的P完整性
#P-completeness of counting update digraphs, cacti, and a series-parallel decomposition method
论文作者
论文摘要
自动机网络是相互作用实体的非常通用的模型，并应用于基因调节等生物学现象。在许多情况下，实体更新其状态的顺序尚不清楚，并且动态可能对此更新时间表的变化非常敏感。自Aracena等人的作品以来。 al，众所周知，更新挖掘是研究非等效块序列更新时间表的相关对象。我们证明，计算给定网络同步敏感性的等效类的数量是＃p-complete。然而，由于分解方法，在准季度的仙人掌和定向的串联平行图中，该问题仍然可以计算。
Automata networks are a very general model of interacting entities, with applications to biological phenomena such as gene regulation. In many contexts, the order in which entities update their state is unknown, and the dynamics may be very sensitive to changes in this schedule of updates. Since the works of Aracena et. al, it is known that update digraphs are pertinent objects to study non-equivalent block-sequential update schedules. We prove that counting the number of equivalence classes, that is a tight upper bound on the synchronism sensitivity of a given network, is #P-complete. The problem is nevertheless computable in quasi-quadratic time for oriented cacti, and for oriented series-parallel graphs thanks to a decomposition method.
