Abschlußeigenschaften

Die Sprachfamilie $\mathscr{L}_{rt}(\operatorname{NIA})$ kann als Abschluß von $\mathscr{L}_{rt}(IA)$ unter $\varepsilon$-freien Homomorphismen charakterisiert werden (Satz 4.2). Dieses Resultat übernimmt bei der Untersuchung der nichtdeterministischen iterativen Arrays ohne Beschränkung des Nichtdeterminismus eine ähnlich zentrale Rolle wie der Satz von Kleene und Myhill für die Untersuchung endlicher Automaten. Insbesondere können fast alle Abschlußeigenschaften von $\mathscr{L}_{rt}(\operatorname{NIA})$ aus diesem Satz gefolgert werden (Korollar 4.10 und 4.12).

Die Untersuchung der Abschlußeigenschaften von $\mathscr{L}_{rt}(f(n)-\operatorname{NIA})$ gestaltet sich schwieriger. Die positiv beantworteten Abschlußeigenschaften wurden durch relativ einfache Konstruktionen gezeigt (Insbesondere die zwei Register-Technik aus Satz 4.22 ist ein von anderen Automatenmodellen bekanntes Prinzip). Die negativ beantworteten Abschlußeigenschaften haben deutlich schwierigere Beweise. Besonders erwähnenswert sind:

• Der Abschluß bezüglich Konkatenation hängt entscheidend von dem Wachstumsverhalten der Funktion f ab (Korollar 4.16 und Satz 4.17).
• Im Gegensatz zu den beiden Grenzfällen $\mathscr{L}_{rt}(\operatorname{IA})$ und $\mathscr{L}_{rt}(\operatorname{NIA})$ ist
  $\mathscr{L}_{rt}(f(n)-\operatorname{NIA})$ nicht abgeschlossen bezüglich markierter Iteration (Satz 4.18). Der Beweis ist technisch sehr aufwendig und besteht im wesentlichen aus einer noch weitergehenden Verallgemeinerung des Äquivalenzklassenkonzepts aus Abschnitt 3.4.
• $\mathscr{L}_{rt}(f(n)-\operatorname{NIA})$ ist nicht abgeschlossen bezüglich Komplementbildung (Satz 4.22). Im allgemeinen ist der Komplementabschluß für nicht deterministische Geräte ein ungelöstes Problem (z.B. NTime(t(n)) bei Turing-Maschinen).