7
$\begingroup$

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.

$\endgroup$
14
$\begingroup$

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.

$\endgroup$
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$ – Ilya Aug 7 '13 at 6:38
  • 3
    $\begingroup$ McNaughton's paper can be found here [sciencedirect.com/science/journal/00199958/9/5] $\endgroup$ – J.-E. Pin Aug 7 '13 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.