  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.
