In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
, a leaf language is a method of characterizing a
complexity class
In computational complexity theory, a complexity class is a set (mathematics), set of computational problems of related resource-based computational complexity, complexity. The two most commonly analyzed resources are time complexity, time and spa ...
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
In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is ''not'' comp ...
, 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
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of sy ...
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
if the leaf string is in the language
*1
*, and will reject if the leaf string is in the language 0
*.
References
*
*
{{Computing-stub
Computational complexity theory