WikiDer > Язык листа

Эта статья тон или стиль могут не отражать энциклопедический тон используется в Википедии. См. Википедию руководство по написанию лучших статей для предложений. (Июль 2019) (Узнайте, как и когда удалить этот шаблон сообщения)

В теория сложности вычислений, а листовой язык это метод характеристики класс сложности путем формализации того, что значит для машины «принять» ввод.

Несколько классов сложности обычно определяются в терминах полиномиальное время недетерминированная машина Тьюринга, где каждая ветвь может либо принять, либо отклонить, а вся машина принимает или отклоняет в зависимости от условий ветвей. Например, недетерминированная машина Тьюринга принимает, если хотя бы одна ветвь принимает, и отклоняет, только если все ветки отклоняют. А недетерминированная машина Тьюринга, с другой стороны, принимает, только если все ветви принимают, и отклоняет, если какая-либо ветвь отклоняет. Таким образом можно определить многие классы.

Затем мы можем формализовать это, исследуя формальный язык связанные с каждым условием приемки. Мы предполагаем, что дерево упорядочено, и считываем строки принятия / отклонения с листьев дерева вычислений. Например, недетерминированная машина примет если только конечная строка на языке {0, 1}^*1{0, 1}^*, и отклонит, если конечная строка находится на языке 0^*.

Рекомендации

• Пападимитриу, Христос Х. (1994). Вычислительная сложность. Ридинг, Массачусетс: Эддисон-Уэсли. стр.504–505. ISBN 0-201-53082-1.

• Bovet, Daniel P .; Пьерлуиджи Крещенци; Риккардо Сильвестри (1992). «Единый подход к определению классов сложности». Теоретическая информатика. 104 (2): 263–283. Дои:10.1016 / 0304-3975 (92) 90125-У.