City Research Online

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


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
Text - Published Version
Available under License Creative Commons: Attribution 3.0.

Download (477kB) | Preview



Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login