Q (complexity class)

The class Q , also known under the name of quasi-real-time languages , is a term used in theoretical computer science , especially complexity theory . Q is a complexity class that is defined on nondeterministic Turing machines , which only require linear time. Ron Book has shown that such machines can always be accelerated so that they read a character at every step and only work until the input is read. Therefore, he gave them the name Quasi-Realzeit-Sprachen (quasi realtime languages).

With the machine characterization of context-sensitive languages (CSL) it can be shown that Q is a subclass of CSL. Conversely, the class of increasingly context-sensitive languages (GCSL) is a real subclass of Q.

Properties of Q

Q is completed under

• average
• inverse homomorphisms
• Kleene star
• Concatenation
• ε-free homomorphisms
• Union

It is also known:

• GCSL ⊂ Q ⊂ CSL
• Q ⊂ NP

Web links

• Q . In: Complexity Zoo. (English)