The Shortest Identities for Max-Plus Automata with Two States.

Daviaud, L. & Johnson, M. (2017). The Shortest Identities for Max-Plus Automata with Two States. In: Larsen, Kim G, Bodlaender, Hans L & Raskin, Jean-François (Eds.), 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), 83. (48:1-48:13). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-046-0

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.

Publication Type:	Conference or Workshop Item (Paper)
Additional Information:	© Laure Daviaud and Marianne Johnson; licensed under Creative Commons License CC-BY
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments:	School of Science & Technology > Computer Science