Talk:Leaf language

Clarifying nondeterministic Turing machine definition

Several complexity classes are typically defined in terms of a polynomial-time 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.

This paragraph needs clarifying. Specifically, the phrase "nondeterministic Turing machine" is used to define a general nondeterministic machine that can accept or reject as a function of results of many computation paths and as a specific category of nondeterministic machines that accept if at least one branch accepts. I suggest that alternative terminology is used to replace the first usage, and the

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.

text remains as is. Bigsnoopyguyhuh (talk) 20:34, 5 December 2023 (UTC)

Include definition

The concept of a leaf language is not precisely defined in the article. A definition should be included, such as in section one of Leaf Language Classes by Wagner (2003).

Also, the definition presented in the article assumes that all computation paths output yes/no answers, but there are computation classes that are not binary decision problems, so their leaf languages using alphabets other than {0, 1} (see Theorem 1 in Wagner) Bigsnoopyguyhuh (talk) 22:51, 5 December 2023 (UTC)