Projection lemmas for \(\omega\)-languages (Q797297)

The paper shows that projection lemmas in an elegant way relate the behaviours of deterministic and nondeterministic (possibly infinite- state) devices, which accept \(\omega\)-languages, even in the case when the branching of the nondeterministic devices is unbounded (though finite) or countably infinite. Moreover, topological characterizations and results are obtained. To this end we regard the product topology in \(X^{\omega}\) where X is a finite alphabet provided with the discrete topology. Let \(E\subseteq(X\times \{0,1\})^{\omega}\) be the set of \(\omega\)-words on \(X\times \{0,1\}\) having infinitely often a one in the second component. In the paper three different notions of acceptance (e- everywhere, ae-almost everywhere, and io - infinitely often) for \(\omega\)-languages are considered. Let T (\({\mathfrak A})\) denote the \(\omega\)-language (\(\alpha\)-accepted by the (possibly infinite) automaton \((\alpha \in \{e,ae,io\}).\) Projection lemmas. Let \({\mathfrak A}\) be a finitely (countably) branching nondeterministic automaton over X. Then there is a deterministic automaton \({\mathfrak A}\) over \(X\times \{0,1\}\) such that \(T_{\alpha}({\mathfrak A})=\Pr T_{\alpha}({\mathfrak A}') (T_{\alpha}({\mathfrak A})=\Pr(T_{\alpha}({\mathfrak A}')\cap E)).\) As a corollary we obtain: For every Souslin set \(F\subseteq X^{\omega}\) there is a closed set \(F'\subseteq(X\times \{0,1\})^{\omega}\) such that \(F=\Pr(F'\cap E).\)