The Shortest Identities for Max-Plus Automata with Two States

Marianne Johnson, Laure Daviaud

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    8 Downloads (Pure)


    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.
    Original languageEnglish
    Title of host publicationLeibniz International Proceedings in Informatics
    Subtitle of host publicationProceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
    Number of pages13
    Publication statusPublished - 1 Dec 2017

    Publication series

    NameLeibniz International Proceedings in Informatics
    ISSN (Electronic)1868-8969


    Dive into the research topics of 'The Shortest Identities for Max-Plus Automata with Two States'. Together they form a unique fingerprint.

    Cite this