2020/02/20 by V. Arvind, Abhranil Chatterjee, Arvind, V. +5
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL
paper · pdf · doi:10.48550/arxiv.2002.08633
arxiv created 2020/05/31 · arxiv updated 2020/06/02
We study 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.