Computing the Rabin Index of a Parity Automaton
Computing the Rabin Index of a Parity Automaton
复制标题
计算奇偶校验自动机的拉宾指数
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
Ramón Maceiras
中科院分区：
文献类型：
--
作者：
Olivier Carton;Ramón Maceiras
由一个具有n个状态的奇偶自动机给出的无限词的有理语言的拉宾指数在时间上是可计算的O（n（2）c），其中c是字母的基数。奇偶性接受条件所使用的值的数量总是大于拉宾指数，相反，奇偶性自动机的接受条件总是可以被一个等价的接受条件所取代，其所使用的值的数量正好是拉宾指数。时间复杂度为O（n（2））。
The Rabin index of a rational language of infinite words given by a parity automaton with n states is computable in time O(n(2)c) where c is the cardinality of the alphabet. The number of values used by a parity acceptance condition is always greater than the Rabin index and conversely, the acceptance condition of a parity automaton can always be replaced by an equivalent acceptance condition whose number of used values is exactly the Rabin index. This new acceptance condition can also be computed in time O(n(2)C).