################################################################
#   Bibio livreOmega
#   Mise a jour 12/02/01
#   reprise sous MatSci du fichier de jep
#    recu le 9/02/01
#
################################################################
# A completer :
# BuchiSiefkes73 (editeur), Carton94, CohenBrzozowski68, Denker76,
# Linna75 (pages), Lindsay2, Morse2, Simon84
#
################################################################
#
# Pour utiliser ce fichier, faire LaTeX sur le document PourBib.tex
# (afin d'obtenir le fichier PourBib.aux), puis utiliser
# BibTeX en appelant PourBib.aux (pour obtenir le fichier PourBib.bbl),
# puis LaTeX encore deux fois en mettant un % devant \cite{*}
# (une premiere fois pour trouver l'information dans le fichier
# PourBib.bbl et ensuite pour rendre correctes les references en avant).
# Dans certains cas tres rares, il peut etre necessaire de refaire 
une passe BibTeX/LaTeX.
#
################################################################

@inCollection{AbadiLamportWolper89,
   author =    {Abadi, Mart{\'\i}n and Lamport, Leslie and Wolper, Pierre},
   title =     {Realizable and unrealizable specifications of reactive systems},
   booktitle = {Automata, languages and programming (Stresa, 1989)},
   pages =     {1--17},
   publisher = {Springer},
   address =   {Berlin},
   year =      1989,
   mrclass =   {68Q60 (68Q10)},
   mrnumber =  {1 037 040},
}

@article{Adler83,
   author =   {Adler, Roy L. and Coppersmith, Don and Hassner, Martin},
   title =    {Algorithms for sliding block codes. {A}n application of symbolic 
               dynamics to information theory},
   journal =  {IEEE Trans. Inform. Theory},
   fjournal = {Institute of Electrical and Electronics Engineers. Transactions 
               on Information Theory},
   volume =   29,
   year =     1983,
   number =   1,
   pages =    {5--22},
   issn =     {0018-9448},
   coden =    {IETTAW},
   mrclass =  {94A24 (28D05 58F11)},
   mrnumber = {85b:94009},
}

@article{AdlerMarcus79,
   author =     {Adler, Roy L. and Marcus, Brian},
   title =      {Topological entropy and equivalence of dynamical systems},
   journal =    {Mem. Amer. Math. Soc.},
   fjournal =   {Memoirs of the American Mathematical Society},
   volume =     20,
   year =       1979,
   number =     219,
   pages =      {iv+84},
   issn =       {0065-9266},
   coden =      {MAMCAU},
   mrclass =    {28D20 (54H20)},
   mrnumber =   {83h:28027},
   mrreviewer = {Bruce Kitchens},
}

@article{Ajtai,
   author =     {Ajtai, Mikl{\'o}s},
   title =      {$\Sigma \sp{1}\sb{1}$-formulae on finite structures},
   journal =    {Ann. Pure Appl. Logic},
   fjournal =   {Annals of Pure and Applied Logic},
   volume =     24,
   year =       1983,
   number =     1,
   pages =      {1--48},
   issn =       {0168-0072},
   coden =      {APALD7},
   mrclass =    {03C13 (03B10 03B15 03C35)},
   mrnumber =   {85b:03048},
   mrreviewer = {A. H. Lachlan},
}

@book{AhoHopcroftUllman74,
   author =     {Aho, Alfred V. and Hopcroft, John E. and Ullman, Jeffrey D.},
   title =      {The design and analysis of computer algorithms},
   note =       {Second printing, Addison-Wesley Series in Computer Science and 
                 Information Processing},
   publisher =  {Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam},
   year =       1975,
   pages =      {x+470},
   mrclass =    {68A10 (68A20)},
   mrnumber =   {54 \#1706},
   mrreviewer = {M. Tetruasvili},
}

@book{Almeida94,
   author =    {Almeida, Jorge},
   title =     {Finite semigroups and universal algebra},
   note =      {Translated from the 1992 Portuguese original and revised by the 
                author},
   publisher = {World Scientific Publishing Co. Inc.},
   address =   {River Edge, NJ},
   year =      1994,
   pages =     {xviii+511},
   isbn =      {981-02-1895-8},
   mrclass =   {20Mxx (08-01)},
   mrnumber =  {96b:20069},
}

@article{Arnold83a,
   author =   {Arnold, Andr{\'e}},
   title =    {Rational $\omega$-languages are nonambiguous},
   journal =  {Theoret. Comput. Sci.},
   fjournal = {Theoretical Computer Science},
   volume =   26,
   year =     1983,
   number =   {1-2},
   pages =    {221--223},
   issn =     {0304-3975},
   coden =    {TCSDI},
   mrclass =  {68F10},
   mrnumber = {84m:68075},
}

@conference{Arnold83b,
   author =    {Arnold, Andr{\'e}},
   title =     {Topological characterizations of infinite behaviours of 
                transition systems},
   booktitle = {Automata, Languages and Programming},
   series =    {Lecture Notes in Computer Science},
   publisher = {Springer Verlag, Berlin, Heidelberg, New York},
   editor =    {J. Diaz},
   year =      1983,
   volume =    154,
   pages =     {28--38},
}

@inCollection{Arnold85a,
   author =     {Arnold, Andr{\'e}},
   title =      {Deterministic and nonambiguous rational $\omega$-languages},
   booktitle =  {Automata on infinite words (Le Mont-Dore, 1984)},
   pages =      {18--27},
   publisher =  {Springer},
   address =    {Berlin},
   year =       1985,
   mrclass =    {68Q45 (03D05)},
   mrnumber =   {87g:68032},
   mrreviewer = {Wolfgang Thomas},
}

@article{Arnold85b,
   author =   {Arnold, Andr{\'e}},
   title =    {A syntactic congruence for rational $\omega$-languages},
   journal =  {Theoret. Comput. Sci.},
   fjournal = {Theoretical Computer Science},
   volume =   39,
   year =     1985,
   number =   {2-3},
   pages =    {333--335},
   issn =     {0304-3975},
   coden =    {TCSDI},
   mrclass =  {68Q45},
   mrnumber = {87c:68037},
}

@article{ArnoldNiwinski90,
   author =   {Arnold, Andr{\'e} and Niwi{\'n}ski, Damian},
   title =    {Fixed point characterization of B{\"u}chi automata 
   on infinite trees},
   journal =  {J. Inf. Process. Cybern. EIK},
   volume =   26,
   year =     1990,
   pages =    {453-461},
}

@inCollection{ArnoldNiwinski92,
   author =    {Arnold, Andr{\'e} and Niwi{\'n}ski, Damian},
   title =     {Fixed point characterization of weak monadic logic definable sets 
                of trees},
   booktitle = {Tree automata and languages},
   pages =     {159--188},
   publisher = {Elsevier},
   editor =    {M. Nivat and A. Podelski},
   address =   {Amsterdam, The Netherlands},
   year =      1992,
}

@book{ArnoldNiwinski01,
   author =    {Arnold, Andr{\'e} and Niwi{\'n}ski, Damian},
   title =     {Rudiments of $\mu$-Calculus},
   publisher = {Elsevier},
   address =   {Amsterdam, The Netherlands},
   year =      2001,
   pages =     {xvii+277},
   issn =      {0049-237X},
   isbn =      {0 444 50620 9},
   mrclass =   {},
   mrnumber =  {},
}

@article{Barua92,
   author =     {Barua, Rana},
   title =      {The {H}ausdorff-{K}uratowski hierarchy of $\omega$-regular 
                 languages and a hierarchy of {M}uller automata},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     96,
   year =       1992,
   number =     2,
   pages =      {345--360},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {03D05 (03D15 68Q45 68Q70)},
   mrnumber =   {93k:03036},
   mrreviewer = {John P. Helm},
}

@book{Barwise77,
   title =     {Handbook of mathematical logic},
   editor =    {{Jon Barwise} note = {Edited with the cooperation of H. J. 
                Keisler, K. Kunen, Y. N. Moschovakis and A. S. Troelstra}},
   publisher = {North-Holland Publishing Co.},
   address =   {Amsterdam},
   series =    {Studies in Logic and the Foundations of Mathematics},
   vol =       {{90} year = 1977},
   pages =     {xi+1165},
   year =      1977,
   isbn =      {0-7204-2285-X},
   mrnumber =  {56 \#15351},
   mrclass =   {02-06},
}

@article{Beauquier84,
   author =  {Beauquier, Dani{\`e}le},
   title =   {Bi-limites de langages reconnaissables},
   journal = {Theoret. Comput. Sci.},
   year =    1984,
   volume =  33,
   pages =   {335--342},
}

@inCollection{Beauquier85,
   author =     {Beauquier, Dani{\`e}le},
   title =      {Ensembles reconnaissables de mots bi-infinis. {L}imite et 
                 d\'eterminisme},
   booktitle =  {Automata on infinite words (Le Mont-Dore, 1984)},
   pages =      {28--46},
   publisher =  {Springer},
   address =    {Berlin},
   year =       1985,
   mrclass =    {68Q45 (03D05 20M05)},
   mrnumber =   {87e:68054},
   mrreviewer = {Christine Charretton},
}

@techReport{Beauquier01,
   author =      {Beauquier, Dani{\`e}le and Rabinovich, Alexander},
   title =       {Monadic logic of order over naturals has no finite base},
   institution = {University Paris XII},
   year =        2001,
}


@inCollection{BeauquierNivat85,
   author =    {Beauquier, Dani{\`e}le and Nivat, Maurice},
   title =     {About rational sets of factors of a bi-infinite word},
   booktitle = {Automata, languages and programming (Nafplion, 1985)},
   pages =     {33--42},
   publisher = {Springer},
   address =   {Berlin},
   year =      1985,
   mrclass =   {68Q45 (20M35)},
   mrnumber =  {87c:68039},
}

@article{BeauquierPerrin84,
   author =   {Beauquier, Dani{\`e}le and Perrin, Dominique},
   title =    {Codeterministic automata on infinite words},
   journal =  {Inform. Process. Lett.},
   fjournal = {Information Processing Letters},
   volume =   20,
   year =     1985,
   number =   2,
   pages =    {95--98},
   issn =     {0020-0190},
   coden =    {IFPLAT},
   mrclass =  {68Q05 (03D05 68Q45)},
   mrnumber = {86i:68028},
}

@inCollection{BeauquierPin89,
   author =     {Beauquier, Dani{\`e}le and Pin, Jean-Eric},
   title =      {Factors of words},
   booktitle =  {Automata, languages and programming (Stresa, 1989)},
   pages =      {63--79},
   publisher =  {Springer},
   address =    {Berlin},
   year =       1989,
   mrclass =    {68Q05 (03D05 18B20)},
   mrnumber =   {91f:68037},
   mrreviewer = {Wolfgang Thomas},
}

@article{BeauquierPin91,
   author =  {Beauquier, Dani{\`e}le and Pin, Jean-Eric},
   title =   {Languages and scanners},
   journal = {Theoret. Comput. Sci.},
   year =    1991,
   volume =  84,
   pages =   {3--21},
}

@article{Bedon96,
   author =     {Bedon, Nicolas},
   title =      {Finite automata and ordinals},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     156,
   year =       1996,
   number =     {1-2},
   pages =      {119--144},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {03D05 (68Q68)},
   mrnumber =   {97d:03052},
   mrreviewer = {Zdzis{\l}aw Grodzki},
}

@article{Bedon98,
   author =     {Bedon, Nicolas},
   title =      {Automata, semigroups and recognizability of words on ordinals},
   journal =    {Internat. J. Algebra Comput.},
   fjournal =   {International Journal of Algebra and Computation},
   volume =     8,
   year =       1998,
   number =     1,
   pages =      {1--21},
   issn =       {0218-1967},
   mrclass =    {68Q70 (03D05 20M35)},
   mrnumber =   {99a:68127},
   mrreviewer = {Boris M. Schein},
}

@inCollection{BedonCarton98,
   author =    {Bedon, Nicolas and Carton, Olivier},
   title =     {An {E}ilenberg theorem for words on countable ordinals},
   booktitle = {LATIN'98: theoretical informatics (Campinas, 1998)},
   pages =     {53--64},
   publisher = {Springer},
   address =   {Berlin},
   year =      1998,
   mrclass =   {68Q70 (03D05 20M35)},
   mrnumber =  {99e:68105},
}

@book{BerlekampConwayGuy82a,
   author =     {Berlekamp, Elwyn R. and Conway, John H. and Guy, Richard K.},
   title =      {Winning ways for your mathematical plays. {V}ol. 1},
   note =       {Games in general},
   publisher =  {Academic Press Inc. [Harcourt Brace Jovanovich Publishers]},
   address =    {London},
   year =       1982,
   pages =      {xxxi+426+xi},
   isbn =       {0-12-091150-7; 0-12-091101-9},
   mrclass =    {90Dxx (05-02 90-02)},
   mrnumber =   {84h:90091a},
   mrreviewer = {Aviezri S. Fraenkel},
}

@book{BerlekampConwayGuy82b,
   author =     {Berlekamp, Elwyn R. and Conway, John H. and Guy, Richard K.},
   title =      {Winning ways for your mathematical plays. {V}ol. 2},
   note =       {Games in particular},
   publisher =  {Academic Press Inc. [Harcourt Brace Jovanovich Publishers]},
   address =    {London},
   year =       1982,
   pages =      {i--xxxiii and 429--850 and i--xix},
   isbn =       {0-12-091152-3; 0-12-091102-7},
   mrclass =    {90Dxx (05-02 90-02)},
   mrnumber =   {84h:90091b},
   mrreviewer = {Aviezri S. Fraenkel},
}

@book{BerstelPerrin85,
   author =     {Berstel, Jean and Perrin, Dominique},
   title =      {Theory of codes},
   publisher =  {Academic Press Inc.},
   address =    {Orlando, Fla.},
   year =       1985,
   pages =      {xiv+433},
   isbn =       {0-12-093420-5},
   mrclass =    {94B05 (20M05 20M35 94B35)},
   mrnumber =   {87f:94033},
   mrreviewer = {R. P. Nederpelt},
}

@article{Birkhoff35,
   author =  {Birkhoff, Garrett},
   title =   {On the structure of abstract algebras},
   journal = {Proc. Cambridge Phil. Soc.},
   year =    1935,
   volume =  31,
   pages =   {433--454},
}

@inCollection{BlanchardHansel85,
   author =    {Blanchard, Fran{\c{c}}ois and Hansel, Georges},
   title =     {Languages and subshifts},
   booktitle = {Automata on infinite words (Le Mont-Dore, 1984)},
   pages =     {138--146},
   publisher = {Springer},
   address =   {Berlin},
   year =      1985,
   mrclass =   {68Q45 (03D05 20M05)},
   mrnumber =  {87e:68056},
}

@article{BlanchardPerrin80,
   author =     {Blanchard, Fran{\c{c}}ois and Perrin, Dominique},
   title =      {Rel\`evement d'une mesure ergodique par un codage},
   journal =    {Z. Wahrsch. Verw. Gebiete},
   fjournal =   {Zeitschrift f\"ur Wahrscheinlichkeitstheorie und Verwandte 
                 Gebiete},
   volume =     54,
   year =       1980,
   number =     3,
   pages =      {303--311},
   issn =       {0044-3719},
   mrclass =    {94A15 (28D99)},
   mrnumber =   {82k:94008},
   mrreviewer = {U. Krengel},
}

@article{Bloom76,
   author =   {Bloom, Stephen L.},
   title =    {Varieties of ordered algebras},
   journal =  {J. Comput. System Sci.},
   volume =   13,
   year =     1976,
   number =   2,
   pages =    {200--212},
   mrclass =  {08A15 (06A70)},
   mrnumber = {55 \#239},
}

@article{BoassonNivat80,
   author =   {Boasson, Luc and Nivat, Maurice},
   title =    {Adherences of languages},
   journal =  {J. Comput. System Sci.},
   fjournal = {Journal of Computer and System Sciences},
   volume =   20,
   year =     1980,
   number =   3,
   pages =    {285--309},
   issn =     {0022-0000},
   coden =    {JCSSBM},
   mrclass =  {68F05},
   mrnumber = {81k:68054},
}

@book{Bourbaki74,
   author =    {Bourbaki, Nicolas},
   title =     {El{\'e}ments de math{\'e}matiques, Topologie G{\'e}n{\'e}rale},
   publisher = {CCLS, Paris},
   year =      1974,
}

@article{BoyleKitchensMarcus85,
   author =     {Boyle, Mike and Kitchens, Bruce and Marcus, Brian},
   title =      {A note on minimal covers for sofic systems},
   journal =    {Proc. Amer. Math. Soc.},
   fjournal =   {Proceedings of the American Mathematical Society},
   volume =     95,
   year =       1985,
   number =     3,
   pages =      {403--411},
   issn =       {0002-9939},
   coden =      {PAMYAR},
   mrclass =    {54H20 (58F20)},
   mrnumber =   {87d:54068},
   mrreviewer = {Karl Petersen},
}

@article{BoyleMarcusTrow87,
   author =     {Boyle, Mike and Marcus, Brian and Trow, Paul},
   title =      {Resolving maps and the dimension group for shifts of finite type},
   journal =    {Mem. Amer. Math. Soc.},
   fjournal =   {Memoirs of the American Mathematical Society},
   volume =     70,
   year =       1987,
   number =     377,
   pages =      {vi+146},
   issn =       {0065-9266},
   coden =      {MAMCAU},
   mrclass =    {28D05 (28D20 54H20 58F11)},
   mrnumber =   {89c:28019},
   mrreviewer = {Manfred Denker},
}

@article{Brown71,
   author =     {Brown, Timothy C.},
   title =      {An interesting combinatorial method in the theory of locally 
                 finite semigroups},
   journal =    {Pacific J. Math.},
   volume =     36,
   year =       1971,
   pages =      {285--289},
   mrclass =    {20.93},
   mrnumber =   {43 \#6346},
   mrreviewer = {L. Fuchs},
}

@article{Brzozowski78,
   author =     {Brzozowski, John A. and Knast, Robert},
   title =      {The dot-depth hierarchy of star-free languages is infinite},
   journal =    {J. Comput. System Sci.},
   volume =     16,
   year =       1978,
   number =     1,
   pages =      {37--55},
   mrclass =    {68A30},
   mrnumber =   {57 \#11183},
   mrreviewer = {H. Jurgensen},
}

@article{BrzozowskiSimon73,
   author =     {Brzozowski, John A. and Simon, Imre},
   title =      {Characterizations of locally testable events},
   journal =    {Discrete Math.},
   volume =     4,
   year =       1973,
   pages =      {243--271},
   mrclass =    {68A25},
   mrnumber =   {47 \#7948},
   mrreviewer = {I. Peak},
}

@article{Buchi60,
   author =  {B{\"u}chi, J. Richard},
   title =   {Weak second-order arithmetic and finite automata},
   journal = {Z. Math. Logik und Grundl. Math.},
   year =    1960,
   volume =  6,
   pages =   {66--92},
}

@inCollection{Buchi62,
   author =     {B{\"u}chi, J. Richard},
   title =      {On a decision method in restricted second order arithmetic},
   booktitle =  {Logic, Methodology and Philosophy of Science (Proc. 1960 
                 Internat. Congr .)},
   pages =      {1--11},
   publisher =  {Stanford Univ. Press},
   address =    {Stanford, Calif.},
   year =       1962,
   mrclass =    {02.54},
   mrnumber =   {32 \#1116},
   mrreviewer = {R. M. Baer},
}

@article{Buchi65a,
   author =     {B{\"u}chi, J. Richard},
   title =      {Decision methods in the theory of ordinals},
   journal =    {Bull. Amer. Math. Soc.},
   volume =     71,
   year =       1965,
   pages =      {767--770},
   mrclass =    {02.54},
   mrnumber =   {32 \#7413},
   mrreviewer = {G. Asser},
}

@inCollection{Buchi65b,
   author =     {B{\"u}chi, J. Richard},
   title =      {Transfinite automata recursions and weak second order theory of 
                 ordinals},
   booktitle =  {Logic, Methodology and Philos. Sci. (Proc. 1964 Internat. Congr.)},
   pages =      {3--23},
   publisher =  {North-Holland},
   address =    {Amsterdam},
   year =       1965,
   mrclass =    {02.88},
   mrnumber =   {35 \#1480},
   mrreviewer = {L. C. Eggan},
}

@inProceedings{Buchi73,
   author =    {B{\"u}chi, J. Richard},
   title =     {The monadic second-order theory of {$\omega_1$}},
   booktitle = {The Monadic Second-Order Theory of All Countable Ordinals},
   series =    {Lecture Notes in Math.},
   publisher = {Springer Verlag, Berlin, Heidelberg, New York},
   editor =    {J. R. B{\"u}chi and D. Siefkes},
   year =      1973,
   volume =    328,
   pages =     {1--127},
}

@inCollection{Buchi77,
   author =    {B{\"u}chi, J. Richard},
   title =     {Using determinancy of games to eliminate quantifiers},
   booktitle = {Fundamentals of computation theory (Proc. Internat. Conf., 
                Pozna\'n-K\'ornik, 1977)},
   pages =     {367--378. Lecture Notes in Comput. Sci., Vol. 56},
   publisher = {Springer},
   address =   {Berlin},
   year =      1977,
   mrclass =   {02G05 (02F10 04A20)},
   mrnumber =  {58 \#16244},
}

@article{Buchi83,
   author =     {B{\"u}chi, J. Richard},
   title =      {State-strategies for games in ${F}\sb {\sigma\delta}\cap {G}\sb 
                 {\delta\sigma}$},
   journal =    {J. Symbolic Logic},
   fjournal =   {The Journal of Symbolic Logic},
   volume =     48,
   year =       1983,
   number =     4,
   pages =      {1171--1198 (1984)},
   issn =       {0022-4812},
   coden =      {JSYLA6},
   mrclass =    {03B25 (03E15 90D40)},
   mrnumber =   {85j:03012},
   mrreviewer = {P. {\v{S}}t{\v{e}}p{\'a}nek},
}

@article{BuchiElgotWright58,
   author =  {B{\"u}chi, J. Richard and Elgot, Calvin and Wright, Jesse B.},
   title =   {The non existence of certain algorithms of finite automata theory},
   journal = {Notices Amer. Math. Soc.},
   year =    1958,
   volume =  5,
   pages =   {98},
}

@article{BuchiLandweber69a,
   author =     {B{\"u}chi, J. Richard and Landweber, Lawrence H.},
   title =      {Solving sequential conditions by finite-state strategies},
   journal =    {Trans. Amer. Math. Soc.},
   volume =     138,
   year =       1969,
   pages =      {295--311},
   mrclass =    {90.70 (68.00)},
   mrnumber =   {43 \#5926},
   mrreviewer = {A. J. Lohwater},
}

@article{BuchiLandweber69b,
   author =     {B{\"u}chi, J. Richard and Landweber, Lawrence H.},
   title =      {Definability in the monadic second-order theory of successor},
   journal =    {J. Symbolic Logic},
   volume =     34,
   year =       1969,
   pages =      {166--170},
   mrclass =    {02.54},
   mrnumber =   {42 \#4387},
   mrreviewer = {S. Garfunkel},
}

@inCollection{BuchiSiefkes73,
   author =    {B{\"u}chi, J. Richard and Siefkes, Dirk},
   title =     {Axiomatization of the monadic second order theory of $\omega 
                \sb{1}$},
   booktitle = {The monadic second order theory of all countable ordinals 
                (Decidable theories, II)},
   pages =     {129--217. Lecture Notes in Math., Vol. 328},
   publisher = {Springer},
   address =   {Berlin},
   year =      1973,
   mrclass =   {02G10 (06A05)},
   mrnumber =  {58 \#198},
}

@phdThesis{Carton93,
   author =  {Carton, Olivier},
   title =   {Mots infinis, $\omega$-semigroupes et topologie},
   school =  {University Paris VII},
   year =    1993,
}

@conference{Carton94,
   author =    {Carton, Olivier},
   title =     {Chain automata},
   booktitle = {Technology and Applications, IFIP},
   series =    {Information Processing'94, Vol. I},
   publisher = {North Holland, Amsterdam},
   editor =    {B. Pherson, I. Simon},
   year =      1994,
   pages =     {451--458},
}

@article{Carton96,
   author =     {Carton, Olivier},
   title =      {Chain automata},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     161,
   year =       1996,
   number =     {1-2},
   pages =      {191--203},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68Q68 (03D05 68Q60)},
   mrnumber =   {98a:68133},
   mrreviewer = {Wolfgang Thomas},
}

@article{Carton99,
   author =   {Carton, Olivier and Maceiras, Ram{\'o}n},
   title =    {Computing the {R}abin index of a parity automaton},
   journal =  {Theor. Inform. Appl.},
   fjournal = {Theoretical Informatics and Applications. Informatique 
               Th\'eorique et Applications},
   volume =   33,
   year =     1999,
   number =   6,
   pages =    {495--505},
   issn =     {0988-3754},
   mrclass =  {68Q45 (03D05 68Q60)},
   mrnumber = {1 747 513},
}

@article{Carton00,
   author =   {Carton, Olivier},
   title =    {Wreath product and infinite words},
   journal =  {J. Pure Appl. Algebra},
   fjournal = {Journal of Pure and Applied Algebra},
   volume =   153,
   year =     2000,
   number =   2,
   pages =    {129--150},
   issn =     {0022-4049},
   coden =    {JPAAA2},
   mrclass =  {68Q70 (20Mxx 68R15)},
   mrnumber = {1 780 739},
}

@inCollection{CartonBedon98,
   author =    {Bedon, Nicolas and Carton, Olivier},
   title =     {An {E}ilenberg theorem for words on countable ordinals},
   booktitle = {LATIN'98: Theoretical Informatics (Campinas, 1998)},
   editor =    {Cl{\'a}udio L. Lucchesi and Arnaldo V. Moura},
   pages =     {53--64},
   volume =    1380,
   publisher = {Springer},
   series =    {Lecture Notes in Comput. Sci.},
   address =   {Berlin},
   year =      1998,
   mrclass =   {68Q70 (03D05 20M35)},
   mrnumber =  {99e:68105},
}

@inProceedings{CartonMichel00,
   author =    {Carton, Olivier and Michel, Max},
   title =     {Unambiguous B{\"u}chi automata},
   booktitle = {LATIN'2000},
   editor =    {G. Gonnet and D. Panario and A. Viola},
   pages =     {407--416},
   volume =    1776,
   publisher = {Springer},
   series =    {Lecture Notes in Comput. Sci.},
   address =   {Berlin},
   year =      2000,
}

@article{CartonMichel01,
   author =  {Carton, Olivier and Michel, Max},
   title =   {Unambiguous B{\"u}chi automata},
   journal = {Theoret. Comput. Sci.},
	 note = {To appear},
}

@inCollection{CartonPerrin96,
   author =    {Carton, Olivier and Perrin, Dominique},
   title =     {Chains and superchains in $\omega$-semigroups},
   booktitle = {Semigroups, automata and languages (Porto, 1994)},
   pages =     {17--28},
   publisher = {World Sci. Publishing},
   address =   {River Edge, NJ},
   year =      1996,
   mrclass =   {68Q70 (20M35 68Q45)},
   mrnumber =  {1 477 719},
}

@article{CartonPerrin97,
   author =   {Carton, Olivier and Perrin, Dominique},
   title =    {Chains and superchains for $\omega$-rational sets, automata and 
               semigroups},
   journal =  {Internat. J. Algebra Comput.},
   fjournal = {International Journal of Algebra and Computation},
   volume =   7,
   year =     1997,
   number =   6,
   pages =    {673--695},
   issn =     {0218-1967},
   mrclass =  {68Q45 (20M35 68Q70)},
   mrnumber = {99h:68100},
}

@inProceedings{CartonPerrin97b,
   author =    {Carton, Olivier and Perrin, Dominique},
   title =     {The Wadge-Wagner hierarchy of $\omega$-rational sets},
   booktitle = {Automata, Languages and Programming},
   editor =    {Pierpaolo Degano and Roberto Gorrieri and Alberto 
                Marchetti-Spaccamela},
   volume =    1256,
   series =    {Lecture Notes in Comput. Sci.},
   year =      1997,
   publisher = {Springer},
   pages =     {17--35},
}

@article{CartonPerrin99,
   author =     {Carton, Olivier and Perrin, Dominique},
   title =      {The {W}agner hierarchy},
   journal =    {Internat. J. Algebra Comput.},
   fjournal =   {International Journal of Algebra and Computation},
   volume =     9,
   year =       1999,
   number =     5,
   pages =      {597--620},
   issn =       {0218-1967},
   mrclass =    {68Q45 (03E15 54F05 68Q70)},
   mrnumber =   {2000k:68081},
   mrreviewer = {I. Mezn{\'\i}k},
}

@article{ChoHuynh91,
   author =     {Cho, Sang and Hu{\`y}nh, D\~{u}ng T.},
   title =      {Finite-automaton aperiodicity is {P}{S}{P}{A}{C}{E}-complete},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     88,
   year =       1991,
   number =     1,
   pages =      {99--116},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68Q15 (03D05 03D15 68Q25 68Q70)},
   mrnumber =   {92k:68028},
   mrreviewer = {Klaus W. Wagner},
}

@article{Choueka74,
   author =     {Choueka, Yaacov},
   title =      {Theories of automata on $\omega$-tapes: a simplified approach},
   journal =    {J. Comput. System Sci.},
   volume =     8,
   year =       1974,
   pages =      {117--141},
   mrclass =    {02F15 (02F10)},
   mrnumber =   {49 \#7124},
   mrreviewer = {D. Rodding},
}

@article{Choueka78,
   author =     {Choueka, Yaacov},
   title =      {Finite automata, definable sets, and regular expressions over 
                 $\omega \sp{n}$-tapes},
   journal =    {J. Comput. System Sci.},
   volume =     17,
   year =       1978,
   number =     1,
   pages =      {81--97},
   mrclass =    {68A30},
   mrnumber =   {58 \#8514},
   mrreviewer = {Matti Linna},
}

@inCollection{Church63,
   author =    {Church, Alonzo},
   title =     {Logic, arithmetic, and automata},
   booktitle = {Proc. Internat. Congr. Mathematicians (Stockholm, 1962)},
   pages =     {23--35},
   publisher = {Inst. Mittag-Leffler},
   address =   {Djursholm},
   year =      1963,
   mrclass =   {02.88},
   mrnumber =  {31 \#65},
}

@article{ClarkeDraghicescuKurshan93,
   author =   {Clarke, Edmund M. and Draghicescu, I. A. and Kurshan, Robert P.},
   title =    {A unified approach for showing language inclusion and equivalence 
               between various types of $\omega$-automata},
   journal =  {Inform. Process. Lett.},
   fjournal = {Information Processing Letters},
   volume =   46,
   year =     1993,
   number =   6,
   pages =    {301--308},
   issn =     {0020-0190},
   coden =    {IFPLAT},
   mrclass =  {68Q70},
   mrnumber = {94f:68137},
}

@inCollection{ClarkeSchlinloff99,
   author =    {Clarke, Edmund M. and Schlingloff Bernd-Holger},
   title =     {Model checking},
   booktitle = {Handbook of automated reasoning},
   editor =    {A. Robinson and A. Voronkov},
   publisher = {Elsevier},
   year =      1999,
}

@article{Cohen91,
   author =     {Cohen-Chesnot, Jo{\"e}lle},
   title =      {On the expressive power of temporal logic for infinite words},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     83,
   year =       1991,
   number =     {2, Algorithms Automat. Complexity Games},
   pages =      {301--312},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68Q45 (03B45 03B70 03D05)},
   mrnumber =   {92h:68046},
   mrreviewer = {Wolfgang Thomas},
}

@conference{CohenBrzozowski68,
   author =    {Brzozowski, John A. and Cohen, R. S.},
   title =     {On star-free events},
   booktitle = {Proc. Hawaii Int. Conf. on System Science},
   year =      1968,
   pages =     {1--4},
}

@article{CohenBrzozowski71,
   author =     {Cohen, Rina S. and Brzozowski, J. A.},
   title =      {Dot-depth of star-free events},
   journal =    {J. Comput. System Sci.},
   volume =     5,
   year =       1971,
   pages =      {1--16},
   mrclass =    {94A30},
   mrnumber =   {46 \#8783},
   mrreviewer = {B. Reusch},
}

@article{CohenPerrinPin93,
   author =     {Cohen, Jo{\"e}lle and Perrin, Dominique and Pin, Jean-Eric},
   title =      {On the expressive power of temporal logic},
   journal =    {J. Comput. System Sci.},
   fjournal =   {Journal of Computer and System Sciences},
   volume =     46,
   year =       1993,
   number =     3,
   pages =      {271--294},
   issn =       {0022-0000},
   coden =      {JCSSBM},
   mrclass =    {68Q45 (03B45 03B70 68T27)},
   mrnumber =   {94i:68154},
   mrreviewer = {Katalin Bimb{\'o}},
}

@inCollection{Compton83,
   author =     {Compton, Kevin J.},
   title =      {On rich words},
   booktitle =  {Combinatorics on words (Waterloo, Ont., 1982)},
   pages =      {39--61},
   publisher =  {Academic Press},
   address =    {Toronto, Ont.},
   year =       1983,
   mrclass =    {03D05 (03C85 68Q05)},
   mrnumber =   {88h:03050},
   mrreviewer = {Peter Clote},
}

@book{Conway71,
   author =    {Conway, John H.},
   title =     {Regular Algebra and Finite Machines},
   publisher = {Chapman and Hall, London},
   year =      1971,
}

@book{Conway76,
   author =     {Conway, J. H.},
   title =      {On numbers and games},
   note =       {London Mathematical Society Monographs, No. 6},
   publisher =  {Academic Press [Harcourt Brace Jovanovich Publishers]},
   address =    {London},
   year =       1976,
   pages =      {ix+238},
   mrclass =    {02K99 (00A25 90D05 02H25)},
   mrnumber =   {56 \#8365},
   mrreviewer = {John W. Dawson, Jr.},
}

@article{Courcelle78,
   author =   {Courcelle, Bruno},
   title =    {Frontiers of infinite trees},
   journal =  {RAIRO Inform. Th\'eor.},
   fjournal = {RAIRO Informatique Th\'eorique},
   volume =   12,
   year =     1978,
   number =   4,
   pages =    {319--337},
   issn =     {0399-0540},
   coden =    {RSITD7},
   mrclass =  {68E10},
   mrnumber = {81i:68093},
}

@article{Courcelle83,
   author =     {Courcelle, Bruno},
   title =      {Fundamental properties of infinite trees},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     25,
   year =       1983,
   number =     2,
   pages =      {95--169},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68C99 (05C05 68F99)},
   mrnumber =   {84e:68048},
   mrreviewer = {Stephen L. Bloom},
}

@article{CovenHedlund73,
   author =     {Coven, Ethan M. and Hedlund, George A.},
   title =      {Sequences with minimal block growth},
   journal =    {Math. Systems Theory},
   volume =     7,
   year =       1973,
   pages =      {138--153},
   mrclass =    {54H20},
   mrnumber =   {48 \#1199},
   mrreviewer = {R. Ellis},
}

@conference{DarondeauKott83,
   author =    {Darondeau, Philippe and Kott, Laurent},
   title =     {On the observational semantics of fair parallelism},
   booktitle = {Automata, Languages and programming},
   series =    {Lecture Notes in Comput. Sci.},
   publisher = {Springer Verlag, Berlin, Heidelberg, New York},
   editor =    {J. Diaz},
   year =      1983,
   volume =    154,
   pages =     {147--159},
}

@article{DarondeauKott84,
   author =   {Darondeau, Philippe and Kott, Laurent},
   title =    {Towards a formal proof system for $\omega$-rational expressions},
   journal =  {Inform. Process. Lett.},
   fjournal = {Information Processing Letters},
   volume =   19,
   year =     1984,
   number =   4,
   pages =    {173--177},
   issn =     {0020-0190},
   coden =    {IFPLAT},
   mrclass =  {68Q60 (03D05 68Q45)},
   mrnumber = {86i:68087},
}

@inCollection{DarondeauKott85,
   author =     {Darondeau, Philippe and Kott, Laurent},
   title =      {A formal proof system for infinitary rational expressions},
   booktitle =  {Automata on infinite words (Le Mont-Dore, 1984)},
   pages =      {68--80},
   publisher =  {Springer},
   address =    {Berlin},
   year =       1985,
   mrclass =    {68Q45 (03B70)},
   mrnumber =   {88b:68102},
   mrreviewer = {Yasuyoshi Inagaki},
}

@conference{DauchetTimmerman85,
   author =    {Dauchet, Max and Timmerman, Eric},
   title =     {Decidability of yield's equality for infinite regular trees},
   booktitle = {Automata on Infinite Words},
   series =    {Lecture Notes in Comput. Sci.},
   publisher = {Springer Verlag, Berlin, Heidelberg, New York},
   editor =    {M. Nivat and D. Perrin},
   year =      1985,
   volume =    192,
   pages =     {118--136},
}

@inCollection{Davis64,
   author =     {Davis, Morton},
   title =      {Infinite games of perfect information},
   booktitle =  {Advances in game theory},
   pages =      {85--101},
   publisher =  {Princeton Univ. Press},
   address =    {Princeton, N.J.},
   year =       1964,
   mrclass =    {90.70},
   mrnumber =   {30 \#965},
   mrreviewer = {J. H. Blau},
}

@book{Denker76,
   author =     {Denker, Manfred and Grillenberger, Christian and Sigmund, Karl},
   title =      {Ergodic theory on compact spaces},
   note =       {Lecture Notes in Mathematics, Vol. 527},
   publisher =  {Springer-Verlag},
   address =    {Berlin},
   year =       1976,
   pages =      {iv+360},
   mrclass =    {28A65 (54H20)},
   mrnumber =   {56 \#15879},
   mrreviewer = {W. Parry},
}

@article{DevolderLatteuxLitovskyStaiger95,
   author =   {Devolder, Jeanne and Latteux, Michel and Litovsky, Igor and 
               Staiger, Ludwig},
   title =    {Codes and infinite words},
   journal =  {Acta Cybernet.},
   fjournal = {Acta Cybernetica},
   volume =   11,
   year =     1994,
   number =   4,
   pages =    {241--256},
   issn =     {0324-721X},
   coden =    {ACCYDX},
   mrclass =  {94A45 (20M05 68Q70 68R15)},
   mrnumber = {95g:94007},
}

@preamble{
   "\def\Dbar{\leavevmode\lower.6ex\hbox to 0pt{\hskip-.23ex
    \accent"16\hss}D} "#
		"\def\cftil#1{\ifmmode\setbox7\hbox{$\accent"5E#1$}\else
    \setbox7\hbox{\accent"5E#1}\penalty 10000\relax\fi\raise 1\ht7
    \hbox{\lower1.15ex\hbox to 1\wd7{\hss\accent"7E\hss}}\penalty 10000
    \hskip-1\wd7\penalty 10000\box7} "
}
@article{DoLongVanLeSaecLitovsky95,
   author =     {{\Dbar}{\cftil{o}} Long V\^{a}n and Le Sa{\"e}c, Bertrand and 
                 Litovsky, Igor},
   title =      {Characterizations of rational $\omega$-languages by means of 
                 right congruences},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     143,
   year =       1995,
   number =     1,
   pages =      {1--21},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68Q68 (03D05 68Q45 68Q70)},
   mrnumber =   {97c:68108},
   mrreviewer = {Wolfgang Thomas},
}

@article{MR44:5179b,
   author =     {Doner, John},
   title =      {Erratum: ``{T}ree acceptors and some of their applications''},
   journal =    {J. Comput. System Sci.},
   volume =     5,
   year =       1971,
   pages =      {453},
   mrclass =    {94.30},
   mrnumber =   {44 \#5179b},
   mrreviewer = {A. Paz},
}

@article{Doner70,
   author =   {Doner, John},
   title =    {Tree acceptors and some of their applications},
   journal =  {J. Comput. System Sci.},
   volume =   4,
   year =     1970,
   pages =    {406--451},
   mrclass =  {94.30},
   mrnumber = {44 \#5179a},
}

@book{EbbinghausFlumThomas84,
   author =     {Ebbinghaus, H.-D. and Flum, J. and Thomas, W.},
   title =      {Mathematical logic},
   edition =    {Second},
   note =       {Translated from the German by Margit Me\ss mer},
   publisher =  {Springer-Verlag},
   address =    {New York},
   year =       1994,
   pages =      {x+289},
   isbn =       {0-387-94258-0},
   mrclass =    {03-01},
   mrnumber =   {95e:03002},
   mrreviewer = {Marcel Guillaume},
}

@article{Ehrenfeucht,
   author =     {Ehrenfeucht, Andrzej},
   title =      {An application of games to the completeness problem for 
                 formalized theories},
   journal =    {Fund. Math.},
   volume =     49,
   year =       {1960/1961},
   pages =      {129--141},
   mrclass =    {02.50},
   mrnumber =   {23 \#A3666},
   mrreviewer = {G. F. Rose},
}

@book{Eilenberg74,
   author =     {Eilenberg, Samuel},
   title =      {Automata, languages, and machines. {V}ol. {A}},
   note =       {Pure and Applied Mathematics, Vol. 58},
   publisher =  {Academic Press [A subsidiary of Harcourt Brace Jovanovich, 
                 Publishers], New York},
   year =       1974,
   pages =      {xvi+451},
   mrclass =    {94A30 (68A25 68A30)},
   mrnumber =   {58 \#26604a},
   mrreviewer = {D. Simovici},
}

@book{Eilenberg76,
   author =     {Eilenberg, Samuel},
   title =      {Automata, languages, and machines. {V}ol. {B}},
   note =       {With two chapters (``Depth decomposition theorem'' and 
                 ``Complexity of semigroups and morphisms'') by Bret Tilson, Pure 
                 and Applied Mathematics, Vol. 59},
   publisher =  {Academic Press [Harcourt Brace Jovanovich Publishers]},
   address =    {New York},
   year =       1976,
   pages =      {xiii+387},
   mrclass =    {94A30 (68A25 68A30)},
   mrnumber =   {58 \#26604b},
   mrreviewer = {D. Simovici},
}

@article{Elgot61,
   author =     {Elgot, Calvin C.},
   title =      {Decision problems of finite automata design and related 
                 arithmetics},
   journal =    {Trans. Amer. Math. Soc.},
   volume =     98,
   year =       1961,
   pages =      {21--51},
   mrclass =    {02.80},
   mrnumber =   {25 \#2962},
   mrreviewer = {S. Huzino},
}

@article{ElgotRabin66,
   author =  {Elgot, Calvin C. and Rabin, Michael O.},
   title =   {Decidability and undecidability of second (first) order theory of 
              (generalized) successor},
   journal = {J. of Symbolic Logic},
   year =    1966,
   volume =  31,
   pages =   {169--181},
}

@inCollection{Emerson90,
   author =    {Emerson, E. Allen},
   title =     {Temporal and modal logic},
   booktitle = {Handbook of theoretical computer science, Vol.\ B},
   pages =     {995--1072},
   publisher = {Elsevier},
   address =   {Amsterdam},
   year =      1990,
   mrclass =   {68T27 (03B45 03B70)},
   mrnumber =  {1 127 201},
}

@article{EmersonLei87,
   author =   {Emerson, E. Allen and Lei, Chin-Laung},
   title =    {Modalities for model checking: branching time logic strikes back},
   journal =  {Sci. Comput. Programming},
   fjournal = {Science of Computer Programming},
   volume =   8,
   year =     1987,
   number =   3,
   pages =    {275--306},
   issn =     {0167-6423},
   coden =    {SCPGD4},
   mrclass =  {68Q60 (03B45 03B70 68Q55 68Q70)},
   mrnumber = {89h:68106},
}

@inProceedings{EmersonJutla,
   author =    {E. A. Emerson and C.S. Jutla},
   title =     {The complexity of tree automata and logic of programs},
   year =      1988,
   booktitle = {Proc. 29th Annual IEEE Symp. on Foundations of Computer Science},
   pages =     {328-337},
}

@inCollection{Fagin74,
   author =     {Fagin, Ronald},
   title =      {Generalized first-order spectra and polynomial-time recognizable 
                 sets},
   booktitle =  {Complexity of computation (Proc. SIAM-AMS Sympos. Appl. Math., 
                 New York, 1973)},
   pages =      {43--73. SIAM-AMS Proc., Vol. VII},
   publisher =  {Amer. Math. Soc.},
   address =    {Providence, R.I.},
   year =       1974,
   mrclass =    {02F10 (02F20 68A20)},
   mrnumber =   {51 \#7840},
   mrreviewer = {A. L. Selman},
}

@book{Feller57,
   author =     {Feller, William},
   title =      {An introduction to probability theory and its applications. 
                 {V}ol. {I}},
   edition =    {Third},
   publisher =  {John Wiley \& Sons Inc.},
   address =    {New York},
   year =       1968,
   pages =      {xviii+509},
   mrclass =    {60.00},
   mrnumber =   {37 \#3604},
   mrreviewer = {J. G. Wendel},
}

@article{Fischer75,
   author =     {Fischer, Roland},
   title =      {Sofic systems and graphs},
   journal =    {Monatsh. Math.},
   volume =     80,
   year =       1975,
   number =     3,
   pages =      {179--186},
   mrclass =    {28A65 (54H20)},
   mrnumber =   {53 \#11018},
   mrreviewer = {B. Weiss},
}

@book{Furstenberg81,
   author =     {Furstenberg, Hillel},
   title =      {Recurrence in ergodic theory and combinatorial number theory},
   note =       {M. B. Porter Lectures},
   publisher =  {Princeton University Press},
   address =    {Princeton, N.J.},
   year =       1981,
   pages =      {xi+203},
   isbn =       {0-691-08269-3},
   mrclass =    {28D05 (10K10 10L10 54H20)},
   mrnumber =   {82j:28010},
   mrreviewer = {Michael Keane},
}

@inCollection{GabbayHodkinsonReynolds93,
   author =     {Gabbay, Dov M. and Hodkinson, Ian M. and Reynolds, Mark A.},
   title =      {Temporal expressive completeness in the presence of gaps},
   booktitle =  {Logic Colloquium '90 (Helsinki, 1990)},
   pages =      {89--121},
   publisher =  {Springer},
   address =    {Berlin},
   year =       1993,
   mrclass =    {03B45 (03C07)},
   mrnumber =   {95m:03041},
   mrreviewer = {Marcus Kracht},
}

@book{GabbayHodkinsonReynolds94,
   author =     {Gabbay, Dov M. and Hodkinson, Ian and Reynolds, Mark},
   title =      {Temporal logic. {V}ol. 1},
   note =       {Mathematical foundations and computational aspects, Oxford 
                 Science Publications},
   publisher =  {The Clarendon Press Oxford University Press},
   address =    {New York},
   year =       1994,
   pages =      {xiv+653},
   isbn =       {0-19-853769-7},
   mrclass =    {03B45 (03B65 03B70 68Q60 68T27)},
   mrnumber =   {95h:03040},
   mrreviewer = {Neculai Curteanu},
}

@conference{GabbayPnueliShelahStavi80,
   author =    {Gabbay, Daniel and Pnueli, Amir and Shelah, Shaharon and Stavi, 
                J.},
   title =     {On the temporal analysis of fairness},
   booktitle = {Proc. 7th ACM Symp. Princ. Prog. Lang.},
   publisher = {Assoc. Comput. Mach.},
   year =      1980,
   pages =     {163--173},
}

@book{GabbayReynoldsFinger00,
   author =    {Gabbay, Dov M. and Reynolds, Mark A. and Finger, Marcelo},
   title =     {Temporal logic. Vol. 2},
   note =      {Mathematical foundations and computational aspects, Oxford 
                Science Publications},
   publisher = {The Clarendon Press Oxford University Press},
   address =   {New York},
   year =      2000,
}

@inCollection{GaleStewart53,
   author =    {Gale, D. and Stewart, F.M.},
   title =     {Infinite games with perfect information},
   booktitle = {Contributions to the Theory of Games},
   series =    {Ann. Math. Studies},
   publisher = {Princeton Univ. Press, Princeton, N.J.},
   year =      1953,
   pages =     {245--266},
}

@book{GareyJohnson79,
   author =     {Garey, Michael R. and Johnson, David S.},
   title =      {Computers and intractability},
   note =       {A guide to the theory of NP-completeness, A Series of Books in 
                 the Mathematical Sciences},
   publisher =  {W. H. Freeman and Co.},
   address =    {San Francisco, Calif.},
   year =       1979,
   pages =      {x+338},
   isbn =       {0-7167-1045-5},
   mrclass =    {68C25 (03D15)},
   mrnumber =   {80g:68056},
   mrreviewer = {Pavel Pudl{\'a}k},
}

@book{GecsegSteinby,
   author =     {G{\'e}cseg, Ferenc and Steinby, Magnus},
   title =      {Tree automata},
   publisher =  {Akad\'emiai Kiad\'o (Publishing House of the Hungarian Academy of 
                 Sciences)},
   address =    {Budapest},
   year =       1984,
   pages =      {235},
   isbn =       {963-05-3170-4},
   mrclass =    {68Q70 (03D05 68Q50)},
   mrnumber =   {86c:68061},
   mrreviewer = {Yasuyoshi Inagaki},
}

@article{Gire82a,
   author =   {Gire, Fran{\c{c}}oise},
   title =    {Langages rationnels dont la limite est ferm\'ee},
   journal =  {C. R. Acad. Sci. Paris S\'er. I Math.},
   fjournal = {Comptes Rendus des S\'eances de l'Acad\'emie des Sciences. 
               S\'erie I. Math\'ematique},
   volume =   294,
   year =     1982,
   number =   21,
   pages =    {701--704},
   issn =     {0249-6321},
   coden =    {CHASAP},
   mrclass =  {68F05},
   mrnumber = {83h:68113},
}

@conference{Gire82b,
   author =    {Gire, Fran{\c{c}}oise},
   title =     {Une extension aux mots infinis de la notion de transduction},
   booktitle = {Theoretical Computer Science, Proceedings of the 6th GI 
                Conference},
   series =    {Lecture Notes in Comput. Sci.},
   publisher = {Springer Verlag, Berlin, Heidelberg, New York},
   editor =    {A.B. Cremers and H.P. Kriegel},
   year =      1982,
   volume =    145,
   pages =     {123--139},
}

@article{Gire86,
   author =     {Gire, Fran{\c{c}}oise},
   title =      {Two decidability problems for infinite words},
   journal =    {Inform. Process. Lett.},
   fjournal =   {Information Processing Letters},
   volume =     22,
   year =       1986,
   number =     3,
   pages =      {135--140},
   issn =       {0020-0190},
   coden =      {IFPLAT},
   mrclass =    {68Q45 (03D05)},
   mrnumber =   {87f:68044},
   mrreviewer = {Karel Culik II},
}

@article{Gire84,
   author =     {Gire, Fran{\c{c}}oise and Nivat, Maurice},
   title =      {Relations rationnelles infinitaires},
   journal =    {Calcolo},
   fjournal =   {Calcolo},
   volume =     21,
   year =       1984,
   number =     2,
   pages =      {91--125},
   issn =       {0008-0624},
   coden =      {CDABAE},
   mrclass =    {68Q45 (03D05)},
   mrnumber =   {87g:68039},
   mrreviewer = {Christine Charretton},
}

@article{Gire91,
   author =     {Gire, Fran{\c{c}}oise and Nivat, Maurice},
   title =      {Langages alg\'ebriques de mots biinfinis},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     86,
   year =       1991,
   number =     2,
   pages =      {277--323},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68Q45},
   mrnumber =   {93a:68073},
   mrreviewer = {Dani{\`e}le Beauquier},
}

@article{GolombGordon65,
   author =   {Golomb, Solomon W. and Gordon, Basil},
   title =    {Codes with bounded synchronization delay},
   journal =  {Information and Control},
   volume =   8,
   year =     1965,
   pages =    {355--372},
   mrclass =  {94.10},
   mrnumber = {31 \#4648},
}

@book{GottschalkHedlund55,
   author =     {Gottschalk, Walter Helbig and Hedlund, Gustav Arnold},
   title =      {Topological dynamics},
   note =       {American Mathematical Society Colloquium Publications, Vol. 36},
   publisher =  {American Mathematical Society},
   address =    {Providence, R. I.},
   year =       1955,
   pages =      {vii+151},
   mrclass =    {56.0X},
   mrnumber =   {17,650e},
   mrreviewer = {Y. N. Dowker},
}

@book{GrahamRotshildSpencer90,
   author =    {Graham, Ronald L. and Rothschild, Bruce L. and Spencer, Joel H.},
   title =     {Ramsey theory},
   edition =   {Second},
   note =      {A Wiley-Interscience Publication},
   publisher = {John Wiley \& Sons Inc.},
   address =   {New York},
   year =      1990,
   pages =     {xii+196},
   isbn =      {0-471-50046-1},
   mrclass =   {05-02 (04A20 05A99 05C55 54H20)},
   mrnumber =  {90m:05003},
}

@inCollection{Gurevich85,
   author =    {Gurevich, Yuri},
   title =     {Monadic second-order theories},
   booktitle = {Model-theoretic logics},
   pages =     {479--506},
   publisher = {Springer},
   address =   {New York},
   year =      1985,
   mrclass =   {03C85 (03B15 03B25 03D35)},
   mrnumber =  {819 544},
}

@inCollection{Gurevich90,
   author =    {Gurevich, Yuri},
   title =     {Games people play},
   booktitle = {The Collected Works of J. Richard B{\"u}chi},
   editor =    {S. McLane and D. Siefkes},
   year =      1990,
   pages =     {518-524},
   publisher = {Springer},
}

@conference{GurevichHarrington82,
   author =    {Gurevich, Yuri and Harrington, Leo},
   title =     {Trees, automata and games},
   booktitle = {Proc. ACM Symp. on Theory of Computing},
   publisher = {Assoc. Comput. Mach.},
   year =      1982,
   pages =     {60--65},
}

@article{GurevichMagidorShelah83,
   author =     {Gurevich, Yuri and Magidor, Menachem and Shelah, Saharon},
   title =      {The monadic theory of $\omega \sb{2}$},
   journal =    {J. Symbolic Logic},
   fjournal =   {The Journal of Symbolic Logic},
   volume =     48,
   year =       1983,
   number =     2,
   pages =      {387--398},
   issn =       {0022-4812},
   coden =      {JSYLA6},
   mrclass =    {03C85 (03E35 03F25)},
   mrnumber =   {84i:03076},
   mrreviewer = {E. Mendelson},
}

@inCollection{Hanf65,
   author =     {Hanf, William},
   title =      {Model-theoretic methods in the study of elementary logic},
   booktitle =  {Theory of Models (Proc. 1963 Internat. Sympos. Berkeley)},
   pages =      {132--145},
   publisher =  {North-Holland},
   address =    {Amsterdam},
   year =       1965,
   mrclass =    {02.50},
   mrnumber =   {35 \#1457},
   mrreviewer = {M. B. Pour-El},
}

@article{HartmanisStearns67,
   author =     {Hartmanis, Juris and Stearns, Richard E.},
   title =      {Sets of numbers defined by finite automata},
   journal =    {Amer. Math. Monthly},
   volume =     74,
   year =       1967,
   pages =      {539--542},
   mrclass =    {94.40},
   mrnumber =   {35 \#2694},
   mrreviewer = {S. Huzino},
}

@book{Hausdorff57,
   author =    {Hausdorff, Felix},
   title =     {Set theory},
   note =      {Second edition. Translated from the German by John R. Aumann et 
                al},
   publisher = {Chelsea Publishing Co.},
   address =   {New York},
   year =      1962,
   pages =     {352},
   mrclass =   {04.00},
   mrnumber =  {25 \#4999},
}

@inCollection{Head85,
   author =     {Head, Tom},
   title =      {The adherences of languages as topological spaces},
   booktitle =  {Automata on infinite words (Le Mont-Dore, 1984)},
   pages =      {147--163},
   publisher =  {Springer},
   address =    {Berlin},
   year =       1985,
   mrclass =    {68Q45 (03D05 54H10)},
   mrnumber =   {87h:68089},
   mrreviewer = {Branislav Rovan},
}

@article{Head86,
   author =     {Head, Tom},
   title =      {The topological structure of adherences of regular languages},
   journal =    {RAIRO Inform. Th\'eor. Appl.},
   fjournal =   {RAIRO Informatique Th\'eorique et Applications},
   volume =     20,
   year =       1986,
   number =     1,
   pages =      {31--41},
   issn =       {0296-1598},
   mrclass =    {68Q45},
   mrnumber =   {88d:68052},
   mrreviewer = {H. J{\"u}rgensen},
}

@inCollection{HeadLando86,
   author =    {Head, Tom and Lando, Barbara},
   title =     {Fixed and Stationary {$\omega$}-words and {$\omega$}-languages},
   booktitle = {The Book of L},
   editor =    {G. Rozenberg, A. Salomaa},
   publisher = {Springer Verlag, Berlin, Heidelberg, New York},
   year =      1986,
   pages =     {147--156},
}

@article{Heilbrunner80,
   author =   {Heilbrunner, Stephan},
   title =    {An algorithm for the solution of fixed-point equations for 
               infinite words},
   journal =  {RAIRO Inform. Th\'eor.},
   fjournal = {RAIRO Informatique Th\'eorique},
   volume =   14,
   year =     1980,
   number =   2,
   pages =    {131--141},
   issn =     {0399-0540},
   coden =    {RSITD7},
   mrclass =  {68F05},
   mrnumber = {81g:68110},
}

@article{Hodgson83,
   author =     {Hodgson, Bernard R.},
   title =      {D\'ecidabilit\'e par automate fini},
   journal =    {Ann. Sci. Math. Qu\'ebec},
   fjournal =   {Les Annales des Sciences Math\'ematiques du Qu\'ebec},
   volume =     7,
   year =       1983,
   number =     1,
   pages =      {39--57},
   issn =       {0707-9109},
   mrclass =    {03B25 (03D05 68D99)},
   mrnumber =   {84m:03016},
   mrreviewer = {H. J{\"u}rgensen},
}

@inCollection{Hodkinson94,
   author =    {Hodkinson, Ian},
   title =     {Expressive completeness of {U}ntil and {S}ince over {D}edekind 
                complete linear time},
   booktitle = {Modal logic and process algebra (Amsterdam, 1994)},
   pages =     {171--185},
   publisher = {CSLI Publ.},
   address =   {Stanford, CA},
   year =      1995,
   mrclass =   {03B45},
   mrnumber =  {97b:03028},
}

@inCollection{HoogeboomRozenberg86,
   author =    {Hoogeboom, Hendrik J. and Rozenberg, Gregorz},
   title =     {Infinitary languages: basic theory and applications to concurrent 
                systems},
   booktitle = {Current trends in concurrency (Noordwijkerhout, 1985)},
   pages =     {266--342},
   publisher = {Springer},
   address =   {Berlin},
   year =      1986,
   mrclass =   {68Q45 (03D05 68Q10)},
   mrnumber =  {87k:68076},
}

@book{HopcroftUllman79,
   author =     {Hopcroft, John E. and Ullman, Jeffrey D.},
   title =      {Introduction to automata theory, languages, and computation},
   note =       {Addison-Wesley Series in Computer Science},
   publisher =  {Addison-Wesley Publishing Co., Reading, Mass.},
   year =       1979,
   pages =      {x+418},
   isbn =       {0-201-02988-X},
   mrclass =    {68-01 (03-01 03Dxx 68D05 68F05)},
   mrnumber =   {83j:68002},
   mrreviewer = {S. Istrail},
}

@book{Howie76,
   author =     {Howie, John M.},
   title =      {An introduction to semigroup theory},
   note =       {L.M.S. Monographs, No. 7},
   publisher =  {Academic Press [Harcourt Brace Jovanovich Publishers]},
   address =    {London},
   year =       1976,
   pages =      {x+272},
   mrclass =    {20MXX},
   mrnumber =   {57 \#6235},
   mrreviewer = {T. E. Hall},
}

@article{Immerman87,
   author =     {Immerman, Neil},
   title =      {Languages that capture complexity classes},
   journal =    {SIAM J. Comput.},
   fjournal =   {SIAM Journal on Computing},
   volume =     16,
   year =       1987,
   number =     4,
   pages =      {760--778},
   issn =       {0097-5397},
   coden =      {SMJCAT},
   mrclass =    {68Q15 (03D15)},
   mrnumber =   {88j:68051},
   mrreviewer = {G. Wechsung},
}

@article{Isli96,
   author =     {Isli, Amar},
   title =      {Converting a {B}\"uchi alternating automaton to a usual 
                 nondeterministic one},
   journal =    {S\=adhan\=a},
   fjournal =   {S\=adhan\=a. Academy Proceedings in Engineering Sciences},
   volume =     21,
   year =       1996,
   number =     2,
   pages =      {213--228},
   issn =       {0256-2499},
   mrclass =    {68Q68 (03D05 68Q60)},
   mrnumber =   {97k:68118},
   mrreviewer = {Wolfgang Thomas},
}

@inCollection{IzumiInagakiHonda84,
   author =    {Izumi, Hiroyuki and Inagaki, Yasuyoshi and Honda, Namio},
   title =     {A complete axiom system for algebra of closed-regular expression},
   booktitle = {Automata, languages and programming (Antwerp, 1984)},
   pages =     {260--269},
   publisher = {Springer},
   address =   {Berlin},
   year =      1984,
   mrclass =   {68Q45},
   mrnumber =  {784 254},
}

@article{Jones75,
   author =     {Jones, Neil D.},
   title =      {Space-bounded reducibility among combinatorial problems},
   journal =    {J. Comput. System Sci.},
   volume =     11,
   year =       1975,
   number =     1,
   pages =      {68--85},
   mrclass =    {68A20},
   mrnumber =   {53 \#2020},
   mrreviewer = {Ronald V. Book},
}

@article{JustinPirillo86,
   author =     {Justin, Jacques and Pirillo, Giuseppe},
   title =      {On a natural extension of {J}acob's ranks},
   journal =    {J. Combin. Theory Ser. A},
   fjournal =   {Journal of Combinatorial Theory. Series A},
   volume =     43,
   year =       1986,
   number =     2,
   pages =      {205--218},
   issn =       {0097-3165},
   coden =      {JCBTA7},
   mrclass =    {06F05 (20M10)},
   mrnumber =   {88a:06019},
   mrreviewer = {P. M. Higgins},
}

@article{Kaminski85,
   author =     {Kaminski, Michael},
   title =      {A classification of $\omega$-regular languages},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     36,
   year =       1985,
   number =     {2-3},
   pages =      {217--229},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68Q45 (68Q15)},
   mrnumber =   {86m:68078},
   mrreviewer = {Gheorghe P{\u{a}}un},
}

@phdThesis{Kamp68,
   author =  {Kamp, J.A.},
   title =   {Tense Logic and the Theory of Linear Order},
   year =    1968,
   school =  {Univ. of California, Los Angeles},
}

@article{Karpinski75,
   author =     {Karpi{\'n}ski, Marek},
   title =      {Almost deterministic $\omega$-automata with existential output 
                 condition},
   journal =    {Proc. Amer. Math. Soc.},
   volume =     53,
   year =       1975,
   number =     2,
   pages =      {449--452},
   mrclass =    {02F10 (68A30 68A25)},
   mrnumber =   {55 \#10253},
   mrreviewer = {Klaus Indermark},
}

@book{Kechris94,
   author =     {Kechris, Alexander S.},
   title =      {Classical descriptive set theory},
   publisher =  {Springer-Verlag},
   address =    {New York},
   year =       1995,
   pages =      {xviii+402},
   isbn =       {0-387-94374-9},
   mrclass =    {03E15 (03-01 03-02 04A15 28A05 54H05 90D44)},
   mrnumber =   {96e:03057},
   mrreviewer = {Jakub Jasi{\'n}ski},
}

@inCollection{Klarlund91,
   author =    {Klarlund, Nils},
   title =     {Progress measures for complementation of $\omega$-automata with 
                applications to temporal logic},
   booktitle = {32nd Annual Symposium on Foundations of Computer Science (San 
                Juan, PR, 1991)},
   pages =     {358--367},
   publisher = {IEEE Comput. Soc. Press},
   address =   {Los Alamitos, CA},
   year =      1991,
   mrclass =   {68Q70 (68T27)},
   mrnumber =  {93i:68134},
}

@article{Klarlund94,
   author =     {Klarlund, Nils},
   title =      {Progress measures, immediate determinacy, and a subset 
                 construction for tree automata},
   note =       {Invited papers presented at the 1992 IEEE Symposium on Logic in 
                 Computer Science (Santa Cruz, CA)},
   journal =    {Ann. Pure Appl. Logic},
   fjournal =   {Annals of Pure and Applied Logic},
   volume =     69,
   year =       1994,
   number =     {2-3},
   pages =      {243--268},
   issn =       {0168-0072},
   coden =      {APALD7},
   mrclass =    {03D05 (03B15 03B25 68Q60 68Q68 90D40)},
   mrnumber =   {96c:03084},
   mrreviewer = {Kai Salomaa},
}

@Manual{KlarlundMoller01,
  title = 	 {{MONA Version 1.4 User Manual}},
  author = 	 {Klarlund, Nils and M{\o}ller, Anders},
  organization = {BRICS Notes Series NS-01-1},
  address = 	 {Department of Computer Science, University of Aarhus},
  month = 	 {January},
  year = 	 {2001}
}

@inCollection{Kleene56,
   author =     {Kleene, S. C.},
   title =      {Representation of events in nerve nets and finite automata},
   booktitle =  {Automata studies},
   pages =      {3--41},
   note =       {Annals of mathematics studies, no. 34},
   publisher =  {Princeton University Press},
   address =    {Princeton, N. J.},
   year =       1956,
   mrclass =    {02.0X},
   mrnumber =   {17,1040c},
   mrreviewer = {C. Y. Lee},
}

@article{KobayashiTakahashiYamasaki84,
   author =     {Kobayashi, Kojiro and Takahashi, Masako and Yamasaki, Hideki},
   title =      {Characterization of $\omega$-regular languages by first-order 
                 formulas},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     28,
   year =       1984,
   number =     3,
   pages =      {315--327},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68Q05 (03D05 68Q15 68Q45)},
   mrnumber =   {86h:68037},
   mrreviewer = {G. E. Tse{\u\i}tlin},
}

@inCollection{KobayashiTakahashiYamasaki85,
   author =    {Kobayashi, Kojiro and Takahashi, Masako and Yamasaki, Hideki},
   title =     {Logical formulas and four subclasses of $\omega$-regular 
                languages},
   booktitle = {Automata on infinite words (Le Mont-Dore, 1984)},
   pages =     {81--88},
   publisher = {Springer},
   address =   {Berlin},
   year =      1985,
   mrclass =   {68Q45 (03D05 20M35)},
   mrnumber =  {814 734},
}

@conference{KupfermanSafraVardi96,
   author =    {Kupferman, Orna and Safra, Shmuel and Vardi, Moshe Y.},
   title =     {Relating word and tree automata},
   booktitle = {Proceedings, 11th Annual IEEE Symposium on Logic in Computer Science},
   series =    {Lecture Notes in Computer Science},
   publisher = {IEEE Computer Society Press},
   year =      1996,
   pages =     {322--332},
}

@article{Kurshan87,
   author =     {Kurshan, Robert P.},
   title =      {Complementing deterministic {B}\"uchi automata in polynomial time},
   journal =    {J. Comput. System Sci.},
   fjournal =   {Journal of Computer and System Sciences},
   volume =     35,
   year =       1987,
   number =     1,
   pages =      {59--71},
   issn =       {0022-0000},
   coden =      {JCSSBM},
   mrclass =    {68Q70 (03D05 03D15 68Q25 68Q45)},
   mrnumber =   {89g:68052},
   mrreviewer = {Aravinda Prasad Sistla},
}

@article{Ladner77,
   author =     {Ladner, Richard E.},
   title =      {Application of model theoretic games to discrete linear orders 
                 and finite automata},
   journal =    {Information and Control},
   volume =     33,
   year =       1977,
   number =     4,
   pages =      {281--303},
   mrclass =    {02G05 (02F10 02H15)},
   mrnumber =   {58 \#10387},
   mrreviewer = {Egon Borger},
}

@book{Lallement79,
   author =     {Lallement, G{\'e}rard},
   title =      {Semigroups and combinatorial applications},
   note =       {Pure and Applied Mathematics, A Wiley-Interscience Publication},
   publisher =  {John Wiley \&\ Sons, New York-Chichester-Brisbane},
   year =       1979,
   pages =      {xi+376},
   isbn =       {0-471-04379-6},
   mrclass =    {20Mxx (05-02 68D30 68F05)},
   mrnumber =   {81j:20082},
   mrreviewer = {H. J{\"u}rgensen},
}

@article{Landweber67,
   author =  {Landweber, Lawrence H.},
   title =   {Finite state games - A solvability algorithm for restricted 
              second-order arithmetic},
   journal = {Notices Amer. Math. Soc.},
   year =    1967,
   volume =  14,
   pages =   {129--130},
}

@article{Landweber69,
   author =     {Landweber, Lawrence H.},
   title =      {Decision problems for $\omega$-automata},
   journal =    {Math. Systems Theory},
   volume =     3,
   year =       1969,
   pages =      {376--384},
   mrclass =    {02.88},
   mrnumber =   {41 \#5219},
   mrreviewer = {J. R. B{\"u}chi},
}

@article{LatteuxTimmermann86a,
   author =     {Latteux, Michel and Timmerman, Eric},
   title =      {Finitely generated $\omega$-languages},
   journal =    {Inform. Process. Lett.},
   fjournal =   {Information Processing Letters},
   volume =     23,
   year =       1986,
   number =     4,
   pages =      {171--175},
   issn =       {0020-0190},
   coden =      {IFPLAT},
   mrclass =    {68Q45 (03D05 20M05 20M35)},
   mrnumber =   {88h:68045},
   mrreviewer = {Ludwig Staiger},
}

@article{LatteuxTimmermann86b,
   author =     {Latteux, Michel and Timmerman, Eric},
   title =      {Two characterizations of rational adherences},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     46,
   year =       1986,
   number =     1,
   pages =      {101--106},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68Q45},
   mrnumber =   {88e:68066},
   mrreviewer = {Juhani Karhum{\"a}ki},
}

@article{LatteuxTimmermann88,
   author =     {Latteux, Michel and Timmerman, Eric},
   title =      {Bifaithful starry transductions},
   journal =    {Inform. Process. Lett.},
   fjournal =   {Information Processing Letters},
   volume =     28,
   year =       1988,
   number =     1,
   pages =      {1--4},
   issn =       {0020-0190},
   coden =      {IFPLAT},
   mrclass =    {68Q45},
   mrnumber =   {89h:68084},
   mrreviewer = {Christine Charretton},
}

@article{LeSaec90,
   author =     {Le Saec, Bertrand},
   title =      {Saturating right congruences},
   journal =    {RAIRO Inform. Th\'eor. Appl.},
   fjournal =   {RAIRO Informatique Th\'eorique et Applications},
   volume =     24,
   year =       1990,
   number =     6,
   pages =      {545--559},
   issn =       {0988-3754},
   mrclass =    {68Q45},
   mrnumber =   {92d:68077},
   mrreviewer = {I. Mezn{\'\i}k},
}

@inProceedings{LeSaec91,
   author =    {Le Saec, Bertrand},
   title =     {A modular proof of {McNaughton}'s theorem},
   booktitle = {Logic and recognizable sets},
   publisher = {Kiel Universit{\"a}t, Kiel},
   editor =    {Thomas, W.},
   year =      1991,
   pages =     {50--55},
}

@inCollection{LeSaecPinWeil91a,
   author =    {Le Sa{\"e}c, Bertrand and Pin, Jean-Eric and Weil, Pascal},
   title =     {A purely algebraic proof of {M}c{N}aughton's theorem on infinite 
                words},
   booktitle = {Foundations of software technology and theoretical computer 
                science (New Delhi, 1991)},
   pages =     {141--151},
   publisher = {Springer},
   address =   {Berlin},
   year =      1991,
   mrclass =   {68Q45 (68Q70)},
   mrnumber =  {94g:68064},
}

@article{LeSaecPinWeil91b,
   author =     {Le Sa{\"e}c, Bertrand and Pin, Jean-Eric and Weil, Pascal},
   title =      {Semigroups with idempotent stabilizers and applications to 
                 automata theory},
   journal =    {Internat. J. Algebra Comput.},
   fjournal =   {International Journal of Algebra and Computation},
   volume =     1,
   year =       1991,
   number =     3,
   pages =      {291--314},
   issn =       {0218-1967},
   mrclass =    {20M35 (20M07 68Q70)},
   mrnumber =   {93d:20120},
   mrreviewer = {Eckehart Hotzel},
}

@inCollection{LichtensteinPnueliZuck85,
   author =     {Lichtenstein, Orna and Pnueli, Amir and Zuck, Lenore},
   title =      {The glory of the past},
   booktitle =  {Logics of programs (Brooklyn, N.Y., 1985)},
   pages =      {196--218},
   publisher =  {Springer},
   address =    {Berlin},
   year =       1985,
   mrclass =    {03B70 (03B45 68Q60)},
   mrnumber =   {87b:03058},
   mrreviewer = {W. Richard Stark},
}

@article{Lindsay86,
   author =   {Lindsay, Peter A.},
   title =    {Alternation and $\omega$-type {T}uring acceptors},
   journal =  {Theoret. Comput. Sci.},
   fjournal = {Theoretical Computer Science},
   volume =   43,
   year =     1986,
   number =   1,
   pages =    {107--115},
   issn =     {0304-3975},
   coden =    {TCSDI},
   mrclass =  {68Q15 (03D10 03D15)},
   mrnumber = {88a:68039},
}

@article{Lindsay88,
   author =     {Lindsay, Peter A.},
   title =      {On alternating $\omega$-automata},
   journal =    {J. Comput. System Sci.},
   fjournal =   {Journal of Computer and System Sciences},
   volume =     36,
   year =       1988,
   number =     1,
   pages =      {16--24},
   issn =       {0022-0000},
   coden =      {JCSSBM},
   mrclass =    {03D05 (68Q70)},
   mrnumber =   {89i:03076},
   mrreviewer = {Hideki Yamasaki},
}

@article{Linna75,
   author =     {Linna, Matti},
   title =      {On $\omega$-words and $\omega$-computations},
   journal =    {Ann. Univ. Turku. Ser A I},
   volume =     168,
   year =       1975,
   pages =      {53},
   mrclass =    {68A30 (02F10)},
   mrnumber =   {56 \#1822},
   mrreviewer = {A. Ja. Dikovskii},
}

@article{LitovskiTimmerman87,
   author =     {Litovsky, I. and Timmerman, E.},
   title =      {On generators of rational $\omega$-power languages},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     53,
   year =       1987,
   number =     {2-3},
   pages =      {187--200},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68Q45},
   mrnumber =   {89a:68120},
   mrreviewer = {Wolfgang Thomas},
}

@book{Lothaire82,
   author =    {Lothaire, M.},
   title =     {Combinatorics on words},
   note =      {With a foreword by Roger Lyndon and a preface by Dominique 
                Perrin, Corrected reprint of the 1983 original, with a new 
                preface by Perrin},
   publisher = {Cambridge University Press},
   address =   {Cambridge},
   year =      1997,
   pages =     {xviii+238},
   isbn =      {0-521-59924-5},
   mrclass =   {68R15 (03D03 03D40 05A99 20M05)},
   mrnumber =  {98g:68134},
}

@inCollection{Louveau81,
   author =    {Louveau, A.},
   title =     {Some results in the {W}adge hierarchy of {B}orel sets},
   booktitle = {Cabal seminar 79--81},
   pages =     {28--55},
   publisher = {Springer},
   address =   {Berlin},
   year =      1983,
   mrclass =   {03E15},
   mrnumber =  {730 585},
}

@article{MalerStaiger93,
   author =     {Maler, Oded and Staiger, Ludwig},
   title =      {On syntactic congruences for $\omega$-languages},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     183,
   year =       1997,
   number =     1,
   pages =      {93--112},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68Q70 (20M35 68Q45)},
   mrnumber =   {98m:68188},
   mrreviewer = {I. Mezn{\'\i}k},
}

@article{Martin75,
   author =     {Martin, Donald A.},
   title =      {Borel determinacy},
   journal =    {Ann. of Math. (2)},
   volume =     102,
   year =       1975,
   number =     2,
   pages =      {363--371},
   mrclass =    {02K30 (90D05 04A15)},
   mrnumber =   {53 \#7785},
   mrreviewer = {John P. Burgess},
}

@article{McNaughton66,
   author =     {McNaughton, Robert},
   title =      {Testing and generating infinite sequences by a finite automaton},
   journal =    {Information and Control},
   volume =     9,
   year =       1966,
   pages =      {521--530},
   mrclass =    {02.88},
   mrnumber =   {35 \#4105},
   mrreviewer = {M. A. Harrison},
}

@article{McNaughton74,
   author =     {McNaughton, Robert},
   title =      {Algebraic decision procedures for local testability},
   journal =    {Math. Systems Theory},
   volume =     8,
   year =       1974,
   number =     1,
   pages =      {60--76},
   mrclass =    {02G05 (68A30)},
   mrnumber =   {52 \#13361},
   mrreviewer = {H. Jurgensen},
}

@book{McNaughtonPappert71,
   author =     {McNaughton, Robert and Papert, Seymour},
   title =      {Counter-free automata},
   note =       {With an appendix by William Henneman, M.I.T. Research Monograph, 
                 No. 65},
   publisher =  {The M.I.T. Press, Cambridge, Mass.-London},
   year =       1971,
   pages =      {xix+163},
   mrclass =    {94A30 (68A25)},
   mrnumber =   {51 \#7756},
   mrreviewer = {Richard L. Tenney},
}

@article{McNaughton93,
   author =     {McNaughton, Robert},
   title =      {Infinite games played on finite graphs},
   journal =    {Ann. Pure Appl. Logic},
   fjournal =   {Annals of Pure and Applied Logic},
   volume =     65,
   year =       1993,
   number =     2,
   pages =      {149--184},
   issn =       {0168-0072},
   coden =      {APALD7},
   mrclass =    {90D43 (05C20)},
   mrnumber =   {95a:90238},
   mrreviewer = {N. N. Petrov},
}

@article{Meyer69,
   author =  {Meyer, Albert R.},
   title =   {A note on star-free events},
   journal = {J. Assoc. Comput. Mach.},
   year =    1969,
   volume =  16,
   pages =   {220--225},
}

@inCollection{Meyer75,
   author =     {Meyer, Albert R.},
   title =      {Weak monadic second order theory of succesor is not 
                 elementary-recursive},
   booktitle =  {Logic Colloquium (Boston, Mass., 1972--1973)},
   pages =      {132--154. Lecture Notes in Math., Vol. 453},
   publisher =  {Springer},
   address =    {Berlin},
   year =       1975,
   mrclass =    {02F99},
   mrnumber =   {52 \#13358},
   mrreviewer = {G. E. Minc},
}

@inCollection{MeyerStockmeyer72,
   author =    {Meyer, Albert R. and Stockmeyer, Larry J.},
   title =     {The equivalence problem for regular expressions with squaring 
                requires exponential time},
   booktitle = {Proc. 13th IEEE Symp. on Switching and Automata Theory},
   publisher = {IEEE Computer Society},
   pages =     {125-129},
   year =      1972,
}

@article{Meznik87,
   author =     {Mezn{\'\i}k, Ivan},
   title =      {On some structural properties of a subclass of $\infty$-regular 
                 languages},
   journal =    {Discrete Appl. Math.},
   fjournal =   {Discrete Applied Mathematics. Combinatorial Algorithms, 
                 Optimization and Computer Science},
   volume =     18,
   year =       1987,
   number =     3,
   pages =      {315--319},
   issn =       {0166-218X},
   coden =      {DAMADU},
   mrclass =    {68Q45 (68Q50 68Q70)},
   mrnumber =   {89a:68123},
   mrreviewer = {A. A. Iskander},
}

@article{MichauxPoint86,
   author =   {Michaux, Christian and Point, Fran{\c{c}}oise},
   title =    {Les ensembles $k$-reconnaissables sont d\'efinissables dans 
               $\langle {\bf {N}},+,{V}\sb k\rangle$},
   journal =  {C. R. Acad. Sci. Paris S\'er. I Math.},
   fjournal = {Comptes Rendus des S\'eances de l'Acad\'emie des Sciences. 
               S\'erie I. Math\'ematique},
   volume =   303,
   year =     1986,
   number =   19,
   pages =    {939--942},
   issn =     {0249-6291},
   coden =    {CASMEI},
   mrclass =  {03C40 (03C62 03D05 68Q45)},
   mrnumber = {88a:03078},
}

@unpublished{Michel88,
   author =  {Michel, Max},
   title =   {Complementation is more difficult with automata on infinite words},
   year =    1988,
   note =    {CNET, Paris},
}

@article{MiyanoHayashi84,
   author =   {Miyano, Satoru and Hayashi, Takeshi},
   title =    {Alternating finite automata on $\omega$-words},
   journal =  {Theoret. Comput. Sci.},
   fjournal = {Theoretical Computer Science},
   volume =   32,
   year =     1984,
   number =   3,
   pages =    {321--330},
   issn =     {0304-3975},
   coden =    {TCSDI},
   mrclass =  {68Q75 (03D05)},
   mrnumber = {86e:68079},
}

@article{MoriyaYamasaki88,
   author =     {Moriya, Tetsuo and Yamasaki, Hideki},
   title =      {Accepting conditions for automata on $\omega$-languages},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     61,
   year =       1988,
   number =     {2-3},
   pages =      {137--147},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68Q45},
   mrnumber =   {90i:68058},
   mrreviewer = {I. M. Havel},
}

@article{Morse38,
   author =  {Morse, Marston and Hedlund, George A.},
   title =   {Symbolic Dynamics},
   journal = {Amer. J. Math.},
   year =    1938,
   volume =  60,
   pages =   {815--866},
}

@article{Morse2,
   author =     {Morse, Marston and Hedlund, Gustav A.},
   title =      {Symbolic dynamics {I}{I}. {S}turmian trajectories},
   journal =    {Amer. J. Math.},
   volume =     62,
   year =       1940,
   pages =      {1--42},
   mrclass =    {70.1X},
   mrnumber =   {1,123d},
   mrreviewer = {C. B. Tompkins},
}

@article{Morse44,
   author =     {Morse, Marston and Hedlund, Gustav A.},
   title =      {Unending chess, symbolic dynamics and a problem in semigroups},
   journal =    {Duke Math. J.},
   volume =     11,
   year =       1944,
   pages =      {1--7},
   mrclass =    {27.0X},
   mrnumber =   {5,202e},
   mrreviewer = {E. R. Lorch},
}

@book{Moschovakis80,
   author =     {Moschovakis, Yiannis N.},
   title =      {Descriptive set theory},
   publisher =  {North-Holland Publishing Co.},
   address =    {Amsterdam},
   year =       1980,
   pages =      {xii+637},
   isbn =       {0-444-85305-7},
   mrclass =    {03-02 (03D55 03E15 04A15 28A05 54H05)},
   mrnumber =   {82e:03002},
   mrreviewer = {Peter G. Hinman},
}

@article{Mostowski82,
   author =   {Mostowski, Andrzej W{\l}odzimierz},
   title =    {Determinancy of sinking automata on infinite trees and 
               inequalities between various {R}abin's pair indices},
   journal =  {Inform. Process. Lett.},
   fjournal = {Information Processing Letters},
   volume =   15,
   year =     1982,
   number =   4,
   pages =    {159--163},
   issn =     {0020-0190},
   coden =    {IFPLAT},
   mrclass =  {68D05},
   mrnumber = {83k:68045},
}

@inProceedings{Mostowski84,
   author =    {Mostowski, Andrzej W{\l}odzimierz},
   title =     {Regular expressions for infinite trees and a standard form of 
                automata},
   booktitle = {Computation Theory},
   editor =    {A. Skowron},
   series =    {Lecture Notes in Computer Science},
   volume =    208,
   pages =     {157-168},
   publisher = {Springer-Verlag},
   year =      1984,
}

@article{Mostowski87,
   author =     {Mostowski, Andrzej W{\l}odzimierz},
   title =      {Hierarchies of weak monadic formulas for two successors 
                 arithmetic},
   journal =    {J. Inform. Process. Cybernet.},
   fjournal =   {Journal of Information Processing and Cybernetics},
   volume =     23,
   year =       1987,
   number =     {10-11},
   pages =      {509--515},
   issn =       {0863-0593},
   mrclass =    {03D55 (03B15 03D05 68Q05 68Q70)},
   mrnumber =   {89c:03076},
   mrreviewer = {Cristian Calude},
}

@article{Muchnik84,
   author =  {Muchnik, A.A.},
   title =   {Games on infinite trees and automata with dead-end markers - a 
              new proof of the decidability of the monadic theory of two 
              successors},
   journal = {Semiotics and Information},
   year =    1984,
   volume =  24,
   pages =   {17--40},
   note =    {(in Russian)},
}

@article{Muchnik87,
   author =  {Muchnik, A.A},
   title =   {Alternating automata on infinite trees},
   journal = {Theoret. Comput. Sci.},
   year =    1987,
   volume =  54,
   pages =   {267--276},
}

@inProceedings{Muller63,
   author =    {Muller, David E.},
   title =     {Infinite sequences and finite machines},
   booktitle = {Switching Theory and Logical Design, Proc. Fourth Annual Symp. 
                IEEE},
   publisher = {IEEE},
   year =      1963,
   pages =     {3--16},
}

@inCollection{MullerSaoudiSchupp86,
   author =     {Muller, David E. and Saoudi, Ahmed and Schupp, Paul E.},
   title =      {Alternating automata, the weak monadic theory of the tree, and 
                 its complexity},
   booktitle =  {Automata, languages and programming (Rennes, 1986)},
   pages =      {275--283},
   publisher =  {Springer},
   address =    {Berlin},
   year =       1986,
   mrclass =    {03D05 (03B15 03B25 03D15 68Q15)},
   mrnumber =   {88d:03079},
   mrreviewer = {P. C. Gilmore},
}

@inCollection{MullerSchupp85a,
   author =    {Muller, David E. and Schupp, Paul E.},
   title =     {Alternating automata on infinite objects. {D}eterminacy and 
                {R}abin's theorem},
   booktitle = {Automata on infinite words (Le Mont-Dore, 1984)},
   pages =     {100--107},
   publisher = {Springer},
   address =   {Berlin},
   year =      1985,
   mrclass =   {68Q05 (03B15 03B25 03D05)},
   mrnumber =  {87k:68036},
}

@article{MullerSchupp85b,
   author =     {Muller, David E. and Schupp, Paul E.},
   title =      {The theory of ends, pushdown automata, and second-order logic},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     37,
   year =       1985,
   number =     1,
   pages =      {51--75},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {03B25 (03B15 03D05 05C25 68Q05)},
   mrnumber =   {87h:03014},
   mrreviewer = {Wolfgang Thomas},
}

@article{MullerSchupp87,
   author =     {Muller, David E. and Schupp, Paul E.},
   title =      {Alternating automata on infinite trees},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     54,
   year =       1987,
   number =     {2-3},
   pages =      {267--276},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68Q70 (03D05 68Q05)},
   mrnumber =   {89g:68054},
   mrreviewer = {Wolfgang Thomas},
}

@article{MullerSaoudiSchupp92a,
   author =     {Muller, David E. and Saoudi, Ahmed and Schupp, Paul E.},
   title =      {Alternating automata, the weak monadic theory of trees and its 
                 complexity},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     97,
   year =       1992,
   number =     2,
   pages =      {233--244},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {03D15 (03-02 03C85 03D05 68-02 68Q05 68Q25 68Q70)},
   mrnumber =   {93h:03058},
   mrreviewer = {George Tourlakis},
}

@article{MullerSaoudiSchupp92b,
   author =     {Saoudi, Ahmed and Muller, David E. and Schupp, Paul E.},
   title =      {Finite state processes, ${\bf {Z}}$-temporal logic and the 
                 monadic theory of the integers},
   journal =    {Internat. J. Found. Comput. Sci.},
   fjournal =   {International Journal of Foundations of Computer Science},
   volume =     3,
   year =       1992,
   number =     3,
   pages =      {233--244},
   issn =       {0129-0541},
   mrclass =    {03D05 (03B15 03B45 03D25 68Q45)},
   mrnumber =   {94c:03052},
   mrreviewer = {Peter Clote},
}

@article{MullerSchupp95,
   author =     {Muller, David E. and Schupp, Paul E.},
   title =      {Simulating alternating tree automata by nondeterministic 
                 automata: new results and new proofs of the theorems of {R}abin, 
                 {M}c{N}aughton and {S}afra},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     141,
   year =       1995,
   number =     {1-2},
   pages =      {69--107},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {03D05 (03B15 03B25 68Q60 68Q68 90D44)},
   mrnumber =   {96k:03089},
   mrreviewer = {Zdzis{\l}aw Grodzki},
}

@article{Nivat78,
   author =   {Nivat, Maurice},
   title =    {Sur les ensembles de mots infinis engendr\'es par une grammaire 
               alg\'ebrique},
   journal =  {RAIRO Inform. Th\'eor.},
   fjournal = {RAIRO Informatique Th\'eorique},
   volume =   12,
   year =     1978,
   number =   3,
   pages =    {259--278, v},
   issn =     {0399-0540},
   coden =    {RSITD7},
   mrclass =  {68F05},
   mrnumber = {80d:68093},
}

@inCollection{Nivat79,
   author =     {Nivat, M.},
   title =      {Infinite words, infinite trees, infinite computations},
   booktitle =  {Foundations of computer science, III (Third Adv. Course, 
                 Amsterdam, 1978), Part 2},
   pages =      {1--52},
   publisher =  {Math. Centrum},
   address =    {Amsterdam},
   year =       1979,
   mrclass =    {68B10 (03D75 68C30)},
   mrnumber =   {82e:68015},
   mrreviewer = {Max Dauchet},
}

@article{NivatPerrin82,
   author =  {Nivat, Maurice and Perrin, Dominique},
   title =   {Ensembles reconnaissables de mots biinfinis},
   journal = {14th ACM Symp. of theory of Computing},
   year =    1982,
   pages =   {47--59},
   volume =  {XXXVIII},
}

@article{NivatPerrin86,
   author =     {Nivat, Maurice and Perrin, Dominique},
   title =      {Ensembles reconnaissables de mots biinfinis},
   journal =    {Canad. J. Math.},
   fjournal =   {Canadian Journal of Mathematics. Journal Canadien de 
                 Math\'ematiques},
   volume =     38,
   year =       1986,
   number =     3,
   pages =      {513--537},
   issn =       {0008-414X},
   coden =      {CJMAAB},
   mrclass =    {68Q45 (03D05)},
   mrnumber =   {87h:68098},
   mrreviewer = {Ronald E. Prather},
}

@inProceedings{Park81,
   author =    {Park, D.},
   title =     {Concurrency and automata on infinite sequences},
   booktitle = {Proc. of the 5th GI Conference, Karlsruhe},
   series =    {Lecture Notes in Comput. Sci},
   publisher = {Springer Verlag, Berlin, Heidelberg, New York},
   editor =    {P. Deussen},
   year =      1981,
   volume =    104,
   pages =     {167--183},
}

@inCollection{Pecuchet85a,
   author =    {P{\'e}cuchet, Jean-Pierre},
   title =     {Automates boustrophedon sur des mots infinis},
   booktitle = {Automata on infinite words (Le Mont-Dore, 1984)},
   pages =     {47--54},
   publisher = {Springer},
   address =   {Berlin},
   year =      1985,
   mrclass =   {68Q05 (03D05 20M35 68Q45)},
   mrnumber =  {87d:68022},
}

@article{Pecuchet85b,
   author =     {P{\'e}cuchet, Jean-Pierre},
   title =      {Automates boustroph\'edon et mots infinis},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     35,
   year =       1985,
   number =     1,
   pages =      {115--122},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68Q45},
   mrnumber =   {86i:68066},
   mrreviewer = {Jean-Eric Pin},
}

@inProceedings{Pecuchet86a,
   author =    {P{\'e}cuchet, Jean-Pierre},
   title =     {Vari{\'e}t{\'e}s de semigroupes et mots infinis},
   booktitle = {STACS 86},
   series =    {Lecture Notes in Comput. Sci.},
   publisher = {Springer Verlag, Berlin, Heidelberg, New York},
   editor =    {B. Monien and G. Vidal-Naquet},
   year =      1986,
   volume =    210,
   pages =     {180--191},
}

@inCollection{Pecuchet86b,
   author =    {P{\'e}cuchet, Jean-Pierre},
   title =     {\'{E}tude syntaxique des parties reconnaissables de mots infinis},
   booktitle = {Automata, languages and programming (Rennes, 1986)},
   pages =     {294--303},
   publisher = {Springer},
   address =   {Berlin},
   year =      1986,
   mrclass =   {68Q45 (20M07)},
   mrnumber =  {87j:68069},
}

@article{Pecuchet88,
   author =     {P{\'e}cuchet, Jean-Pierre},
   title =      {\'{E}tude syntaxique des parties reconnaissables de mots infinis},
   note =       {Thirteenth International Colloquium on Automata, Languages and 
                 Programming (Rennes, 1986)},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     58,
   year =       1988,
   number =     {1-3},
   pages =      {231--248},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68Q70 (68Q45)},
   mrnumber =   {90d:68057},
   mrreviewer = {Andr{\'e} Lentin},
}

@article{Pecuchet86c,
   author =   {P{\'e}cuchet, Jean-Pierre},
   title =    {On the complementation of {B}\"uchi automata},
   journal =  {Theoret. Comput. Sci.},
   fjournal = {Theoretical Computer Science},
   volume =   47,
   year =     1986,
   number =   1,
   pages =    {95--98},
   issn =     {0304-3975},
   coden =    {TCSDI},
   mrclass =  {68Q05 (03D05 68Q15)},
   mrnumber = {88b:68045},
}

@techReport{Peikert85,
   author =      {Peikert, Ronald},
   title =       {$\omega$-regular languages and propositional temporal logic},
   institution = {ETH Z{\"u}rich},
   volume =      {85-01},
   year =        1985,
}

@article{Perrin82,
   author =   {Perrin, Dominique},
   title =    {Vari\'et\'es de semigroupes et mots infinis},
   journal =  {C. R. Acad. Sci. Paris S\'er. I Math.},
   fjournal = {Comptes Rendus des S\'eances de l'Acad\'emie des Sciences. 
               S\'erie I. Math\'ematique},
   volume =   295,
   year =     1982,
   number =   10,
   pages =    {595--598},
   issn =     {0249-6321},
   coden =    {CHASAP},
   mrclass =  {20M35 (68F05)},
   mrnumber = {83m:20095},
}

@inCollection{Perrin83,
   author =    {Perrin, Dominique},
   title =     {Vari\'et\'es de semigroupes et mots infinis},
   booktitle = {Automata, languages and programming (Barcelona, 1983)},
   pages =     {610--616},
   publisher = {Springer},
   address =   {Berlin},
   year =      1983,
   mrclass =   {68Q45 (03D05 20M05 20M07)},
   mrnumber =  {85f:68046},
}

@inCollection{Perrin84,
   author =    {Perrin, Dominique},
   title =     {Recent results on automata and infinite words},
   booktitle = {Mathematical foundations of computer science, 1984 (Prague, 1984)},
   pages =     {134--148},
   publisher = {Springer},
   address =   {Berlin},
   year =      1984,
   mrclass =   {68Q70 (03D05)},
   mrnumber =  {86i:68098},
}

@inCollection{Perrin85,
   author =     {Perrin, Dominique},
   title =      {An introduction to finite automata on infinite words},
   booktitle =  {Automata on infinite words (Le Mont-Dore, 1984)},
   pages =      {2--17},
   publisher =  {Springer},
   address =    {Berlin},
   year =       1985,
   mrclass =    {68Q05 (03D05 20M05 20M35 68Q70)},
   mrnumber =   {87d:68023},
   mrreviewer = {Howard Straubing},
}

@inCollection{Perrin90,
   author =    {Perrin, Dominique},
   title =     {Finite automata},
   booktitle = {Handbook of theoretical computer science, Vol.\ B},
   pages =     {1--57},
   publisher = {Elsevier},
   address =   {Amsterdam},
   year =      1990,
   mrclass =   {68Q68},
   mrnumber =  {1 127 186},
}

@article{PerrinPin86,
   author =     {Perrin, Dominique and Pin, Jean-Eric},
   title =      {First-order logic and star-free sets},
   journal =    {J. Comput. System Sci.},
   fjournal =   {Journal of Computer and System Sciences},
   volume =     32,
   year =       1986,
   number =     3,
   pages =      {393--406},
   issn =       {0022-0000},
   coden =      {JCSSBM},
   mrclass =    {68Q45 (03D05)},
   mrnumber =   {88a:68065},
   mrreviewer = {Howard Straubing},
}

@inCollection{PerrinPin95,
   author =     {Perrin, Dominique and Pin, Jean-Eric},
   title =      {Semigroups and automata on infinite words},
   booktitle =  {Semigroups, formal languages and groups (York, 1993)},
   pages =      {49--72},
   publisher =  {Kluwer Acad. Publ.},
   address =    {Dordrecht},
   year =       1995,
   mrclass =    {68Q45 (20M35 68R15)},
   mrnumber =   {99f:68123},
   mrreviewer = {Dong Yang Long},
}

@inProceedings{PerrinSchupp86,
   author =    {Perrin, Dominique and Schupp, Paul E.},
   title =     {Automata on the integers, recurrence, distinguishability and the 
                equivalence and decidability of monadic theories},
   booktitle = {Proc. 1st IEEE Symp. on Logic in Computer Science},
   publisher = {IEEE},
   year =      1986,
   pages =     {301--304},
}

@article{Pin84,
   author =     {Pin, Jean-Eric},
   title =      {Hi\'erarchies de concat\'enation},
   journal =    {RAIRO Inform. Th\'eor.},
   fjournal =   {RAIRO Informatique Th\'eorique},
   volume =     18,
   year =       1984,
   number =     1,
   pages =      {23--46},
   issn =       {0399-0540},
   coden =      {RSITD7},
   mrclass =    {68Q45},
   mrnumber =   {85k:68048},
   mrreviewer = {Howard Straubing},
}

@inCollection{Pin85,
   author =     {Pin, Jean-Eric},
   title =      {Star-free $\omega$-languages and first order logic},
   booktitle =  {Automata on infinite words (Le Mont-Dore, 1984)},
   pages =      {56--67},
   publisher =  {Springer},
   address =    {Berlin},
   year =       1985,
   mrclass =    {68Q45 (03D05)},
   mrnumber =   {87f:68049},
   mrreviewer = {Wolfgang Thomas},
}

@book{Pin86,
   author =    {Pin, J.-E.},
   title =     {Varieties of formal languages},
   note =      {With a preface by M.-P. Sch\"utzenberger, Translated from the 
                French by A. Howie},
   publisher = {Plenum Publishing Corp.},
   address =   {New York},
   year =      1986,
   pages =     {x+138},
   isbn =      {0-306-42294-8},
   mrclass =   {68Q45 (03D05 20M35 68-02)},
   mrnumber =  {89a:68125},
}

@inCollection{Pin95a,
   author =     {Pin, Jean-Eric},
   title =      {Finite semigroups and recognizable languages: an introduction},
   booktitle =  {Semigroups, formal languages and groups (York, 1993)},
   pages =      {1--32},
   publisher =  {Kluwer Acad. Publ.},
   address =    {Dordrecht},
   year =       1995,
   mrclass =    {68Q45 (20M35 68Q70)},
   mrnumber =   {99f:68124},
   mrreviewer = {Dong Yang Long},
}

@article{Pin95b,
   author =  {Pin, Jean-Eric},
   title =   {A variety theorem without complementation},
   journal = {Russian Mathematics (Iz. VUZ)},
   year =    1995,
   volume =  39,
   pages =   {80--90},
}

@article{Pin95f,
   author =   {Pin, Jean-Eric},
   title =    {A negative answer to a question of {W}ilke on varieties of 
               $\omega$-languages},
   journal =  {Inform. Process. Lett.},
   fjournal = {Information Processing Letters},
   volume =   56,
   year =     1995,
   number =   4,
   pages =    {197--200},
   issn =     {0020-0190},
   coden =    {IFPLAT},
   mrclass =  {68Q45 (68Q70)},
   mrnumber = {96k:68117},
}

@article{Pin96c,
   author =     {Pin, Jean-Eric},
   title =      {Logic, semigroups and automata on words},
   journal =    {Ann. Math. Artificial Intelligence},
   fjournal =   {Annals of Mathematics and Artificial Intelligence},
   volume =     16,
   year =       1996,
   number =     {1-4},
   pages =      {343--384},
   issn =       {1012-2443},
   mrclass =    {03D05 (03B15 68Q15 68Q70)},
   mrnumber =   {97d:03054},
   mrreviewer = {Damian Niwi{\'n}ski},
}

@conference{Pin98a,
   author =    {Pin, Jean-Eric},
   title =     {Positive varieties and infinite words},
   booktitle = {Latin'98},
   series =    {Lecture Notes in Comput. Sci.},
   publisher = {Springer Verlag, Berlin, Heidelberg, New York},
   editor =    {C.L. Lucchesi and A.V. Moura},
   year =      1998,
   volume =    1380,
   pages =     {76--87},
}

@article{PinWeil96a,
   author =     {Pin, J.-E. and Weil, P.},
   title =      {A {R}eiterman theorem for pseudovarieties of finite first-order 
                 structures},
   journal =    {Algebra Universalis},
   fjournal =   {Algebra Universalis},
   volume =     35,
   year =       1996,
   number =     4,
   pages =      {577--595},
   issn =       {0002-5240},
   coden =      {AGUVA3},
   mrclass =    {03C05 (03C13 08A70 08C99 22A30)},
   mrnumber =   {97g:03041},
   mrreviewer = {Paul Bankston},
}

@inCollection{Pin97a,
   author =     {Pin, Jean-Eric},
   title =      {Syntactic semigroups},
   booktitle =  {Handbook of formal languages, Vol.\ 1},
   pages =      {679--746},
   publisher =  {Springer},
   address =    {Berlin},
   year =       1997,
   mrclass =    {68Q70 (03D05 20M35 68Q45)},
   mrnumber =   {98i:68205},
   mrreviewer = {A. A. Iskander},
}

@conference{PinWeil95a,
   author =    {Pin, Jean-Eric and Weil, Pascal},
   title =     {Polynomial closure and unambiguous product},
   booktitle = {22th ICALP},
   publisher = {Springer},
   address =   {Berlin},
   series =    {Lecture Notes in Comput. Sci.},
   number =    944,
   year =      1995,
   pages =     {348--359},
}

@article{PinWeil97a,
   author =     {Pin, J.-E. and Weil, P.},
   title =      {Polynomial closure and unambiguous product},
   journal =    {Theory Comput. Syst.},
   fjournal =   {Theory of Computing Systems},
   volume =     30,
   year =       1997,
   number =     4,
   pages =      {383--422},
   issn =       {1432-4350},
   coden =      {TCSYFI},
   mrclass =    {68Q70 (03D05)},
   mrnumber =   {98i:68206},
   mrreviewer = {Howard Straubing},
}

@inCollection{Pnueli77,
   author =    {Manna, Zohar and Pnueli, Amir},
   title =     {The modal logic of programs},
   booktitle = {Automata, languages and programming (Sixth Colloq., Graz, 1979)},
   pages =     {385--409},
   publisher = {Springer},
   address =   {Berlin},
   year =      1979,
   mrclass =   {68B10 (03B45 68C01)},
   mrnumber =  {81d:68022},
}

@article{Quine46,
   author =     {Quine, Willard V.},
   title =      {Concatenation as a basis for arithmetic},
   journal =    {J. Symbolic Logic},
   volume =     11,
   year =       1946,
   pages =      {105--114},
   mrclass =    {02.0X},
   mrnumber =   {8,307b},
   mrreviewer = {M. H. A. Newman},
}

@article{Rabin68,
   author =     {Rabin, Michael O.},
   title =      {Decidability of second-order theories and automata on infinite 
                 trees.},
   journal =    {Bull. Amer. Math. Soc.},
   volume =     74,
   year =       1968,
   pages =      {1025--1029},
   mrclass =    {02.74},
   mrnumber =   {38 \#44},
   mrreviewer = {J. R. B{\"u}chi},
}

@article{Rabin69,
   author =     {Rabin, Michael O.},
   title =      {Decidability of second-order theories and automata on infinite 
                 trees.},
   journal =    {Trans. Amer. Math. Soc.},
   volume =     141,
   year =       1969,
   pages =      {1--35},
   mrclass =    {02.32},
   mrnumber =   {40 \#30},
   mrreviewer = {Walter Oberschelp},
}

@inCollection{Rabin70,
   author =    {Rabin, Michael O.},
   title =     {Weakly definable relations and special automata},
   booktitle = {Mathematical Logic and Foundations of Set Theory},
   editor =    {Y. Bar-Hillel},
   year =      1970,
   pages =     {1-23},
   publisher = {North Holland},
}

@book{Rabin72,
   author =     {Rabin, Michael O.},
   title =      {Automata on infinite objects and {C}hurch's problem},
   note =       {Conference Board of the Mathematical Sciences Regional Conference 
                 Series in Mathematics, No. 13},
   publisher =  {American Mathematical Society},
   address =    {Providence, R.I.},
   year =       1972,
   pages =      {iii+22},
   mrclass =    {02F10},
   mrnumber =   {48 \#75},
   mrreviewer = {D. Rodding},
}

@inCollection{Rabin77,
   author =    {Rabin, Michael O.},
   title =     {Decidable theories},
   booktitle = {Handbook of Mathematical Logic},
   publisher = {North Holland},
   year =      1977,
   pages =     {595-629},
}

@article{RabinScott59,
   author =     {Rabin, Michael O. and Scott, Dana},
   title =      {Finite automata and their decision problems},
   journal =    {IBM J. Res. Develop.},
   volume =     3,
   year =       1959,
   pages =      {114--125},
   mrclass =    {93.00 (02.00)},
   mrnumber =   {21 \#2559},
   mrreviewer = {J. McCarthy},
}

@phdThesis{Rackoff72,
   author =  {Rackoff, Charles W.},
   title =   {The emptyness and complementation problem for automata on 
              infinite trees},
   year =    1972,
   school =  {MIT},
}

@article{Ramsey29,
   author =  {Ramsey, Frank D.},
   title =   {On a problem of formal logic},
   journal = {Proc. of the London Math. Soc.},
   year =    1929,
   volume =  30,
   pages =   {338--384},
}

@inProceedings{Rauzy85,
   author =    {Rauzy, G{\'e}rard},
   title =     {Mots infinis en arithm{\'e}tique},
   booktitle = {Automata on Infinite Words},
   series =    {Lecture Notes in Comput. Sci.},
   publisher = {Springer Verlag, Berlin, Heidelberg, New York},
   editor =    {M. Nivat and D. Perrin},
   year =      1985,
   volume =    192,
   pages =     {165--171},
}

@article{Redziejowski86,
   author =     {Redziejowski, Roman R.},
   title =      {Infinite-word languages and continuous mappings},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     43,
   year =       1986,
   number =     1,
   pages =      {59--79},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68Q45 (03D05)},
   mrnumber =   {87k:68077},
   mrreviewer = {Joffroy Beauquier},
}

@article{Reiterman82,
   author =   {Reiterman, Jan},
   title =    {The {B}irkhoff theorem for finite algebras},
   journal =  {Algebra Universalis},
   fjournal = {Algebra Universalis},
   volume =   14,
   year =     1982,
   number =   1,
   pages =    {1--10},
   issn =     {0002-5240},
   mrclass =  {08B05 (03C05 03C13)},
   mrnumber = {84c:08008},
}

@inCollection{Reutenauer79,
   author =    {Reutenauer, Christophe},
   title =     {Sur les vari\'et\'es de langages et de mono\"\i des},
   booktitle = {Theoretical computer science (Fourth GI Conf., Aachen, 1979)},
   pages =     {260--265},
   publisher = {Springer},
   address =   {Berlin},
   year =      1979,
   mrclass =   {68F05},
   mrnumber =  {82a:68154},
}

@book{RozenbergSalomaa80,
   author =     {Rozenberg, Grzegorz and Salomaa, Arto},
   title =      {The mathematical theory of {L} systems},
   publisher =  {Academic Press Inc. [Harcourt Brace Jovanovich Publishers]},
   address =    {New York},
   year =       1980,
   pages =      {xvi+352},
   isbn =       {0-12-597140-0},
   mrclass =    {68D22 (68F05 68F10 92A05)},
   mrnumber =   {82g:68053},
   mrreviewer = {Gheorghe P{\u{a}}un},
}

@book{Rosenstein82,
   author =     {Rosenstein, Joseph G.},
   title =      {Linear orderings},
   publisher =  {Academic Press Inc. [Harcourt Brace Jovanovich Publishers]},
   address =    {New York},
   year =       1982,
   pages =      {xvii+487},
   isbn =       {0-12-597680-1},
   mrclass =    {06-02 (03C65)},
   mrnumber =   {84m:06001},
   mrreviewer = {W. Hodges},
}

@inProceedings{Safra88,
   author =    {Safra, Shmuel},
   title =     {On the complexity of the {$\omega$}-automata},
   booktitle = {Proc. 29th Ann. IEEE Symp. on Foundations of Computer Science},
   publisher = {IEEE},
   year =      1988,
   pages =     {319--327},
}

@inCollection{Safra92,
   author =    {Safra, Shmuel},
   title =     {Exponential determinization for $\omega$-automata with strong 
                fairness condition},
   booktitle = {Proc. 24th ACM Symp. on the Theory of Computing},
   publisher = {ACM},
   year =      1992,
   pages =     {275-282},
}

@article{Savitch70,
   author =     {Savitch, Walter J.},
   title =      {Relationships between nondeterministic and deterministic tape 
                 complexities},
   journal =    {J. Comput. System. Sci.},
   volume =     4,
   year =       1970,
   pages =      {177--192},
   mrclass =    {94.40},
   mrnumber =   {42 \#1605},
   mrreviewer = {H. Maurer},
}

@article{Schutzenberger65,
   author =  {Sch{\"u}tzenberger, Marcel-Paul},
   title =   {On finite monoids having only trivial subgroups},
   journal = {Information and Control},
   year =    1965,
   volume =  8,
   pages =   {190--194},
}

@inCollection{Schutzenberger73,
   author =     {Sch{\"u}tzenberger, M.},
   title =      {\`{A} propos des relations rationelles fonctionnelles},
   booktitle =  {Automata, languages and programming (Proc. Sympos., Rocquencourt, 
                 1972)},
   pages =      {103--114},
   publisher =  {North Holland},
   address =    {Amsterdam},
   year =       1973,
   mrclass =    {68A25 (20M35 68A30)},
   mrnumber =   {52 \#7205},
   mrreviewer = {Y. Zalcstein},
}

@inCollection{Schutzenberger75,
   author =     {Sch{\"u}tzenberger, M. P.},
   title =      {Sur certaines op\'erations de fermeture dans les langages 
                 rationnels},
   booktitle =  {Symposia Mathematica, Vol. XV (Convegno di Informatica Teorica, 
                 INDAM, Roma, 1973)},
   pages =      {245--253},
   publisher =  {Academic Press},
   address =    {London},
   year =       1975,
   mrclass =    {68A30},
   mrnumber =   {54 \#9182},
   mrreviewer = {Andre Lentin},
}

@inProceedings{Selivanov95a,
   author =    {Selivanov, V. L.},
   title =     {Fine hierarchies of $\omega$-rational languages},
   booktitle = {TAPSOFT'95:Theory and Practice of Software Development},
   series =    {Lecture Notes in Comput. Sci.},
   publisher = {Springer Verlag, Berlin},
   year =      1995,
   pages =     {277--287},
}

@article{Selivanov95b,
   author =     {Selivanov, V. L.},
   title =      {Fine hierarchies and {B}oolean terms},
   journal =    {J. Symbolic Logic},
   fjournal =   {The Journal of Symbolic Logic},
   volume =     60,
   year =       1995,
   number =     1,
   pages =      {289--317},
   issn =       {0022-4812},
   coden =      {JSYLA6},
   mrclass =    {03D55 (03D15 03E15)},
   mrnumber =   {96f:03036},
   mrreviewer = {Peter G. Hinman},
}

@article{Selivanov98,
   author =     {Selivanov, Victor},
   title =      {Fine hierarchy of regular $\omega$-languages},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     191,
   year =       1998,
   number =     {1-2},
   pages =      {37--59},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68Q45 (03D05 03E15 68Q68)},
   mrnumber =   {99f:68126},
   mrreviewer = {Hideki Yamasaki},
}

@article{Semenov80,
   author =  {Semenov, Alexei},
   title =   {On certain extensions of the arithmetic of addition of natural 
              numbers},
   journal = {Math. USSR Izvestiya},
   year =    1980,
   volume =  15,
   pages =   {401--418},
}

@inCollection{Semenov84b,
   author =     {Semenov, Alexei L.},
   title =      {Decidability of monadic theories},
   booktitle =  {Mathematical foundations of computer science, 1984 (Prague, 1984)},
   pages =      {162--175},
   publisher =  {Springer},
   address =    {Berlin},
   year =       1984,
   mrclass =    {03B25 (03D05)},
   mrnumber =   {86i:03006},
   mrreviewer = {Roman Murawski},
}

@article{Semenov84a,
   author =     {Semenov, Alexei L.},
   title =      {Logical theories of one-place functions on the natural number 
                 series},
   journal =    {Izv. Akad. Nauk SSSR Ser. Mat.},
   fjournal =   {Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya},
   volume =     47,
   year =       1983,
   number =     3,
   pages =      {623--658},
   issn =       {0373-2436},
   mrclass =    {03B25 (68C01)},
   mrnumber =   {84i:03033},
   mrreviewer = {Roman Murawski},
}

@article{Shelah75,
   author =     {Shelah, Saharon},
   title =      {The monadic theory of order},
   journal =    {Ann. of Math. (2)},
   volume =     102,
   year =       1975,
   number =     3,
   pages =      {379--419},
   mrclass =    {02G05 (02H10)},
   mrnumber =   {58 \#10390},
   mrreviewer = {Andreas Blass},
}

@book{Siefkes70,
   author =     {Siefkes, Dirk},
   title =      {B\"uchi's monadic second order successor arithmetic},
   publisher =  {Springer-Verlag},
   address =    {Berlin},
   year =       1970,
   pages =      {xii+130},
   mrclass =    {02.72},
   mrnumber =   {44 \#6488},
   mrreviewer = {K. Sch{\"u}tte},
}

@inProceedings{Simon75,
   author =    {Simon, Imre},
   title =     {Piecewise testable events},
   booktitle = {Proc. 2nd GI Conf.},
   series =    {Lecture Notes in Comp. Sci.},
   publisher = {Springer Verlag, Berlin, Heidelberg, New York},
   editor =    {H. Brackage},
   year =      1975,
   volume =    33,
   pages =     {214--222},
}

@inCollection{Simon84,
   author =    {Simon, Imre},
   title =     {Word {R}amsey theorems},
   booktitle = {Graph theory and combinatorics (Cambridge, 1983)},
   pages =     {283--291},
   publisher = {Academic Press},
   address =   {London},
   year =      1984,
   mrclass =   {05A99},
   mrnumber =  {86k:05013},
}

@article{Simon90,
   author =     {Simon, Imre},
   title =      {Factorization forests of finite height},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     72,
   year =       1990,
   number =     1,
   pages =      {65--94},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68R15 (05D10 20M05)},
   mrnumber =   {91j:68105},
   mrreviewer = {Andr{\'e} Lentin},
}

@inCollection{Simon93,
   author =    {Simon, Imre},
   title =     {The product of rational languages},
   booktitle = {Automata, languages and programming (Lund, 1993)},
   pages =     {430--444},
   publisher = {Springer},
   address =   {Berlin},
   year =      1993,
   mrclass =   {68Q45 (68Q70)},
   mrnumber =  {94k:68117},
}

@phdThesis{Simonnet92,
   author =  {Simonnet, Pierre},
   title =   {Automates et Th\'{e}orie descriptive},
   school =  {Universit\'{e} Paris VII},
   year =    1992,
}

@article{SistlaVardiWolper87,
   author =     {Sistla, A. Prasad and Vardi, Moshe Y. and Wolper, Pierre},
   title =      {The complementation problem for {B}\"uchi automata with 
                 applications to temporal logic},
   note =       {Twelfth international colloquium on automata, languages and 
                 programming (Nafplion, 1985)},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     49,
   year =       1987,
   number =     {2-3},
   pages =      {217--237},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68Q05 (03B45 03D05 68Q15 68Q60)},
   mrnumber =   {89a:68056},
   mrreviewer = {Robert P. Kurshan},
}

@article{Skurczynski93,
   author =   {Skurczy{\'n}ski, Jerzy},
   title =    {The {B}orel hierarchy is infinite in the class of regular sets of 
               trees},
   journal =  {Theoret. Comput. Sci.},
   fjournal = {Theoretical Computer Science},
   volume =   112,
   year =     1993,
   number =   2,
   pages =    {413--418},
   issn =     {0304-3975},
   coden =    {TCSDI},
   mrclass =  {03E15 (54H05 68Q70)},
   mrnumber = {94d:03104},
}

@inCollection{Skurczynski89,
   author =    {Skurczy{\'n}ski, Jerzy},
   title =     {The {B}orel hierarchy is infinite in the class of regular sets of 
                trees},
   booktitle = {Fundamentals of computation theory (Szeged, 1989)},
   pages =     {416--423},
   publisher = {Springer},
   address =   {New York},
   year =      1989,
   mrclass =   {03D05 (03D55 68Q70)},
   mrnumber =  {91g:03080},
}

@article{Staiger80,
   author =   {Staiger, Ludwig},
   title =    {A note on connected $\omega$-languages},
   journal =  {Elektron. Informationsverarb. Kybernet.},
   fjournal = {Elektronische Informationsverarbeitung und Kybernetik},
   volume =   16,
   year =     1980,
   number =   {5-6},
   pages =    {245--251},
   issn =     {0013-5712},
   coden =    {EIVKAX},
   mrclass =  {68F05},
   mrnumber = {81m:68062},
}

@article{Staiger83,
   author =   {Staiger, Ludwig},
   title =    {Finite-state $\omega$-languages},
   journal =  {J. Comput. System Sci.},
   fjournal = {Journal of Computer and System Sciences},
   volume =   27,
   year =     1983,
   number =   3,
   pages =    {434--448},
   issn =     {0022-0000},
   coden =    {JCSSBM},
   mrclass =  {68F10},
   mrnumber = {84m:68076},
}

@article{Staiger84,
   author =   {Staiger, Ludwig},
   title =    {Projection lemmas for $\omega$-languages},
   journal =  {Theoret. Comput. Sci.},
   fjournal = {Theoretical Computer Science},
   volume =   32,
   year =     1984,
   number =   3,
   pages =    {331--337},
   issn =     {0304-3975},
   coden =    {TCSDI},
   mrclass =  {68Q45 (03D05)},
   mrnumber = {86g:68096},
}

@article{Staiger85,
   author =   {Staiger, Ludwig},
   title =    {The entropy of finite-state $\omega$-languages},
   journal =  {Problems Control Inform. Theory/Problemy Upravlen. Teor. Inform.},
   fjournal = {Problems of Control and Information Theory. Problemy Upravlenija 
               i Teorii Informacii},
   volume =   14,
   year =     1985,
   number =   5,
   pages =    {383--392},
   issn =     {0370-2529},
   coden =    {PUTIAI},
   mrclass =  {68Q45},
   mrnumber = {87b:68061},
}

@article{Staiger86a,
   author =     {Staiger, Ludwig},
   title =      {Hierarchies of recursive $\omega$-languages},
   journal =    {Elektron. Informationsverarb. Kybernet.},
   fjournal =   {Elektronische Informationsverarbeitung und Kybernetik},
   volume =     22,
   year =       1986,
   number =     {5-6},
   pages =      {219--241},
   issn =       {0013-5712},
   coden =      {EIVKAX},
   mrclass =    {68Q45 (03D05)},
   mrnumber =   {88b:68109},
   mrreviewer = {Matti Linna},
}

@article{Staiger86b,
   author =     {Staiger, Ludwig},
   title =      {On infinitary finite length codes},
   journal =    {RAIRO Inform. Th\'eor. Appl.},
   fjournal =   {RAIRO Informatique Th\'eorique et Applications},
   volume =     20,
   year =       1986,
   number =     4,
   pages =      {483--494},
   issn =       {0296-1598},
   mrclass =    {94B45 (68Q45)},
   mrnumber =   {88m:94034},
   mrreviewer = {H. J{\"u}rgensen},
}

@article{Staiger87a,
   author =     {Staiger, Ludwig},
   title =      {Sequential mappings of $\omega$-languages},
   journal =    {RAIRO Inform. Th\'eor. Appl.},
   fjournal =   {RAIRO Informatique Th\'eorique et Applications},
   volume =     21,
   year =       1987,
   number =     2,
   pages =      {147--173},
   issn =       {0296-1598},
   mrclass =    {68Q45 (68Q05)},
   mrnumber =   {89a:68127},
   mrreviewer = {Wolfgang Thomas},
}

@article{Staiger87b,
   author =     {Staiger, Ludwig},
   title =      {Research in the theory of $\omega$-languages},
   note =       {Mathematical aspects of informatics (M\"agdesprung, 1986)},
   journal =    {J. Inform. Process. Cybernet.},
   fjournal =   {Journal of Information Processing and Cybernetics},
   volume =     23,
   year =       1987,
   number =     {8-9},
   pages =      {415--439},
   issn =       {0863-0593},
   mrclass =    {03D05 (68Q45)},
   mrnumber =   {89b:03063},
   mrreviewer = {Hideki Yamasaki},
}

@inCollection{Staiger98,
   author =    {Staiger, Ludwig},
   title =     {Rich $\omega$-words and monadic second-order arithmetic},
   booktitle = {Computer science logic (Aarhus, 1997)},
   pages =     {478--490},
   publisher = {Springer},
   address =   {Berlin},
   year =      1998,
   mrclass =   {68Q45 (03C85 03D05)},
   mrnumber =  {2000h:68131},
}

@inCollection{Staiger97,
   author =     {Staiger, Ludwig},
   title =      {$\omega$-languages},
   booktitle =  {Handbook of formal languages, Vol.\ 3},
   pages =      {339--387},
   publisher =  {Springer},
   address =    {Berlin},
   year =       1997,
   mrclass =    {68Q45 (03D05 03D15 03D55 68Q68)},
   mrnumber =   {98m:68162},
   mrreviewer = {Do Long Van},
}

@article{StaigerWagner74,
   author =   {Staiger, Ludwig and Wagner, Klaus},
   title =    {Automatentheoretische und automatenfreie {C}harakterisierungen 
               topologischer {K}lassen regul\"arer {F}olgenmengen},
   journal =  {Elektron. Informationsverarbeit. Kybernetik},
   volume =   10,
   year =     1974,
   pages =    {379--392},
   mrclass =  {94A30 (02F10)},
   mrnumber = {57 \#11971},
}

@article{Stern85a,
   author =     {Stern, Jacques},
   title =      {Characterizations of some classes of regular events},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     35,
   year =       1985,
   number =     1,
   pages =      {17--42},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68Q45},
   mrnumber =   {86k:68057},
   mrreviewer = {Jean-Eric Pin},
}

@article{Stern85b,
   author =     {Stern, Jacques},
   title =      {Complexity of some problems from the theory of automata},
   journal =    {Inform. and Control},
   fjournal =   {Information and Control},
   volume =     66,
   year =       1985,
   number =     3,
   pages =      {163--176},
   issn =       {0019-9958},
   coden =      {IFCNA4},
   mrclass =    {68Q05 (03D05 68Q15)},
   mrnumber =   {87k:68038},
   mrreviewer = {E. B. Kinber},
}

@article{Stockmeyer77,
   author =     {Stockmeyer, Larry J.},
   title =      {The polynomial-time hierarchy},
   journal =    {Theoret. Comput. Sci.},
   volume =     3,
   year =       1976,
   number =     1,
   pages =      {1--22 (1977)},
   mrclass =    {68A20},
   mrnumber =   {55 \#11716},
   mrreviewer = {John T. Gill},
}

@article{Stone,
   author =  {Stone, M.},
   title =   {The representation of boolean algebras},
   journal = {Bulletin of the AMS},
   volume =  44,
   pages =   {807--816},
   year =    {19??},
   note =    {reviewed in Zentralblatt f{\"u}r Mathematik {\bf 20}, 342},
}

@article{Straubing79,
   author =     {Straubing, Howard},
   title =      {Families of recognizable sets corresponding to certain varieties 
                 of finite monoids},
   journal =    {J. Pure Appl. Algebra},
   fjournal =   {Journal of Pure and Applied Algebra},
   volume =     15,
   year =       1979,
   number =     3,
   pages =      {305--318},
   issn =       {0022-4049},
   mrclass =    {68D45 (20M35)},
   mrnumber =   {80k:68046},
   mrreviewer = {Hubert Grassmann},
}

@article{Straubing81,
   author =     {Straubing, Howard},
   title =      {A generalization of the {S}ch\"utzenberger product of finite 
                 monoids},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     13,
   year =       1981,
   number =     2,
   pages =      {137--150},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {20M35 (68D30)},
   mrnumber =   {82a:20079},
   mrreviewer = {V{\'a}clav Koubek},
}

@article{Straubing85,
   author =     {Straubing, Howard},
   title =      {Finite semigroup varieties of the form ${V}\ast {D}$},
   journal =    {J. Pure Appl. Algebra},
   fjournal =   {Journal of Pure and Applied Algebra},
   volume =     36,
   year =       1985,
   number =     1,
   pages =      {53--94},
   issn =       {0022-4049},
   coden =      {JPAAA2},
   mrclass =    {20M35 (20M07 20M30)},
   mrnumber =   {86j:20070},
   mrreviewer = {A. A. Iskander},
}

@article{Straubing88,
   author =     {Straubing, Howard},
   title =      {Semigroups and languages of dot-depth two},
   note =       {Thirteenth International Colloquium on Automata, Languages and 
                 Programming (Rennes, 1986)},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     58,
   year =       1988,
   number =     {1-3},
   pages =      {361--378},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {20M35 (03D05 18B40 68Q70)},
   mrnumber =   {90j:20139},
   mrreviewer = {Pascal Weil},
}

@book{Straubing94,
   author =     {Straubing, Howard},
   title =      {Finite automata, formal logic, and circuit complexity},
   publisher =  {Birkh\"auser Boston Inc.},
   address =    {Boston, MA},
   year =       1994,
   pages =      {xii+226},
   isbn =       {0-8176-3719-2},
   mrclass =    {68Q70 (03-02 03B70 03D05 03D15 20M35 68-02 68Q15)},
   mrnumber =   {95f:68173},
   mrreviewer = {Alexey P. Stolboushkin},
}

@article{StraubingTherien88,
   author =     {Straubing, Howard and Th{\'e}rien, Denis},
   title =      {Partially ordered finite monoids and a theorem of {I}.\ {S}imon},
   journal =    {J. Algebra},
   fjournal =   {Journal of Algebra},
   volume =     119,
   year =       1988,
   number =     2,
   pages =      {393--399},
   issn =       {0021-8693},
   coden =      {JALGA4},
   mrclass =    {20M10 (06F05 68Q45)},
   mrnumber =   {89j:20070},
   mrreviewer = {R. B. McFadden},
}

@article{StraubingWeil92,
   author =     {Straubing, Howard and Weil, Pascal},
   title =      {On a conjecture concerning dot-depth two languages},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     104,
   year =       1992,
   number =     2,
   pages =      {161--183},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68Q45},
   mrnumber =   {93j:68105},
   mrreviewer = {Ranjan Chaudhuri},
}

@article{Streett82,
   author =     {Streett, Robert S.},
   title =      {Propositional dynamic logic of looping and converse is 
                 elementarily decidable},
   journal =    {Inform. and Control},
   fjournal =   {Information and Control},
   volume =     54,
   year =       1982,
   number =     {1-2},
   pages =      {121--141},
   issn =       {0019-9958},
   coden =      {IFCNA4},
   mrclass =    {68Q60 (03B25 03B45)},
   mrnumber =   {85d:68051},
   mrreviewer = {Joseph Y. Halpern},
}

@article{Takahashi86,
   author =     {Takahashi, Masako},
   title =      {The greatest fixed-points and rational omega-tree languages},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     44,
   year =       1986,
   number =     3,
   pages =      {259--274},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {03D05 (68Q45)},
   mrnumber =   {88a:03091},
   mrreviewer = {M. Kunze},
}

@article{Takahashi87,
   author =     {Takahashi, Masako},
   title =      {Brzozowski hierarchy of $\omega$-languages},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     49,
   year =       1987,
   number =     1,
   pages =      {1--12},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68Q45 (03D05)},
   mrnumber =   {88j:68094},
   mrreviewer = {Dominique Perrin},
}

@article{TakahashiYamasaki83,
   author =   {Takahashi, Masako and Yamasaki, Hideki},
   title =    {A note on $\omega$-regular languages},
   journal =  {Theoret. Comput. Sci.},
   fjournal = {Theoretical Computer Science},
   volume =   23,
   year =     1983,
   number =   2,
   pages =    {217--225},
   issn =     {0304-3975},
   coden =    {TCSDI},
   mrclass =  {68F10},
   mrnumber = {84g:68068},
}

@article{ThatcherWright68,
   author =     {Thatcher, James W. and Wright, Jesse B.},
   title =      {Generalized finite automata theory with an application to a 
                 decision problem of second-order logic},
   journal =    {Math. Systems Theory},
   volume =     2,
   year =       1968,
   pages =      {57--81},
   mrclass =    {02.88},
   mrnumber =   {37 \#75},
   mrreviewer = {L. H. Landweber},
}

@article{TherienWeiss85,
   author =     {Th{\'e}rien, Denis and Weiss, Alex},
   title =      {Graph congruences and wreath products},
   journal =    {J. Pure Appl. Algebra},
   fjournal =   {Journal of Pure and Applied Algebra},
   volume =     36,
   year =       1985,
   number =     2,
   pages =      {205--215},
   issn =       {0022-4049},
   coden =      {JPAAA2},
   mrclass =    {20M35 (05C25 18B99)},
   mrnumber =   {86i:20093},
   mrreviewer = {Howard Straubing},
}

@inProceedings{TherienWilke96,
   author =    {Th{\'e}rien, Denis and Wilke, Thomas},
   title =     {Temporal logic and semidirect products: an effective 
                characterization of the until hierarchy},
   booktitle = {Proceedings of the 37th Annual Symposium on Foundations of 
                Computer Science},
   publisher = {IEEE Computer Science},
   year =      1996,
   pages =     {256--263},
}

@inProceedings{TherienWilke98,
   author =    {Th{\'e}rien, Denis and Wilke, Thomas},
   title =     {Over words, two variables are as powerful as one quantifier 
                alternation: FO${}^2 = \Sigma^2 \cap \Pi^2$},
   booktitle = {Proceedings of the 30th Annual ACM Symposium on Theory of 
                Computing},
   year =      1998,
   pages =     {41--47},
}

@article{Thomas79,
   author =     {Thomas, Wolfgang},
   title =      {Star-free regular sets of $\omega$-sequences},
   journal =    {Inform. and Control},
   fjournal =   {Information and Control},
   volume =     42,
   year =       1979,
   number =     2,
   pages =      {148--156},
   issn =       {0019-9958},
   coden =      {IFCNA4},
   mrclass =    {68D45},
   mrnumber =   {80h:68052},
   mrreviewer = {R. E. Ladner},
}

@article{Thomas81,
   author =     {Thomas, Wolfgang},
   title =      {A combinatorial approach to the theory of $\omega$-automata},
   journal =    {Inform. and Control},
   fjournal =   {Information and Control},
   volume =     48,
   year =       1981,
   number =     3,
   pages =      {261--283},
   issn =       {0019-9958},
   coden =      {IFCNA4},
   mrclass =    {68D05 (03D05 05A99)},
   mrnumber =   {84d:68054},
   mrreviewer = {Dominique Perrin},
}

@article{Thomas82a,
   author =     {Thomas, Wolfgang},
   title =      {Classifying regular events in symbolic logic},
   journal =    {J. Comput. System Sci.},
   fjournal =   {Journal of Computer and System Sciences},
   volume =     25,
   year =       1982,
   number =     3,
   pages =      {360--376},
   issn =       {0022-0000},
   coden =      {JCSSBM},
   mrclass =    {03D05 (68Q45)},
   mrnumber =   {85a:03053},
   mrreviewer = {Jean-Eric Pin},
}

@inProceedings{Thomas82b,
   author =    {Thomas, Wolfgang},
   title =     {A hierarchy of sets of infinite trees},
   booktitle = {Theoretical Computer Science, Proceedings of the 6th GI 
                Conference},
   series =    {Lecture Notes in Comput. Sci.},
   publisher = {Springer Verlag, Berlin, Heidelberg, New York},
   editor =    {A.B. Cremers and H.P. Kriegel},
   year =      1982,
   volume =    145,
   pages =     {335--342},
}

@article{Thomas86,
   author =     {Thomas, Wolfgang},
   title =      {On frontiers of regular trees},
   journal =    {RAIRO Inform. Th\'eor. Appl.},
   fjournal =   {RAIRO Informatique Th\'eorique et Applications},
   volume =     20,
   year =       1986,
   number =     4,
   pages =      {371--381},
   issn =       {0296-1598},
   mrclass =    {68Q45 (03D05)},
   mrnumber =   {89c:68065},
   mrreviewer = {Stephen L. Bloom},
}

@inProceedings{Thomas87,
   author =    {Thomas, Wolfgang},
   title =     {On chain logic, path logic, and first-order logic over infinite 
                trees},
   booktitle = {Proc. 2nd IEEE Symp. on Logic in Comput. Sci. Ithaca, N.Y.},
   publisher = {IEEE},
   year =      1987,
   pages =     {245--256},
}

@inCollection{Thomas90,
   author =    {Thomas, Wolfgang},
   title =     {Automata on infinite objects},
   booktitle = {Handbook of Theoretical Computer Science},
   volume =    {vol. B, Formal models and semantics},
   editor =    {J. van Leeuwen},
   publisher = {Elsevier},
   year =      1990,
   pages =     {135--191},
}

@inCollection{Thomas95,
   author =     {Thomas, Wolfgang},
   title =      {On the synthesis of strategies in infinite games},
   booktitle =  {STACS 95 (Munich, 1995)},
   pages =      {1--13},
   publisher =  {Springer},
   address =    {Berlin},
   year =       1995,
   mrclass =    {03D05 (03B15 68Q60 68Q68 90D46 94C05)},
   mrnumber =   {98a:03062},
   mrreviewer = {R. Suzanne Zeitman},
}

@inCollection{Thomas97,
   author =     {Thomas, Wolfgang},
   title =      {Languages, automata, and logic},
   booktitle =  {Handbook of formal languages, Vol.\ 3},
   pages =      {389--455},
   publisher =  {Springer},
   address =    {Berlin},
   year =       1997,
   mrclass =    {68Q45 (03B15 03C75 03D05 68Q68)},
   mrnumber =   {99j:68069},
   mrreviewer = {R. Suzanne Zeitman},
}

@article{Thue06,
   author =  {Thue, Axel},
   title =   {{\"U}ber unendliche {Z}eichenreihen},
   journal = {Norske Vid. Selsk. Skr. I Math-Nat. Kl.},
   year =    1906,
   volume =  7,
   pages =   {1--22},
}

@article{Thue12,
   author =  {Thue, Axel},
   title =   {{\"U}ber die gegenseitige {L}oge gleicher {T}eile gewisser 
              {Z}eichenreihen},
   journal = {Norske Vid. Selsk. Skr. I Math-Nat. Kl. Chris.},
   year =    1912,
   pages =   {1--67},
   volume =  1,
}

@article{Timmermann88,
   author =  {Timmermann, Eric},
   title =   {The three subfamilies of rational {$\omega$}-languages closed 
              under {$\omega$}-transduction},
   journal = {Theoret. Comput. Sc.},
   year =    1988,
   volume =  76,
   pages =   {243--250},
}

@article{Trakhtenbrot62,
   author =  {Trakhtenbrot, Boris A.},
   title =   {Finite automata and monadic second order logic (Russian)},
   journal = {Siberian Math. J},
   year =    1962,
   volume =  3,
   pages =   {103--131},
   note =    {( English translation in {\sl Amer. Math. Soc. Transl.} {\bf 59}, 
              1966, 23--55)},
}

@preamble{"\def\cprime{$'$}",}

@book{Trakhtenbrot73,
   author =    {Trakhtenbrot, Boris A. and Barzdin{\cprime}, Ya. M.},
   title =     {Finite automata},
   note =      {Behavior and synthesis, Translated from the Russian by D. 
                Louvish, English translation edited by E. Shamir and L. H. 
                Landweber, Fundamental Studies in Computer Science, Vol. 1},
   publisher = {North-Holland Publishing Co.},
   address =   {Amsterdam},
   year =      1973,
   pages =     {xi+321},
   mrclass =   {94A30},
   mrnumber =  {50 \#4174},
}

@book{VanLeeuwen90b,
   title =     {Handbook of theoretical computer science. {V}ol. {B}},
   editor =    {van Leeuwen, Jan},
   note =      {Formal models and semantics},
   publisher = {Elsevier Science Publishers B.V.},
   address =   {Amsterdam},
   year =      1990,
   pages =     {xiv+1273},
   isbn =      {0-444-88074-7},
   mrclass =   {68-00 (68Qxx)},
   mrnumber =  {92d:68002},
}

@book{VanLeeuwen90a,
   title =     {Handbook of theoretical computer science. {V}ol. {A}},
   editor =    {van Leeuwen, Jan},
   note =      {Algorithms and complexity},
   publisher = {Elsevier Science Publishers B.V.},
   address =   {Amsterdam},
   year =      1990,
   pages =     {x+996},
   isbn =      {0-444-88071-2},
   mrclass =   {68-00 (68Qxx)},
   mrnumber =  {92d:68001},
}

@article{VardiWolper86,
   author =  {Vardi, Moshe Y. and Wolper, Pierre},
   title =   {Automata-theoretic techniques for modal logics of programs},
   journal = {J. Comput. Syst. Sci.},
   year =    1986,
   volume =  32,
   pages =   {183-221},
}

@article{VardiWolper94,
   author =     {Vardi, Moshe Y. and Wolper, Pierre},
   title =      {Reasoning about infinite computations},
   journal =    {Inform. and Comput.},
   fjournal =   {Information and Computation},
   volume =     115,
   year =       1994,
   number =     1,
   pages =      {1--37},
   issn =       {0890-5401},
   mrclass =    {68Q60 (03B45 03D05 03D15)},
   mrnumber =   {96a:68080},
   mrreviewer = {Wolfgang Thomas},
}

@phdThesis{Wadge83,
   author =  {Wadge, W.},
   title =   {Reducibility and determinateness in the Baire space},
   school =  {University of California, Berkeley},
   year =    1983,
}

@article{Wagner75a,
   author =  {Wagner, Klaus},
   title =   {Akzeptierbarkeitsgrade regul{\"a}ren Folgenmengen},
   journal = {Elektron. Informationsverarb. Kybernet.},
   year =    1975,
   volume =  11,
   pages =   {626--630},
}

@inProceedings{Wagner75b,
   author =    {Wagner, Klaus},
   title =     {A hierarchy of regular sequence sets},
   booktitle = {Mathematical Foundations of Computer Science},
   series =    {Lecture Notes in Comput. Sci.},
   publisher = {Springer, Berlin},
   editor =    {J. Be{\v c}v{\'a}{\v r}},
   year =      1975,
   volume =    32,
   pages =     {445--449},
}

@article{Wagner75c,
   author =     {Wagner, Klaus},
   title =      {Eine {A}xiomatisierung der {T}heorie der regul\"aren 
                 {F}olgenmengen},
   journal =    {Elektron. Informationsverarbeit. Kybernetik},
   volume =     12,
   year =       1976,
   number =     7,
   pages =      {337--354},
   mrclass =    {68A25 (02G20)},
   mrnumber =   {54 \#9163},
   mrreviewer = {E. W. Chapin, Jr.},
}

@article{Wagner77,
   author =     {Wagner, Klaus},
   title =      {Eine topologische {C}harakterisierung einiger {K}lassen 
                 regul\"arer {F}olgenmengen},
   journal =    {Elektron. Informationsverarbeit. Kybernetik},
   volume =     13,
   year =       1977,
   number =     9,
   pages =      {473--487},
   mrclass =    {02F10 (68A25)},
   mrnumber =   {58 \#27388},
   mrreviewer = {W. Vollmerhaus},
}

@inProceedings{WagnerStaiger77,
   author =    {Wagner, Klaus and Staiger, Ludwig},
   title =     {Recursive {$\omega$}-languages},
   booktitle = {Fundamentals of Computation Theory},
   series =    {Lecture Notes in Computer Sci.},
   publisher = {Springer Verlag, Berlin, Heidelberg, New York},
   editor =    {M. Karpi\'nski},
   year =      1977,
   volume =    56,
   pages =     {532--537},
}

@article{Wagner79,
   author =     {Wagner, Klaus},
   title =      {On $\omega$-regular sets},
   journal =    {Inform. and Control},
   fjournal =   {Information and Control},
   volume =     43,
   year =       1979,
   number =     2,
   pages =      {123--177},
   issn =       {0019-9958},
   coden =      {IFCNA4},
   mrclass =    {68D45 (03D15)},
   mrnumber =   {81f:68070},
   mrreviewer = {K. L. Yushchenko},
}

@inProceedings{WagnerStaiger79,
   author =    {Wagner, Klaus and Staiger, Ludwig},
   title =     {Finite automata acceptance of infinite sequences},
   booktitle = {Mathematical Foundations of Computer Science},
   series =    {Lecture Notes in Computer Sci.},
   publisher = {Springer Verlag, Berlin, Heidelberg, New York},
   editor =    {A. Blikle},
   year =      1979,
   volume =    28,
   pages =     {69--72},
}

@article{Weil92,
   author =  {Weil, Pascal},
   title =   {Closure of varieties of languages under products with counter},
   journal = {J. Comput. System Sci.},
   year =    1992,
   volume =  45,
   pages =   {316--339},
}

@article{Weiss73,
   author =  {Weiss, Benjamin},
   title =   {Subshifts of finite type and sofic systems},
   journal = {Monats. Math.},
   year =    1973,
   volume =  77,
   pages =   {462--474},
}

@inProceedings{Wilke91,
   author =    {Wilke, Thomas},
   title =     {An Eilenberg theorem for $\infty$-languages},
   booktitle = {Automata, Languages and Programming},
   series =    {Lecture Notes in Computer Sci.},
   publisher = {Springer Verlag, Berlin, Heidelberg, New York},
   year =      1991,
   volume =    510,
   pages =     {588--599},
}

@article{Wilke93a,
   author =  {Wilke, Thomas},
   title =   {An algebraic theory for regular languages of finite and infinite 
              words},
   journal = {Int. J. Alg. Comput.},
   year =    1993,
   volume =  3,
   pages =   {447--489},
}

@inProceedings{Wilke93b,
   author =    {Wilke, Thomas},
   title =     {Locally threshold testable languages of infinite words},
   booktitle = {STACS 93},
   series =    {Lect. Notes in Comp. Sci.},
   publisher = {Springer Verlag, Berlin, Heidelberg, New York},
   editor =    {P. Enjalbert and A. Finkel and K.W. Wagner},
   year =      1993,
   volume =    665,
   pages =     {607--616},
}

@inProceedings{WilkeYoo95,
   author =    {Wilke, Thomas and Yoo, Haiseung},
   title =     {Computing the Wadge degree, the Lifschitz degree, and the Rabin 
                index of a regular language of infinite words in polynomial time},
   booktitle = {TAPSOFT 95},
   series =    {Lect. Notes in Comp. Sci.},
   publisher = {Springer Verlag, Berlin, Heidelberg, New York},
   editor =    {P.D. Mosses and M. Nielsen and M.I Schwartzbach},
   year =      1995,
   volume =    915,
   pages =     {288--302},
}

@article{WilkeYoo96,
   author =  {Wilke, Thomas and Yoo, Haiseung},
   title =   {Computing the Rabin index of a regular language of infinite words},
   journal = {Information and Computation},
   year =    1996,
   volume =  130,
   pages =   {61-70},
}

@article{Wojciechowski84,
   author =  {Wojciechowski, J.},
   title =   {Classes of transfinite sequences accepted by finite automata},
   journal = {Fundamenta Informaticae},
   year =    1984,
   volume =  7,
   pages =   {191--223},
}

@article{Wojciechowski85,
   author =  {Wojciechowski, J.},
   title =   {Finite automata on transfinite sequences and regular expressions},
   journal = {Fundamenta Informaticae},
   year =    1985,
   volume =  8,
   pages =   {379--396},
}

@inCollection{Wojciechowski86,
   author =     {Wojciechowski, J.},
   title =      {The ordinals less than $\omega\sp \omega$ are definable by finite 
                 automata},
   booktitle =  {Algebra, combinatorics and logic in computer science, Vol.\ I, II 
                 (Gy\H or, 1983)},
   pages =      {871--887},
   publisher =  {North-Holland},
   address =    {Amsterdam},
   year =       1986,
   mrclass =    {68Q70},
   mrnumber =   {88f:68112},
   mrreviewer = {Matti Linna},
}
#ancien Wojciechowski83

@article{Wolfe55,
   author =  {Wolfe, Philip},
   title =   {The strict determinacy of certain infinite games},
   journal = {Pacific J. Math.},
   volume =  5,
   pages =   {841-847},
   year =    1955,
}

@article{Yakhnis90,
   author =  {Yakhnis, A. and Yakhnis, V.},
   title =   {Extension of {G}urevitch-{H}arrington's restricted determinacy 
              theorem: a criterion for the winning player and an explicit class 
              of winning strategies},
   journal = {Ann. Pure Appl. Logic},
   volume =  48,
   pages =   {277-279},
   year =    1990,
}


@article{YamasakiTakahashiKobayashi86,
   author =     {Yamasaki, Hideki and Takahashi, Masako and Kobayashi, Kojiro},
   title =      {Characterization of $\omega$-regular languages by monadic 
                 second-order formulas},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     46,
   year =       1986,
   number =     1,
   pages =      {91--99},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {03D05 (03B15 68Q99)},
   mrnumber =   {88a:03092},
   mrreviewer = {Klaus W. Wagner},
}

@article{Yamasaki89,
   author =     {Yamasaki, Hideki},
   title =      {Language-theoretical representations of $\omega$-languages},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     66,
   year =       1989,
   number =     3,
   pages =      {247--254},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68Q70 (68Q45)},
   mrnumber =   {91a:68204},
   mrreviewer = {Klaus W. Wagner},
}

@article{Zeitman94,
   author =     {Zeitman, Suzanne},
   title =      {Unforgettable forgetful determinacy},
   journal =    {J. Logic Comput.},
   fjournal =   {Journal of Logic and Computation},
   volume =     4,
   year =       1994,
   number =     3,
   pages =      {273--283},
   issn =       {0955-792X},
   mrclass =    {03B15 (03B25 68Q10 90D35)},
   mrnumber =   {96g:03012},
   mrreviewer = {Alexey P. Stolboushkin},
}

@article{Zielonka98,
   author =     {Zielonka, Wies{\l}aw},
   title =      {Infinite games on finitely coloured graphs with applications to 
                 automata on infinite trees},
   journal =    {Theoret. Comput. Sci.},
   fjournal =   {Theoretical Computer Science},
   volume =     200,
   year =       1998,
   number =     {1-2},
   pages =      {135--183},
   issn =       {0304-3975},
   coden =      {TCSDI},
   mrclass =    {68Q45 (03B15 03B25 68Q60 91A43)},
   mrnumber =   {2000b:68139},
   mrreviewer = {P. A. Biryukov},
}