Equivalence Testing of Weighted Automata over Partially Commutative Monoids

DOI10.4230/LIPICS.MFCS.2021.10MaRDI QIDQ6168419zbMATH OpenOpenAlexFDO

Authors Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay

Publication date 8 August 2023

Full work available at URL https://arxiv.org/abs/2002.08633

zbMATH Keywords

automata equivalencepartially commutative monoidweighted automata

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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

Recommendations

• On the Complexity of Equivalence and Minimisation for Q-weighted Automata
• Revisiting the equivalence problem for finite multitape automata
• The equivalence problem of multitape finite automata
• On deterministic weighted automata

This page was built for publication: Equivalence Testing of Weighted Automata over Partially Commutative Monoids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6168419)