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.
@InProceedings{daviaud_et_al:LIPIcs.MFCS.2017.48, author = {Daviaud, Laure and Johnson, Marianne}, title = {{The Shortest Identities for Max-Plus Automata with Two States}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {48:1--48:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.48}, URN = {urn:nbn:de:0030-drops-81048}, doi = {10.4230/LIPIcs.MFCS.2017.48}, annote = {Keywords: Max-plus automata, Weighted automata, Identities, Tropical matrices} }
Feedback for Dagstuhl Publishing