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 of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms ...
by formalizing what it means for a machine to "accept" an input.
Several complexity classes are typically defined in terms of a
polynomial-time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
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
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 s ...
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