Logspace and Logtime Leaf Languages

• Published in: Information and computation 1996-08, Vol.129 (1), p.21-33
• Main Authors: Jenner, Birgit, McKenzie, Pierre, Thérien, Denis
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Applied sciences; Automata. Abstract machines. Turing machines; Computer science; control theory; systems; Exact sciences and technology; Language theory and syntactical analysis; Theoretical computing
• ISSN: 0890-5401; 1090-2651
• DOI: 10.1006/inco.1996.0071

The computation tree of a nondeterministic machineMwith inputxgives rise to aleaf stringformed by concatenating the outcomes of all the computations in the tree in lexicographical order. We may characterize problems by considering, for a particular “leaf language”Y, the set of allxfor which the leaf string ofMis contained inY. In this way, in the context of polynomial time computation, leaf languages were shown to capture many complexity classes. In this paper, we study the expressibility of the leaf language mechanism in the contexts of logarithmic space and of logarithmic time computation. We show that logspace leaf languages yield a much finer classification scheme for complexity classes than polynomial time leaf languages, capturing also many classes withinP. In contrast, logtime leaf languages basically behave like logtime reducibilities. Both cases are more subtle to handle than the polynomial time case. We also raise the issue of balanced versus nonbalanced computation trees underlying the leaf language. We indicate that it is a nontrivial problem to obtain information about the leaf string of a nonbalanced computation tree and present conditions under which it does not matter whether the computation tree is balanced or not.