Computing the Rabin Index of a Parity Automaton
Olivier Carton; Ramón Maceiras
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 33, Issue: 6, page 495-505
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topCarton, Olivier, and Maceiras, Ramón. "Computing the Rabin Index of a Parity Automaton." RAIRO - Theoretical Informatics and Applications 33.6 (2010): 495-505. <http://eudml.org/doc/222006>.
@article{Carton2010,
abstract = {
The Rabin index of a rational language of infinite words given by a
parity automaton with n states is computable in time O(n2c) 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(n2c).
},
author = {Carton, Olivier, Maceiras, Ramón},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Rabin index; parity automaton},
language = {eng},
month = {3},
number = {6},
pages = {495-505},
publisher = {EDP Sciences},
title = {Computing the Rabin Index of a Parity Automaton},
url = {http://eudml.org/doc/222006},
volume = {33},
year = {2010},
}
TY - JOUR
AU - Carton, Olivier
AU - Maceiras, Ramón
TI - Computing the Rabin Index of a Parity Automaton
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 33
IS - 6
SP - 495
EP - 505
AB -
The Rabin index of a rational language of infinite words given by a
parity automaton with n states is computable in time O(n2c) 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(n2c).
LA - eng
KW - Rabin index; parity automaton
UR - http://eudml.org/doc/222006
ER -
References
top- J.R. Büchi, On a decision method in the restricted second-order arithmetic, in Proc. Int. Congress Logic, Methodology and Philosophy of science, Berkeley 1960, Stanford University Press (1962) 1-11.
- O. Carton, Chain automata. Theoret. Comput. Sci.161 (1996) 191-203.
- E.A. Emerson and C.S. Jutla, Tree automata, Mu-calculus and determinacy, in Proc. 32th Symp. on Foundations of Computer Science (1991) 368-377.
- S.C. Krishnan, A. Puri and R.K. Brayton, Structural complexity of ω-languages, in STACS '95, Springer-Verlag, Lectures Notes in Comput. Sci.900 (1995) 143-156.
- R. McNaughton, Testing and generating infinite sequences by a finite automaton. Inform. Control9 (1966) 521-530.
- A. Mostowski Regular expressions for infinite trees and a standard form for automata, in Computation theory, A. Skowron, Ed., Springer-Verlag, Berlin, Lectures Notes in Comput. Sci.208 (1984) 157-168.
- A. Mostowski, Hierarchies of weak automata and weak monadic formulas. Theoret. Comput. Sci.83 (1991) 323-335.
- D. Muller, Infinite sequences and finite machines, in Switching Theory and Logical Design, P. of Fourth Annual IEEE Symp., Ed. (1963) 3-16.
- M.O. Rabin, Decidability of second-order theories and automata on infinite trees. Trans. Amer. Math. Soc.141 (1969) 1-35.
- R.E. Tarjan, Depth first search and linear graphs. SIAM J. Comput.1 (1972) 146-160.
- W. Thomas, Automata on infinite objects, in Handbook of Theoretical Computer Science, J. van Leeuwen, Ed., B (Elsevier, 1990) Chapter 4, pp. 133-191.
- K. Wagner, Eine topologische Charakteriesierung einiger Klassen regulärer Folgenmengen. Elektron. Informationsverarb. Kybernet.13 (1977) 505-519.
- K. Wagner, On ω-regular sets. Inform. Control43 (1979) 123-177.
- T. Wilke and H. Yoo, Computing the Wadge degree, the Lipschitz degree, and the Rabin index of a regular language of infinite words in polynomial time, in Trees in Algebra and Programming - CAAP '95 P. M. et al., Ed., Springer-Verlag, Lectures Notes in Comput. Sci.915 (1995) 288-302.
- T. Wilke and H. Yoo, Computing the Rabin index of a regular language of infinite words. Inform. Comput.130 (1996) 61-70.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.