Name
Abstract | ||
|---|---|---|
The computation tree of a nondeterministic machine M with input x gives rise to a leaf string formed 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 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 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 within P . 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. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1006/inco.1996.0071 | Information and Computation/information and Control |
Keywords | DocType | Volume |
logtime leaf language,turing machines,theorem proving,polynomial time,complexity class,computational complexity,formal languages | Conference | 129 |
Issue | ISSN | ISBN |
1 | Information and Computation | 0-8186-5670-0 |
Citations | PageRank | References |
32 | 1.17 | 20 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Birgit Jenner | 1 | 247 | 14.47 |
| P. McKenzie | 2 | 152 | 8.23 |
| Denis Thérien | 3 | 671 | 55.71 |