Abstract
Motivated by equivalence testing of ktape automata, we study the equivalence testing of weighted automata in the more general setting, over partially commutative monoids (in short, pc monoids), and show efficient algorithms in some special cases, exploiting the structure of the underlying noncommutation graph of the monoid.
Specifically, if the edge clique cover number of the noncommutation graph of the pc monoid is a constant, we obtain a deterministic quasipolynomial time algorithm for equivalence testing. As a corollary, we obtain the first deterministic quasipolynomial time algorithms for equivalence testing of ktape weighted automata and for equivalence testing of deterministic ktape automata for constant k. Prior to this, the best complexity upper bound for these ktape automata problems were randomized polynomialtime, shown by Worrell [James Worrell, 2013]. Finding a polynomialtime deterministic algorithm for equivalence testing of deterministic ktape automata for constant k has been open for several years [Emily P. Friedman and Sheila A. Greibach, 1982] and our results make progress.
We also consider pc monoids for which the noncommutation graphs have an edge cover consisting of at most k cliques and star graphs for any constant k. We obtain a randomized polynomialtime algorithm for equivalence testing of weighted automata over such monoids.
Our results are obtained by designing efficient zerotesting algorithms for weighted automata over such pc monoids.
BibTeX  Entry
@InProceedings{arvind_et_al:LIPIcs.MFCS.2021.10,
author = {Arvind, V. and Chatterjee, Abhranil and Datta, Rajit and Mukhopadhyay, Partha},
title = {{Equivalence Testing of Weighted Automata over Partially Commutative Monoids}},
booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
pages = {10:110:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772013},
ISSN = {18688969},
year = {2021},
volume = {202},
editor = {Bonchi, Filippo and Puglisi, Simon J.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14450},
URN = {urn:nbn:de:0030drops144503},
doi = {10.4230/LIPIcs.MFCS.2021.10},
annote = {Keywords: Weighted Automata, Automata Equivalence, Partially Commutative Monoid}
}
Keywords: 

Weighted Automata, Automata Equivalence, Partially Commutative Monoid 
Collection: 

46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) 
Issue Date: 

2021 
Date of publication: 

18.08.2021 