论文标题
在部分交换性单体上对加权自动机进行等效性测试
Equivalence Testing of Weighted Automata over Partially Commutative Monoids
论文作者
论文摘要
我们研究自动机对部分交换性单体（PC单体）对自动机进行的\ EMPH {多样性等效性}，并在特殊情况下显示出有效的算法，利用了单型基础的基础非信誉图的结构。 具体而言，如果PC MONOID的非信誉图（覆盖图的最小数量覆盖图的最小数量）的集合覆盖率是常数，则我们获得了确定性的准多项式时间算法。结果，我们还获得了第一个确定性的准多项式时间算法，用于$ k $ -tape automata的多重等效性测试以及用于常数$ k $的确定性$ k $ -tape automata的等效测试。在此之前，Worrell [ICALP 2013]显示了上述问题的随机多项式算法。 我们还考虑了PC MONOIDS，其覆盖范围的无通用图最多由$ k $ cliques和star Graphs组成，以适用于任何常数$ k $。我们获得了随机多项式时间算法，用于在此类单体上对自动机进行多重性测试。
We study \emph{multiplicity equivalence} testing of automata over partially commutative monoids (pc monoids) and show efficient algorithms in special cases, exploiting the structure of the underlying non-commutation graph of the monoid. Specifically, if the clique cover number of the non-commutation graph (the minimum number of cliques covering the graph) of the pc monoid is a constant, we obtain a deterministic quasi-polynomial time algorithm. As a consequence, we also obtain the first deterministic quasi-polynomial time algorithms for multiplicity equivalence testing of $k$-tape automata and for equivalence testing of deterministic $k$-tape automata for constant $k$. Prior to this, a randomized polynomial-time algorithm for the above problems was shown by Worrell [ICALP 2013]. We also consider pc monoids for which the non-commutation graphs have cover consisting of at most $k$ cliques and star graphs for any constant $k$. We obtain randomized polynomial-time algorithm for multiplicity equivalence testing of automata over such monoids.
