Document Open Access Logo

Equivalence Testing of Weighted Automata over Partially Commutative Monoids

Authors V. Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.10.pdf
  • Filesize: 0.67 MB
  • 15 pages

Document Identifiers

Author Details

V. Arvind
  • Institute of Mathematical Sciences (HBNI), Chennai,India
Abhranil Chatterjee
  • Institute of Mathematical Sciences (HBNI), Chennai, India
Rajit Datta
  • Chennai Mathematical Institute, India
Partha Mukhopadhyay
  • Chennai Mathematical Institute, India

Acknowledgements

We thank the anonymous reviewers for their helpful feedback.

Cite As Get BibTex

V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay. Equivalence Testing of Weighted Automata over Partially Commutative Monoids. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.10

Abstract

Motivated by equivalence testing of k-tape 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 non-commutation graph of the monoid.
Specifically, if the edge clique cover number of the non-commutation graph of the pc monoid is a constant, we obtain a deterministic quasi-polynomial time algorithm for equivalence testing. As a corollary, we obtain the first deterministic quasi-polynomial time algorithms for equivalence testing of k-tape weighted automata and for equivalence testing of deterministic k-tape automata for constant k. Prior to this, the best complexity upper bound for these k-tape automata problems were randomized polynomial-time, shown by Worrell [James Worrell, 2013]. Finding a polynomial-time deterministic algorithm for equivalence testing of deterministic k-tape 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 non-commutation graphs have an edge cover consisting of at most k cliques and star graphs for any constant k. We obtain a randomized polynomial-time algorithm for equivalence testing of weighted automata over such monoids.
Our results are obtained by designing efficient zero-testing algorithms for weighted automata over such pc monoids.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
  • Theory of computation
Keywords
  • Weighted Automata
  • Automata Equivalence
  • Partially Commutative Monoid

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Manindra Agrawal, Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Hitting-sets for ROABP and sum of set-multilinear circuits. SIAM J. Comput., 44(3):669-697, 2015. URL: https://doi.org/10.1137/140975103.
  2. A. S. Amitsur and J. Levitzki. Minimal identities for algebras. Proceedings of the American Mathematical Society, 1(4):449-463, 1950. URL: http://www.jstor.org/stable/2032312.
  3. C. Beeri. An improvement on Valiant’s decision procedure for equivalence of deterministic finite turn pushdown machines. Theoretical Computer Science, 3(3):305-320, 1976. URL: https://doi.org/10.1016/0304-3975(76)90049-9.
  4. J. Berstel and C. Reutenauer. Noncommutative Rational Series with Applications. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2011. Google Scholar
  5. Malcolm Bird. The equivalence problem for deterministic two-tape automata. J. Comput. Syst. Sci., 7(2):218-236, 1973. URL: https://doi.org/10.1016/S0022-0000(73)80045-5.
  6. Mireille Clerbout, Michel Latteux, and Yves Roos. Decomposition of partial commutations. In Mike Paterson, editor, Automata, Languages and Programming, 17th International Colloquium, ICALP90, Warwick University, England, UK, July 16-20, 1990, Proceedings, volume 443 of Lecture Notes in Computer Science, pages 501-511. Springer, 1990. URL: https://doi.org/10.1007/BFb0032054.
  7. Richard A. Demillo and Richard J. Lipton. A probabilistic remark on algebraic program testing. Information Processing Letters, 7(4):193-195, 1978. URL: https://doi.org/10.1016/0020-0190(78)90067-4.
  8. Volker Diekert. Combinatorics on Traces, volume 454 of Lecture Notes in Computer Science. Springer, 1990. URL: https://doi.org/10.1007/3-540-53031-2.
  9. Volker Diekert, Markus Lohrey, and Alexander Miller. Partially commutative inverse monoids. In Rastislav Kralovic and Pawel Urzyczyn, editors, Mathematical Foundations of Computer Science 2006, 31st International Symposium, MFCS 2006, Stará Lesná, Slovakia, August 28-September 1, 2006, Proceedings, volume 4162 of Lecture Notes in Computer Science, pages 292-304. Springer, 2006. URL: https://doi.org/10.1007/11821069_26.
  10. Manfred Droste and Paul Gastin. On recognizable and rational formal power series in partially commuting variables. In Pierpaolo Degano, Roberto Gorrieri, and Alberto Marchetti-Spaccamela, editors, Automata, Languages and Programming, 24th International Colloquium, ICALP'97, Bologna, Italy, 7-11 July 1997, Proceedings, volume 1256 of Lecture Notes in Computer Science, pages 682-692. Springer, 1997. URL: https://doi.org/10.1007/3-540-63165-8_222.
  11. Samuel Eilenberg. Automata, Languages, and Machines (Vol A). Pure and Applied Mathematics. Academic Press, 1974. Google Scholar
  12. Michael A. Forbes and Amir Shpilka. Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 243-252, 2013. URL: https://doi.org/10.1109/FOCS.2013.34.
  13. Emily P. Friedman and Sheila A. Greibach. A polynomial time algorithm for deciding the equivalence problem for 2-tape deterministic finite state acceptors. SIAM J. Comput., 11:166-183, 1982. Google Scholar
  14. T. V. Griffiths. The unsolvability of the equivalence problem for nondeterministic generalized machines. J. ACM, 15(3):409-413, 1968. URL: https://doi.org/10.1145/321466.321473.
  15. Tero Harju and Juhani Karhumäki. The equivalence problem of multitape finite automata. Theor. Comput. Sci., 78(2):347-355, 1991. URL: https://doi.org/10.1016/0304-3975(91)90356-7.
  16. Antoni W. Mazurkiewicz. Trace theory. In Petri Nets: Central Models and Their Properties, Advances in Petri Nets 1986, Part II, Proceedings of an Advanced Course, Bad Honnef, Germany, 8-19 September 1986, pages 279-324, 1986. URL: https://doi.org/10.1007/3-540-17906-2_30.
  17. Noam Nisan. Lower bounds for non-commutative computation (extended abstract). In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, pages 410-418, 1991. URL: https://doi.org/10.1145/103418.103462.
  18. Ran Raz and Amir Shpilka. Deterministic polynomial identity testing in non-commutative models. Computational Complexity, 14(1):1-19, 2005. URL: https://doi.org/10.1007/s00037-005-0188-8.
  19. M.P. Schützenberger. On the definition of a family of automata. Information and Control, 4(2):245-270, 1961. URL: https://doi.org/10.1016/S0019-9958(61)80020-X.
  20. Jacob T. Schwartz. Fast probabilistic algorithm for verification of polynomial identities. J. ACM., 27(4):701-717, 1980. Google Scholar
  21. W. Tzeng. A polynomial-time algorithm for the equivalence of probabilistic automata. SIAM Journal on Computing, 21(2):216-227, 1992. Google Scholar
  22. Leslie G. Valiant. The equivalence problem for deterministic finite-turn pushdown automata. Information and Control, 25(2):123-133, 1974. URL: https://doi.org/10.1016/S0019-9958(74)90839-0.
  23. Stefano Varricchio. On the decidability of equivalence problem for partially commutative rational power series. Theor. Comput. Sci., 99(2):291-299, 1992. URL: https://doi.org/10.1016/0304-3975(92)90354-I.
  24. James Worrell. Revisiting the equivalence problem for finite multitape automata. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II, pages 422-433, 2013. URL: https://doi.org/10.1007/978-3-642-39212-2_38.
  25. R. Zippel. Probabilistic algorithms for sparse polynomials. In Proc. of the Int. Sym. on Symbolic and Algebraic Computation, pages 216-226, 1979. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact