Сборники трудов ИСП РАН


О синтаксическом определении класса языков, распознаваемых недетерминированными машинами Тьюринга на логарифмической памяти.

Д.А. Носов.

Аннотация

В работе М. А. Тайцлина и А. П. Столбоушкина было введено понятие недетерминированной программы, и определен класс языков, распознаваемых недетерминированными программами. Доказана теорема, свидетельствующая о близости этого класса, и NL. Мы исследуем класс языков, определяемый в некоторой модификации указанной вычислительной модели, и доказываем, что рассматриваемый класс языков равен NL.

Ключевые слова

машина Тьюринга; недетерминированные программы; класс сложностей; логарифмическая память; сложность вычислений; универсальная алгебра

Издание

Труды Института системного программирования РАН, том 26, вып. 2, 2014, стр. 275-296.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2014-26(2)-13

Полный текст статьи в формате pdf Вернуться к содержанию тома