Equivalence Testing of Weighted Automata over Partially Commutative Monoids

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...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-05
Main Authors: Arvind, V, Chatterjee, Abhranil, Datta, Rajit, Mukhopadhyay, Partha
Format: Article
Language:English
Subjects:
Algorithms
Commutation
Equivalence
Graphs
Monoids
Polynomials
Randomization
Traveling salesman problem
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422