Do all complexity classes have a leaf language characterization?

Question

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:

1. Uniform characterizations of complexity classes by H Vollmer
2. 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.

Answer 1

Have a look at

Bernd Borchert, Riccardo Silvestri: A Characterization of the Leaf Language Classes. Inf. Process. Lett. 63(3): 153-158 (1997) (doi link here)

The authors characterize the leaf language classes as those which are (a) "countable", (b) are "downward" closed wrt polytime many-one reducibility, and (c) "join-closed" (i.e., disjoint union) wrt polytime many-one reducibility.

More formally, all the languages $L$ in a leaf language class have a bijection with the natural numbers, and the property that for every $C,D \in L$, if $E \leq^P_m C \sqcup D$ then $E \in L$ as well (the $\sqcup$ denotes disjoint union). Also, every "non-leaf language class" contains a language which fails to have one of these properties.

From these three conditions we can get many examples of classes which aren't leaf language classes. For example, the "countable" condition rules out advice classes like $P/poly$, and the "downward closed wrt polytime many-one reducibility" rules out fixed resource-bound classes like $SPACE[n]$. (Recall that the usual proof that $SPACE[n] \neq P$ uses the fact that $SPACE[n]$ is not closed under such reductions.)