Computing the Rabin index of a parity automaton

Authors
Carton, O Maceiras, R
Citation
O. Carton et R. Maceiras, Computing the Rabin index of a parity automaton, RAIRO-INF, 33(6), 1999, pp. 495-505
Citations number
15
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS
ISSN journal
09883754 → ACNP
Volume
33
Issue
6
Year of publication
1999
Pages
495 - 505
Database
ISI
SICI code
0988-3754(199911/12)33:6<495:CTRIOA>2.0.ZU;2-9
Abstract
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 cardi nality of the alphabet. The number of values used by a parity acceptance co ndition is always greater than the Rabin index and conversely, the acceptan ce 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).