Equivalence Testing of Weighted Automata over Partially Commutative Monoids

We study the 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 edge cover number of the non-commutation 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 equivalence testing of k-tape weighted 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 equivalence testing of weighted automata over such monoids. Our results are obtained by designing efficient zero testing algorithms for weighted automata over such pc monoids.

Authors

• Rajit Datta

Keywords

No keywords are indexed for this paper.