Leaf language

Leaf language is a method in computational complexity theory of characterizing a complexity class by formalizing what it means for a machine to "accept" an input.^[1]

Complexity classes are typically defined in terms of a polynomial-time nondeterministic Turing machine (NTM). Machines possess many computational paths whose outcomes are used to determine whether an input is accepted or rejected by the machine.^[1] Traditional NTMs will accept the input if at least one path accepts it, and rejects only if all paths reject it. However, a co-NTM accepts the input only if all paths accept it, and rejects it if any path rejects it. Different and more sophisticated notions of acceptance can be defined similarly.

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. NTMs 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[edit]

^ ^a ^b Wagner, Klaus W. (2005). "Leaf Language Classes". In Margenstern, Maurice (ed.). Lecture Notes in Computer Science. Vol. 3354. Berlin, Heidelberg: Springer. pp. 60–81. doi:10.1007/978-3-540-31834-7_5. ISBN 978-3-540-31834-7. {{cite book}}: |journal= ignored (help); Missing or empty |title= (help)
^ Papadimitriou, Christos H. (1994). Computational complexity. Reading (Mass): Addison-Wesley. ISBN 978-0-201-53082-7.

[:0-1] Wagner, Klaus W. (2005). "Leaf Language Classes". In Margenstern, Maurice (ed.). Lecture Notes in Computer Science. Vol. 3354. Berlin, Heidelberg: Springer. pp. 60–81. doi:10.1007/978-3-540-31834-7_5. ISBN 978-3-540-31834-7. {{cite book}}: |journal= ignored (help); Missing or empty |title= (help)

[2] Papadimitriou, Christos H. (1994). Computational complexity. Reading (Mass): Addison-Wesley. ISBN 978-0-201-53082-7.

[1]

[2]