@inproceedings{fd42d9bc975e4b0ab3fb820e2b297b36,
title = "The shortest identities for max-plus automata with two states",
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 = "Identities, Max-plus automata, Tropical matrices, Weighted automata",
author = "Laure Daviaud and Marianne Johnson",
note = "Funding Information: ∗ This work was partially supported by the LIPA project, funded by the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No 683080). Publisher Copyright: {\textcopyright} Laure Daviaud and Marianne Johnson; licensed under Creative Commons License CC-BY.; 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017 ; Conference date: 21-08-2017 Through 25-08-2017",
year = "2017",
month = nov,
day = "1",
doi = "10.4230/LIPIcs.MFCS.2017.48",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Larsen, {Kim G.} and Jean-Francois Raskin and Bodlaender, {Hans L.}",
booktitle = "42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017",
}