It the previous question of mine I put a reference which shows that any $\omega$-regular language over the alphabet $\Sigma$ is a Borel subset of $\Sigma^\omega$. I am not sure whether the reference I am aware of is the first the showed this result, so I wonder whether there are other papers the contain it. Alternatively, I am also interested in textbooks that contain the proof of this fact.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
An $\omega$-regular language is actually quite low in the Borel hierarchy (inside $\Delta_3$), a result due to
R. McNaughton, Testing and generating infinite sequences by a finite automaton, Information and Control 9 (1966), 521-530.
For a proof and more details, you can look at Chapter 3 of the following book
D. Perrin et J.-É. Pin, Infinite words, Pure and Applied Mathematics Vol 141, Elsevier, 2004, ISBN 0-12-532111-2.
-
$\begingroup$ Thank you for the answer. Unfortunately, the paper by McNaughton does not seem to be accessible, and my library does not have the book you've mentioned. Perhaps, I can try convincing them to buy it. $\endgroup$– SBFCommented Aug 7, 2013 at 6:38
-
3$\begingroup$ McNaughton's paper can be found here [sciencedirect.com/science/journal/00199958/9/5] $\endgroup$ Commented Aug 7, 2013 at 10:00