zbMATH — the first resource for mathematics

Projection lemmas for \(\omega\)-languages. (English) Zbl 0545.68074
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).\)

68Q45 Formal languages and automata
Full Text: DOI
[1] Arnold, A., Topological characterizations of infinite behaviours of transition systems, () · Zbl 0515.68063
[2] Davis, M., Infinitary games of perfect information, (), 89-101 · Zbl 0133.13104
[3] Eilenberg, S., Automata, languages and machines, Vol. A, (1974), Academic Press New York · Zbl 0317.94045
[4] Elgot, C.C., Decision problems of finite automata design and related arithmetics, Trans. amer. math. soc., 98, 21-51, (1961) · Zbl 0111.01102
[5] Kuratowski, K., Topology I, (1966), Academic Press New York
[6] Landweber, L.H., Decision problems for ω-automata, Math. systems theory, 3, 376-384, (1969) · Zbl 0182.02402
[7] Staiger, L., Zur topologie der regulären mengen, ()
[8] Staiger, L.; Wagner, K., Rekursive folgenmengen I, Zeitschr. math. logik grundl. math., 24, 523-538, (1978) · Zbl 0421.03035
[9] Trachtenbrot, B.A.; Barzdin, J.M., Finite automata, behaviour and synthesis, (1973), North-Holland Amsterdam
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.