Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata
Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata
复制标题
确定多项式模糊最小加自动机的无歧义性和顺序性
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
S. Lombardy
中科院分区：
文献类型：
--
作者：
D. Kirsten;S. Lombardy
本文解决了多项式模糊最小加自动机的不模糊性和顺序性问题。通过一个涉及所谓的超迁移的可决代数刻划和有限半群结构理论结果的应用，证明了这一结果。值得注意的是，对于多项式二义自动机，等价问题是不可判定的。
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.