Leaf language
In computational complexity theory, a leaf language is a method of characterizing a complexity class by formalizing the notion of acceptance by nondeterministic machines.[1]
Complexity classes are typically defined in terms of a polynomial-time nondeterministic Turing machine. This machine posses many computation paths which can either accept or reject an input, and the outcomes of these computation paths determine whether the input is accepted or not by the entire machine.[1] For example, a non-deterministic Turing machine accepts the input if at least one path accepts it, and rejects only if all paths reject it. On the other hand, a co-nondeterministic Turing machine accepts the input only if all paths accept it, and rejects it if any path rejects it. Different and sophisticated notions of acceptance can be defined in a similar way.
The characterization of a complexity class can be formalized by examining the formal language associated with each acceptance condition. It involves assuming an ordered tree, and reading the accept/reject strings from the leaves of the computation tree. For example, the nondeterministic machine will accept if the leaf string is in the language 0*1{0, 1}*, and will reject if the leaf string is in the language 0*. [2]
References
- ↑ 1.0 1.1 Wagner, Klaus W. (2005). Margenstern, Maurice. ed. "Leaf Language Classes" (in en). Machines, Computations, and Universality. Lecture Notes in Computer Science (Berlin, Heidelberg: Springer): 60–81. doi:10.1007/978-3-540-31834-7_5. ISBN 978-3-540-31834-7. https://link.springer.com/chapter/10.1007/978-3-540-31834-7_5.
- ↑ Papadimitriou, Christos H. (1994). Computational complexity. Reading (Mass): Addison-Wesley. ISBN 978-0-201-53082-7.
 |  |
