The Shortest Identities for Max-Plus Automata with Two States

Authors Laure Daviaud, Marianne Johnson



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.48.pdf
  • Filesize: 466 kB
  • 13 pages

Document Identifiers

Author Details

Laure Daviaud
Marianne Johnson

Cite AsGet BibTex

Laure Daviaud and Marianne Johnson. The Shortest Identities for Max-Plus Automata with Two States. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 48:1-48:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.MFCS.2017.48

Abstract

Max-plus automata are quantitative extensions of automata designed to associate an integer with every non-empty word. A pair of distinct words is said to be an identity for a class of max-plus automata if each of the automata in the class computes the same value on the two words. We give the shortest identities holding for the class of max-plus automata with two states. For this, we exhibit an interesting list of necessary conditions for an identity to hold. Moreover, this result provides a counter-example of a conjecture of Izhakian, concerning the minimality of certain identities.
Keywords
  • Max-plus automata
  • Weighted automata
  • Identities
  • Tropical matrices

Metrics

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

References

  1. Y. Chen, X. Hu, Y. Luo, and O. Sapir. The finite basis problem for the monoid of two-by-two upper triangular tropical matrices. Bull. Aust. Math. Soc., 94(1):54-64, 2016. URL: http://dx.doi.org/10.1017/S0004972715001483.
  2. T. Colcombet, L. Daviaud, and F. Zuleger. Size-change abstraction and max-plus automata. In Erzsébet Csuhaj-Varjú, Martin Dietzfelbinger, and Zoltán Ésik, editors, Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part I, volume 8634 of Lecture Notes in Computer Science, pages 208-219. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44522-8_18.
  3. L. Daviaud, M. Johnson, and M. Kambites. Identities in upper triangular tropical matrix semigroups and the bicyclic monoid, 2017. preprint, http://arxiv.org/abs/1612.04219. Google Scholar
  4. S. Gaubert. Performance evaluation of (max,+) automata. IEEE Trans. Automat. Control, 40(12):2014-2025, 1995. URL: http://dx.doi.org/10.1109/9.478227.
  5. S. Gaubert and J. Mairesse. Modeling and analysis of timed Petri nets using heaps of pieces. IEEE Trans. Automat. Control, 44(4):683-697, 1999. URL: http://dx.doi.org/10.1109/9.754807.
  6. Z. Izhakian. Semigroup identities in the monoid of triangular tropical matrices. Semigroup Forum, 88(1):145-161, 2014. URL: http://dx.doi.org/10.1007/s00233-013-9507-6.
  7. Z. Izhakian. Erratum to: Semigroup identities in the monoid of triangular tropical matrices [ MR3164156]. Semigroup Forum, 92(3):733, 2016. URL: http://dx.doi.org/10.1007/s00233-016-9790-0.
  8. Z. Izhakian. Semigroup identities of tropical matrix semigroups of maximal rank. Semigroup Forum, 92(3):712-732, 2016. URL: http://dx.doi.org/10.1007/s00233-015-9765-6.
  9. Z. Izhakian and S. W. Margolis. Semigroup identities in the monoid of two-by-two tropical matrices. Semigroup Forum, 80(2):191-218, 2010. URL: http://dx.doi.org/10.1007/s00233-009-9203-8.
  10. J. Okniński. Identities of the semigroup of upper triangular tropical matrices. Comm. Algebra, 43(10):4422-4426, 2015. URL: http://dx.doi.org/10.1080/00927872.2014.946141.
  11. J. Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009. Google Scholar
  12. M. P. Schützenberger. On the definition of a family of automata. Information and Control, 4:245-270, 1961. Google Scholar
  13. Y. Shitov. A semigroup identity for tropical 3×3 matrices, 2014. To appear in Ars Mathematica Contemporanea 14 (2018), 15-23. 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