Q (Komplexitätsklasse)

Die Klasse Q, auch bekannt unter dem Namen Quasi-Realzeit-Sprachen, ist ein Begriff der Theoretischen Informatik, speziell der Komplexitätstheorie. Q ist eine Komplexitätsklasse, die auf nichtdeterministischen Turingmaschinen definiert ist, welche nur linearen Zeitbedarf haben. Ron Book hat gezeigt, dass solche Maschinen stets beschleunigt werden können, so dass sie in jedem Schritt ein Zeichen lesen und nur so lange arbeiten, bis die Eingabe gelesen ist. Daher hat er ihnen den Namen Quasi-Realzeit-Sprachen (engl.: quasi realtime languages) gegeben.

Mit der Maschinencharakterisierung der kontextsensitiven Sprachen (CSL) lässt sich nachweisen, dass Q eine Teilklasse von CSL ist. Umgekehrt ist die Klasse wachsend kontextsensitiver Sprachen (GCSL) eine echte Teilklasse von Q.

Eigenschaften von Q

Q ist abgeschlossen unter

• Durchschnitt
• inversen Homomorphismen
• Kleene-Stern
• Konkatenation
• ε-freien Homomorphismen
• Vereinigung

Weiterhin ist bekannt:

• GCSL ⊂ Q ⊂ CSL
• Q ⊂ NP

Weblinks

• Q. In: Complexity Zoo. (englisch)