The shortest identities for max-plus automata with two states

Daviaud, Laure and Johnson, Marianne (2017) The shortest identities for max-plus automata with two states. In: 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017. Leibniz International Proceedings in Informatics, LIPIcs . Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, DNK. ISBN 9783959770460

Full text not available from this repository.

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.

Item Type:	Book Section
Additional Information:	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: © Laure Daviaud and Marianne Johnson; licensed under Creative Commons License CC-BY.
Uncontrolled Keywords:	identities,max-plus automata,tropical matrices,weighted automata,software ,/dk/atira/pure/subjectarea/asjc/1700/1712
Related URLs:	http://www.scopus.com/inward/record.url?...
Depositing User:	LivePure Connector
Date Deposited:	08 Jun 2023 14:30
Last Modified:	08 Jun 2023 14:30
URI:	https://ueaeprints.uea.ac.uk/id/eprint/92343
DOI:	10.4230/LIPIcs.MFCS.2017.48

Actions (login required)

View Item