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)