Leaf language

In computational complexity theory, a "leaf language" is a method of characterizing a complexity class by formalizing what it means for a machine to "accept" an input.

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.

We can then formalize this by examining the formal language associated with each acceptance condition. We assume that the tree is ordered, and read the accept/reject strings off the leaves of the computation tree. For example, the nondeterministic machine will accept iff the leaf string is in the language $\{0,1\}^*1\{0,1\}^*$, and will reject iff the leaf string is in the language $0^*$.

References

cite book
last = Papadimitriou
first = Christos H.
authorlink = Christos Papadimitriou
year = 1994
title = Computational Complexity
publisher = Addison-Wesley
location = Reading, Massachusetts
id = ISBN 0-201-53082-1
pages = 504-505

cite journal
last = Bovet
first = Daniel P.
coauthors = Pierluigi Crescenzi; Riccardo Silvestri
year = 1992
title = A uniform approach to define complexity classes
journal = Theoretical Computer Science
volume = 104
pages = 263–283
doi = 10.1016/0304-3975(92)90125-Y