Alternation and \(\omega\)-type Turing acceptors (Q1088417)

Das Hinzutreten des Prädikats ''alternierend'' zu der klassischen Menge: \(E=\{\det er\min istisch\), nondeterministisch\(\}\) ist schon rein kombinatorisch für die Erzeugung von neuen Fragestellungen recht nützlich. Für Akzeptoren unendlich langer Eingabestrings, kurz \(\omega\)-Akzeptoren, tritt als weitere kombinatorische Dimension die Menge \(C=\{Ci|\) \(1<i<6\}\) der in der Literatur hauptsächlich behandelten Bedingungen für das Akzeptieren der Eingabe hinzu. Für \(\omega\)-Turing-Akzeptoren gaben \textit{K. Wagner} und \textit{L. Staiger} [Lect. Notes Comput. Sci. 56, 532-537 (1977; Zbl 0367.02017)] ein \(E\times C\)-Tableau T der akzeptierten Sprachklassen an, dem die vorliegende Arbeit eine Zeile für das Element ''alternierend'' anfügt, deren letzte zwei Einträge besonders gegen den sonstigen Inhalt von T abstechen (B(\(\cdot)\) bezeichne den Booleschen Abschluss): \(T[alt.,C6]=\Delta^ 1_ 0\), \(B(\Sigma^ 1_ 1)\subset T[alt.,C5]\subset \Delta^ 1_ 2\) mit echter Inklusion (!).