We investigate the power of regular leaf languages with respect to three different tree shapes: the first one is the case of arbitrary (and thus potentially non-regular) computation trees; the second one is the case of balanced computation trees (these trees are initial segments of full binary trees); and the third one is the case of full binary computation trees. It is known that the class characterizable by regular leaf languages is PSPACE in all cases; but, contrary to our intuition, the description power does not decrease, but may increase with the regularity of the trees. We also investigate three subclasses of the class of regular languages and their description power with respect to the three different models. We exhibit the somehow strange fact that for each of the three models there is one subclass, which makes this model in question strictly more powerful than the other ones (under some reasonable complexity theoretic assumption). We conclude that the crucial property behind the characterization power is not a property of the model, but a matter of the extent, to which the models and the respective leaf language classes are suitable for each other.
['Ulrich Hertrampf']
The Shapes of Trees