most recent 30 from http://mathoverflow.net 2013-05-19T10:25:50Z http://mathoverflow.net/feeds/question/57832 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/57832/complementation-of-omega-regular-languages-in-reverse-mathematics Alex Simpson 2011-03-08T14:18:38Z 2012-01-19T07:22:12Z

<p>Does anyone know where B&uuml;chi's theorem that $\omega$-regular languages are closed under complementation fits into the reverse-mathematics classification scheme? That is, is it equivalent over $\mathrm{RCA}_0$ to one of the usual subsystems of second-order arithmetic? Or, if not known to be equivalent, what is known about where it fits in?</p> <p>The formulation I have in mind is, for a fixed finite signature $\Sigma$, the statement: for every finite automaton $M$ (over $\Sigma$), there exists a finite automaton $M^c$, such that, for every $\omega$-word $\alpha$ over $\Sigma$, it holds that $\alpha$ is (B&uuml;chi-)accepted by $M$ if and only if $\alpha$ is not accepted by $M^c$.</p>

http://mathoverflow.net/questions/57832/complementation-of-omega-regular-languages-in-reverse-mathematics/81777#81777 Benjamin Steinberg 2011-11-24T04:43:18Z 2011-11-24T04:43:18Z

<p>I am not familiar with all proofs of McNaughton's theorem, but the ones I have seen use the weak form of Konig's Lemma that a finitely branching infinite tree contains an infinite path.</p>