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). 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), 21 -25 August 2017, Aalborg, Denmark.
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 |
Available under License Creative Commons: Attribution 3.0.
Download (477kB) | Preview
Export
Downloads
Downloads per month over past year
Metadata
MetadataActions (login required)
Admin Login