文章基本信息

标题：Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata
本地全文：下载
作者：Daniel Kirsten ; Sylvain Lombardy
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2009
卷号：3
页码：589-600
DOI：10.4230/LIPIcs.STACS.2009.1850
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：This paper solves the unambiguity and the sequentiality problem for polynomially ambiguous min-plus automata. This result is proved through a decidable algebraic characterization involving so-called metatransitions and an application of results from the structure theory of finite semigroups. It is noteworthy that the equivalence problem is known to be undecidable for polynomially ambiguous automata.
关键词：Min-plus automata; Determinization; Finite semigroups