Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-16T02:29:16.404Z Has data issue: false hasContentIssue false

Computing the Rabin Indexof a Parity Automaton

Published online by Cambridge University Press:  15 August 2002

Olivier Carton
Affiliation:
Institut Gaspard Monge, Université de Marne-la-Vallée, 5 boulevard Descartes, Champs-sur-Marne, 77454 Marne-la-Vallée Cedex 2, France; Olivier.Carton@univ-mlv.fr.
Ramón Maceiras
Affiliation:
Institut Gaspard Monge, Université de Marne-la-Vallée, 5 boulevard Descartes, Champs-sur-Marne, 77454 Marne-la-Vallée Cedex 2, France; Olivier.Carton@univ-mlv.fr.
Get access

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 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).

Keywords

Information

Type
Research Article
Copyright
© EDP Sciences, 1999

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable