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. [1]

Several complexity classes are typically defined in terms of a polynomial-time nondeterministic Turing machine. In this machine, each branch can either accept or reject an input, and the entire machine accepts or rejects as some function of the conditions of its branches. For example, a non-deterministic Turing machine accepts if at least one branch accepts, and rejects only if all branches reject. On the other hand, a co-non-deterministic Turing machine accepts only if all branches accept, and rejects if any branch rejects. Many classes can be defined in this fashion.

This characterization 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. ↑ Wagner, Klaus W. (2005). Margenstern, Maurice (ed.). "Leaf Language Classes". 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.
  2. ↑ Papadimitriou, Christos H. (1994). Computational complexity. Reading (Mass): Addison-Wesley. ISBN 978-0-201-53082-7.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.