On Synchronizing Unambiguous Automata
On Synchronizing Unambiguous Automata
复制标题
关于同步明确自动机
DOI：
10.1016/0304-3975(88)90114-4
复制
发表时间：
1988
影响因子：
1.1
通讯作者：
A. Carpi
中科院分区：
文献类型：
--
作者：
A. Carpi
本文给出了一个过渡幺半群不含空关系的可迁n态无二义性自动机中最小秩最短字长度的多项式上界。特别地，在n状态同步明确自动化中，存在长度小于1 2 n 3的同步字。
We give a polynomial upper bound for the length of the shortest word of minimal rank in a transitive n-state unambiguous automation whose transition monoid does not contain the null relation. In particular, in an n-state synchronizing unambiguous automation there is a synchronizing word of length less than 1 2 n 3.