Talk:Leaf language

This article is rated Stub-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Science This article is within the scope of WikiProject Science, a collaborative effort to improve the coverage of Science on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ScienceWikipedia:WikiProject ScienceTemplate:WikiProject Sciencescience ??? This article has not yet received a rating on the project's importance scale.

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)Reply

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)Reply