Вычислительная мощность детерминированных и недетерминированных автоматов с минимальной кучей

15

Это дополнительный вопрос этого .

В предыдущем вопросе об экзотических конечных автоматах Алекс тен Бринк и Рафаэль обратились к вычислительным возможностям особого вида конечного автомата: автоматов с минимальной кучей. Они смогли показать, что множество языков, принятых на таких машинах ( ), не является ни подмножеством, ни надмножеством набора языков без контекста. Учитывая успешное разрешение и очевидный интерес к этому вопросу, я перехожу к нескольким последующим вопросам.ЧАСAL

Известно, что детерминированные и недетерминированные конечные автоматы имеют эквивалентные вычислительные возможности, как и детерминированные и недетерминированные машины Тьюринга. Однако вычислительные возможности детерминированных автоматов с нажатием меньше, чем у недетерминированных автоматов с нажатием.

Являются ли вычислительные возможности детерминированных автоматов с минимальной кучей меньшими или равны таковым у недетерминированных автоматов с минимальной кучей?

Patrick87
источник

Ответы:

3

Кажется, что для этой модели недетерминированные машины не эквивалентны детерминированным, в основном по той же причине, по которой детерминированные КПК не эквивалентны недетерминированным.

Рассмотрим язык

Lзнак равноИкс$Y||Икс|знак равно|Y|ИксY
(где - специальный знак, не содержащийся в x и y ).$ИксY

Я утверждаю , что недетерминированная машина - Н L может решить этот язык: Он выполняет такой же , как для КПК L . Стандартное решение PDA использует стек только для подсчета смещений: он недетерминированно угадывает смещение i , запоминает значение x i (добавляя символ в стек на каждом шаге), затем PDA игнорирует ввод, пока не найдет $ , и затем он выталкивает символы из стека, пока не станет пустым. На этом этапе мы находимся именно на y i, и он может проверить, если x iy iNЧАСALLяИкся$YяИксяYя, (если что-то пойдет не так в середине, КПК «умирает»). Поскольку алфавит стека одинарный, его можно смоделировать на машине с минимальной кучей. На самом деле: любой который принимается КПК с унарным алфавитом, может быть принят машиной с минимальной кучей. (Я игнорирую, может быть, еще один специальный знак, добавленный для идентификации пустого стека, но эквивалентный знак может быть добавлен в кучу)L

Что касается другого направления, у меня нет формального доказательства, но вот мои мысли:

Я утверждаю, что детерминированная машина - H A L не способна решить этот язык. Интуитивно понятно, что содержимое кучи не может быть соотнесено с x (в противном случае перестановка x . Содержимое кучи остается неизменной ..). Это говорит о том, что единственное, что имеет значение, это количество элементов в куче, но тогда, если D - H A L может решить L , то может быть и детерминистический - P D ADЧАСALИксИксDЧАСALLпDA .

Изменить: более подробную информацию о претензии "permute ". Предполагая гипотезу Рафаэля, существуют x 1 и x 2, что после прочтения их содержимое кучи одинаково. Затем рассмотрим слова x 1 $ x 1 и x 2 $ x 1 . Содержимое кучи одинаково, когда HAL достигает знака доллара, поэтому он должен либо принять оба, либо отклонить оба. противоречие .ИксИкс1Икс2Икс1$Икс1Икс2$Икс1

Кто-нибудь видит непосредственное доказательство этой гипотезы?

Ран Г.
источник
Икс
Какое определение мин-куч вы используете: мое оригинальное или более естественное, предложенное Рафаэлем? В любом случае, можете ли вы быть более ясными о том, как недетерминированный компьютер будет воспринимать язык, который вы даете ... что он помещает и удаляет из кучи и когда?
Patrick87
NN