Leaf languages are a beautiful way to uniformly define many complexity classes. Most complexity classes are usually specified by a model of computation (e.g., deterministic/randomized TM), and a resource bound (log time, poly space, etc.). However in the leaf language formulation, there is only one model of computation, and the class is specified by giving its leaf language.
The details are too long to explain, so I'll direct interested readers to either of these two surveys:
- Uniform characterizations of complexity classes by H Vollmer
- Leaf Language Classes by KW Wagner
Both surveys do a great job of explaining the formulation within the first few pages.
In Wagner's survey, he says "it turns out that practically every complexity class considered so far can be described by leaf languages."
My question relates to this statement. I know there are some classes for which we do not know a leaf language characterization, so this means either the classes don't necessarily have such a characterization, or we haven't found it.
Do we expect every complexity class (say between P and PSPACE) to have a leaf language characterization? (Let's restrict ourselves to "natural" complexity classes.) Is there any result of this sort in the literature?
(A related question that I'd be happy to know the answer to: Is there a (heuristic) method to come up with a leaf language for a given class?)
EDIT: Suresh points out that there is a short definition of leaf languages in the Wikipedia article. I'm copying it below.
Several complexity classes are typically defined in terms of a polynomial-time nondeterministic Turing machine, where each branch can either accept or reject, and the entire machine accepts or rejects as some function of the branches' conditions. For example, a non-deterministic Turing machine accepts if at least one branch accepts, and rejects only if all branches reject. A co-non-deterministic Turing machine, on the other hand, accepts only if all branches accept, and rejects if any branch rejects. Many classes can be defined in this fashion.