LOGSPACE AND LOGTIME LEAF LANGUAGES

The computation tree of a nondeterministic machine M with input x give s rise to a leaf string formed by concatenating the outcomes of all th e computations in the tree in lexicographical order. We may characteri ze problems by considering, for a particular ''leaf language'' Y, the set of all x for which the leaf string of M is contained in Y. In this way, in the context of polynomial time computation, leaf languages we re shown to capture many complexity classes. In this paper, we study t he expressibility of the leaf language mechanism in the contexts of lo garithmic space and of logarithmic time computation. We show that logs pace leaf languages yield a much finer classification scheme for compl exity classes than polynomial time leaf languages, capturing also many classes within P. In contrast, logtime leaf languages basically behav e like logtime reducibilities. Both cases are more subtle to handle th an the polynomial time case. We also raise the issue of balanced versu s nonbalanced computation trees underlying the leaf language. We indic ate that it is a nontrivial problem to obtain information about the le af string of a nonbalanced computation tree and present conditions und er which it does not matter whether the computation tree is balanced o r not. (C) 1996 Academic Press, Inc.