文章基本信息

标题：The Shortest Identities for Max-Plus Automata with Two States
本地全文：下载
作者：Laure Daviaud ; Marianne Johnson
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：83
页码：48:1-48:13
DOI：10.4230/LIPIcs.MFCS.2017.48
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Max-plus automata; Weighted automata; Identities; Tropical matrices