Computing the Rabin index of a parity automaton
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999) no. 6, pp. 495-505. 
@article{ITA_1999__33_6_495_0,
     author = {Carton, Olivier and Maceiras, Ram\'on},
     title = {Computing the {Rabin} index of a parity automaton},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {495--505},
     publisher = {EDP-Sciences},
     volume = {33},
     number = {6},
     year = {1999},
     mrnumber = {1747513},
     zbl = {0958.68089},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1999__33_6_495_0/}
}
TY  - JOUR
AU  - Carton, Olivier
AU  - Maceiras, Ramón
TI  - Computing the Rabin index of a parity automaton
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1999
SP  - 495
EP  - 505
VL  - 33
IS  - 6
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1999__33_6_495_0/
LA  - en
ID  - ITA_1999__33_6_495_0
ER  - 
%0 Journal Article
%A Carton, Olivier
%A Maceiras, Ramón
%T Computing the Rabin index of a parity automaton
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1999
%P 495-505
%V 33
%N 6
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_1999__33_6_495_0/
%G en
%F ITA_1999__33_6_495_0
Carton, Olivier; Maceiras, Ramón. Computing the Rabin index of a parity automaton. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999) no. 6, pp. 495-505. http://www.numdam.org/item/ITA_1999__33_6_495_0/

[1] 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. | MR | Zbl

[2] O. Carton, Chain automata. Theoret. Comput. Sci. 161 (1996) 191-203. | MR | Zbl

[3] 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.

[4] 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. | MR

[5] R. Mcnaughton, Testing and generating infinite sequences by a finite automaton. Inform. Control 9 (1966) 521-530. | MR | Zbl

[6] 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. | MR | Zbl

[7] A. Mostowski, Hierarchies of weak automata and weak monadic formulas. Theoret. Comput. Sci. 83 (1991) 323-335. | MR | Zbl

[8] D. Muller, Infinite sequences and finite machines, in Switching Theory and Logical Design, P. of Fourth Annual IEEE Symp., Ed. (1963) 3-16.

[9] M. O. Rabin, Decidability of second-order theories and automata on infinite trees. Trans. Amer. Math. Soc. 141 (1969) 1-35. | MR | Zbl

[10] R. E. Tarjan, Depth first search and linear graphs. SIAM J. Comput. 1 (1972) 146-160. | MR | Zbl

[11] W. Thomas, Automata on infinite objects, in Handbook of Theoretical Computer Science, J. van Leeuwen, Ed., B (Elsevier, 1990) Chapter 4, pp. 133-191. | MR | Zbl

[12] K. Wagner, Eine topologische Charakteriesierung einiger Klassen regulärer Folgenmengen. Elektron. Informationsverarb. Kybemet. 13 (1977) 505-519. | MR | Zbl

[13] K. Wagner, On ω-regular sets. Inform. Control 43 (1979) 123-177. | MR | Zbl

[14] 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 Prograrnming - CAAP '95 P. M. et al., Ed., Springer-Verlag, Lectures Notes in Comput. Sci. 915 (1995) 288-302.

[15] T. Wilke and H. Yoo, Computing the Rabin index of a regular language of infinite words. Inform. Comput. 130 (1996) 61-70. | MR | Zbl