Определение возможностей конечного автомата с минимальной кучей (или других экзотических)

44

Смотрите в конце этого поста некоторые пояснения к определению (ям) автоматов с минимальной кучей.

Можно представить себе использование различных структур данных для хранения информации для использования конечными автоматами. Например, автоматы с отложенным запуском хранят информацию в стеке, а машины Тьюринга используют ленту. Было показано, что конечные автоматы, использующие очереди, и те, которые используют два нескольких стека или ленты, по мощности эквивалентны машинам Тьюринга.

Представьте себе машину с минимальной кучей. Он работает точно так же, как автомат с понижением частоты, со следующими исключениями:

  1. Вместо того, чтобы смотреть на последнюю вещь, которую вы добавили в кучу, вы можете посмотреть только на самый маленький элемент (с порядком, определенным для каждой машины) в настоящее время в куче.
  2. Вместо того, чтобы удалить последнее, что вы добавили в кучу, вы можете удалить только один из самых маленьких элементов (с порядком, определенным для каждой машины), который в настоящее время находится в куче.
  3. Вместо того, чтобы добавлять элемент в верхнюю часть кучи, вы можете добавить только элемент в кучу, причем его положение определяется в соответствии с другими элементами в куче (с порядком, определенным для каждой машины).

Эта машина может принимать все обычные языки, просто не используя кучу. Он также может принять язык , добавив «S в кучу, и удаление « » из кучи, когда он читает « ». Он может принимать множество других контекстно-свободных языков. Однако он не может принять, например, (указано без доказательства). РЕДАКТИРОВАТЬ: или это может? Я не думаю, что это возможно, но я был удивлен прежде, и я уверен, что буду продолжать удивляться, когда мои предположения будут продолжать делать из меня ... ну.{anbn{a,b}n0}aab{w{a,b}w=wR}

Может ли он принимать какие-либо контекстно-зависимые или тьюрингово-полные языки?

В целом, какие исследования, если таковые имеются, проводились в этом направлении? Какие результаты есть, если таковые имеются? Меня также интересуют другие разновидности экзотических конечных автоматов, возможно, те, которые используют другие структуры данных для хранения, или различные виды ограничений доступа (например, как LBA являются ограниченными TM). Рекомендации приветствуются. Я заранее прошу прощения, если этот вопрос демонстрирует невежество.


Формальное определение:

Я привожу некоторые более подробные определения автоматов минимальной кучи, чтобы прояснить дальнейшее обсуждение вопросов, которые ссылаются на этот материал.

Мы определяем недетерминированный автомат мини-кучи типа 1 как 7-ряд где ...

(Q,q0,A,Σ,Γ,Z0,δ)
  1. Q - конечное непустое множество состояний;
  2. q0Q - начальное состояние;
  3. AQ - множество принимающих состояний;
  4. Σ - это конечный непустой входной алфавит;
  5. gamma Г ш ( & gamma ) N ш ( & gamma 1 ) = ш ( & gamma 2 )Γ - это конечный непустой входной алфавит, в котором вес символа , таков, что ;γΓw(γ)Nw(γ1)=w(γ2)γ1=γ2
  6. Z0Γ - это специальный символ в нижней части кучи;
  7. δ:Q×(Σ{ϵ})×(Γ{Z0})P(Q×Γ) является функция перехода.

Функция перехода работает, предполагая изначально пустую кучу, состоящую только из . Функция перехода может добавить в кучу произвольный набор (конечный, но, возможно, пустой или с повторениями) элементов . В качестве альтернативы, функция перехода может удалить экземпляр элемента с наименьшим весом из всех элементов, остающихся в куче (т. Е. Элемент в верхней части кучи). Функция перехода может использовать только самый верхний (т. Е. Минимальный вес) экземпляр символа при определении любого данного перехода.γ 1 , & gamma ; 2 , . , , , γ kΓ γ w ( γ )Z0γ1,γ2,...,γkΓγw(γ)

Далее, определите детерминированный автомат минимальной кучи типа 1 как недетерминированный автомат минимальной кучи типа 1, который удовлетворяет следующему свойству: для всех строк таких что и , .| х | = n σ Σ | δ n + 1 ( q 0 , x σ y , Z 0 ) | 1xσyΣ|x|=nσΣ|δn+1(q0,xσy,Z0)|1

Определите также недетерминированный автомат минимальной кучи типа 2 точно так же, как недетерминированный автомат минимальной кучи типа 1, за исключением следующих изменений:

  1. gamma Г ш ( & gamma ) N ш ( & gamma 1 ) = ш ( & gamma 2 ) & gamma 1 = & gamma 2Γ - это конечный непустой входной алфавит, где вес символа , таков, что не обязательно подразумевает ; другими словами, разные символы кучи могут иметь одинаковый вес.γΓw(γ)Nw(γ1)=w(γ2)γ1=γ2
  2. Когда в кучу добавляются экземпляры различных символов кучи с одинаковым весом, их относительный порядок сохраняется в соответствии со стековым порядком «последний пришел - первым вышел» (LIFO).

Спасибо Рафаэлю за то, что он указал на это более естественное определение, которое охватывает (и расширяет) языки без контекста.


Некоторые результаты, продемонстрированные до сих пор:

  1. Автоматы min-heap типа 1 распознают набор языков, которые не являются ни подмножеством, ни надмножеством языков без контекста. [ 1 , 2 ]
  2. Автоматы min-heap типа 2, по их определению, распознают набор языков, которые представляют собой надлежащий надмножество языков без контекста, а также надлежащий надмножество языков, принимаемых автоматами min-heap типа 1.
  3. Языки, принимаемые автоматами с минимальной кучей типа 1, кажутся замкнутыми под объединением, конкатенацией и звездой Клини, но не под дополнением [ 1 ], пересечением или различием;
  4. Языки, принимаемые недетерминированными автоматами минимальной кучи типа 1, представляются надлежащим набором языков, принимаемых детерминированными автоматами минимальной кучи типа 1.

Там может быть несколько других результатов, которые я пропустил. Больше результатов (возможно) на пути.


Последующие вопросы

  1. Закрытие при развороте? -- Открыто
  2. Закрытие при дополнении? - нет!
  3. Увеличивает ли недетерминизм власть? -- Да?
  4. Является ли для типа 2? HALCSL-- Открыто
  5. Увеличивает ли куча мощность для типа 1? - для (?)HAL1HAL2=HALkk>2
  6. Добавляет ли стек увеличение мощности для типа 1? -- Открыто
Patrick87
источник
1
Отличный вопрос, кстати. У меня возникает соблазн найти лемму прокачки для этих автоматов.
Рафаэль
@Raphael: Я думаю, что вы можете использовать мое (обновленное) доказательство для такой леммы: любой язык, для которого вам нужно «запомнить» больше, чем линейный объем информации в некоторой подстроке, чтобы правильно сопоставить последующую подстроку, не может быть проанализирован автомат с минимальной кучей. Я не уверен, возможна ли настоящая лемма в стиле накачки - она ​​может также оказаться частным случаем моей леммы.
Алекс тен Бринк
@AlextenBrink Поскольку для кодирования вещей можно использовать комбинации номеров символов кучи, я не уверен, что линейной границы достаточно.
Рафаэль

Ответы:

25

Вы можете распознать канонический неконтекстно-свободный (но контекстно-зависимый) язык с этим типом конечного автомата. Суть в том , что вы добавляете маркеры в кучу для каждого характере, и во время разбора символов, вы добавляете «большую» фишку в кучу, так что они только в конечном итоге в нижней части кучи , когда вы разобраны все символы.{anbncn | n1}abb

Символами кучи являются и , где . Мы потребить все символы на входе и добавить символы в кучу. Если мы сталкиваемся с a , мы переключаем стратегии: для каждого мы сталкиваемся, впоследствии мы удаляем из кучи и добавляем a в кучу. Когда мы столкнулись с мы должны были бежать из S , чтобы удалить, а затем для каждого в остальном входном снимает из кучи. Если куча пуста в конце, строка на языке. Очевидно, мы отвергаем, если что-то пойдет не так.aba<baabbabcacb

Обновить:

Язык не может быть распознано автоматами с минимальной кучей. Предположим, что у нас есть автомат с минимальной кучей, который может распознавать . Мы смотрим на «состояние», в котором находится автомат после чтения (первая часть ввода, поэтому следующая). Единственное государство , у нас есть содержимое кучи и конкретного состояния автомата он находится. Это означает , что после признания , это нужно «государство» , чтобы удерживать достаточное количество информации , чтобы соответствовать .EPAL={wwR|w{a,b}}EPALwwRwwR

В частности, чтобы сделать это, должно быть возможных различных 'состояний (где ), так как есть возможных слов, состоящих из символов и . Поскольку существует только конечное число состояний и только конечное количество символов кучи, это означает, что существует некоторое слово для которого куча содержит экспоненциальное число некоторого символа кучи, скажем, .2nn=|w|2nabwx

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

Мы докажем, что куча может содержать не более того количества токенов кучи, которое является линейным по количеству символов, считанных из входных данных. Это немедленно исключает, что появляется экспоненциальное число раз в куче, что завершает доказательство того, что не может быть распознан автоматами min-heap.xEPAL

Поскольку в нашем автомате имеется только конечное число состояний и поскольку детерминированный автомат не будет замыкаться в бесконечном цикле, при считывании входного сигнала он будет добавлять не более постоянного числа символов кучи в кучу. Аналогично, при использовании некоторого символа кучи , он может добавить не более постоянного числа символов кучи, строго превышающих и может только уменьшить количество символов в стеке (в противном случае мы получаем бесконечный цикл).yyy

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

В недетерминированном случае доказательство аналогично, но немного сложнее: вместо добавления не более некоторого постоянного числа жетонов кучи в кучу, оно добавляет произвольное количество жетонов кучи в кучу. Однако решающим моментом является то, что это число не зависит от . В частности, если мы можем недетерминированно получить точно правильные символы кучи в куче после распознавания (право на распознавание ), мы также можем недетерминированно выбрать символы кучи, которые соответствуют некоторому другому слову , и тем самым распознать , что противоречит тому, что автомат с минимальной кучей распознает именно .nwwRwwwREPAL

Обновление 3: я сделаю последний аргумент (о недетерминированности) строгим. Согласно приведенному выше аргументу, должно существовать бесконечное множество словтаких что для каждого, после распознавания, куча содержитэлементов ( обратите внимание, что мы можем говорить опоскольку у нас есть бесконечный набор слов). Поскольку мы не можем получить столько элементов в куче с помощью детерминированных средств, у нас должна была быть какая-то форма цикла, в которой мы сначала недетерминированно решили добавить больше элементов в кучу (без использования входных данных), а затем решили выйти из этого цикл, и мы должны пройти этот циклраз.W{a,b}wWwω(|w|)O(f(|w|))ω(1)

Возьмем множество всех таких петель , используемых . Поскольку существует только состояний, размер этого набора , а набор всех его подмножеств также . Теперь обратите внимание, что «детерминированная» часть путей выполнения может вносить вклад только в токенов, что означает, что у многих из экспоненциального числа разных слов должны быть пути выполнения, чьи «детерминированные» части вносят одинаковый вклад жетоны в кучу. В частности, единственный способ получить больше токенов - это взять циклы, которые мы определили выше.WO(1)O(1)O(1)O(|w|)

Объединяя эти наблюдения, это означает, что в должно быть два разных слова , , и , чья «детерминистическая» часть путей выполнения вносит в кучу одни и те же токены, и которые дифференцируются путем взятия некоторого подмножества вышеуказанных циклов. разное количество раз, но при этом используется одно и то же подмножество циклов (помните, что только из этих циклов).Ww1w2O(1)

Теперь мы можем показать, что также может быть распознан автоматом минимальной кучи: мы следуем пути выполнения для как описано выше, но мы проходим циклы же раз, путь выполнения для их пересекает. Это заполняет мин-кучу токенами, так что принимается как суффикс, что завершает доказательство.w1w2w1w2w2

Обновление 2:

Мне только что пришло в голову, что вышеизложенное означает, что мы можем моделировать детерминированный автомат с минимальной кучей, используя только логарифмическое пространство: мы сохраняем счетчик для каждого типа символа в минимальной куче. Как показано выше, этот счетчик будет самое большее , и, следовательно, может быть сохранен с использованием только пробела (поскольку существует только постоянное число этих счетчиков). Это дает нам:O(n)O(logn)

DHALL

HALNL

где - это множество языков, распознаваемых некоторым детерминированным автоматом минимальной кучи.DHAL

Алекс тен Бринк
источник
1
+1 за отличную проницательность, кажется, вы полностью поняли мой смысл. Правильно ли я считаю, что такие машины не распознают палиндромы? Поскольку порядок добавления символов не сохраняется, это кажется невозможным.
Patrick87
@ Patrick87: я думаю об этой проблеме прямо сейчас :)
Алекс тен Бринк
@Raphael Очень классное наблюдение, касающееся машин Тьюринга с логарифмическими ограничениями ресурсов, вы оба, ребята, проделали фантастическую работу по исследованию этих автоматов. Знаете, я просто выбрасывал автомат мини-кучи в качестве примера того, что меня интересовало, но, похоже, это было хорошо принято. На какие еще вопросы можно ответить о таких автоматах? DHAL = HAL? Каковы свойства закрытия HAL? Стоит ли проводить дальнейшие исследования, и если да, то должны ли они остаться здесь или быть поставлены перед новым вопросом? Еще раз спасибо за отличные идеи.
Patrick87
1
@ Рафаэль: Я сделал эту часть полностью строгой. Вы правы, что должно быть достаточно большим - я замалчивал некоторые детали слева и справа. n
Алекс тен Бринк
1
@ Рафаэль: Действительно, это так. , поэтому по теореме о пространственной иерархии и некоторых включениях. CSL=NLINSPACEDHALCSL
Алекс тен Бринк
19

Вот что мы (верим) знаем:

  • HALCFL (тип-1, тип-2)
  • CFLHAL (type-1)
  • CFLHAL (тип-2, по определению)
  • CSLHAL (тип-1, тип-2)

Смотрите подробности и некоторые другие заметки ниже.


HALCFL

Эта часть ответа относится как к типу 1, так и к типу 2.

Автомат с минимальной кучей (HA) с конечным, полностью упорядоченным алфавитом кучи принимает .L={anbncnnN}CSLCFL

Предположения: Подобно PDA, наша функция перехода потребляет самый верхний символ кучи и записывает произвольное количество символов кучи. Куча изначально содержит выделенный символ который больше всех других символов кучи.$

Пусть автомат с минимальной кучей иA=(Q,ΣI,ΣH,,q0,QF)

  • Q={q0,q1,q2,qf} множество состояний
  • ΣI={a,b,c} входной алфавит.
  • ΣH=a,b,$ алфавит кучи с порядком .a<b<$
  • QF={qf}
  •  (Q×ΣI×ΣH)×(Q×ΣH) с
    • (q0,a,σ)(q0,aσ) для всехσΣH
    • (q0,b,a)(q1,b)
    • (q1,b,a)(q1,b)
    • (q1,c,b)(q2,ε)
    • (q2,c,b)(q2,ε)
    • (q2,c,$)(qf,ε)

Автомат записывает по одному в кучу для каждого на входе. Когда происходит , он потребляет столько же сколько было , записывая a в кучу для каждого найденного . Это не мешает подсчет , потому что куча удобно держит на вершине. Только после того, как все взяты из кучи являются приняты; только после того, как будет найдено столько сколько (а вместе с ним и ), примет с пустой кучей и конечным состоянием.aabbabbaaccbaA

Таким образом, .L(A)=L


CFLHAL

Эта часть ответа относится только к типу 1.

Рассмотрим множество четных палиндромов и предположить , что существует ГК с .EPAL={wwRw{a,b}}AL(A)=L

Предположение: мы находим с итак что находится в том же состоянии и имеет одинаковое содержимое кучи после считывания и соответственно. Поскольку принимает как и , он также принимает (и ), что противоречит .w1,w2{a,b}w1w2|w1|=|w2|Aw1w2Aw1w1Rw2w2Rw1w2REPALw2w1RL(A)=EPAL


CSLHAL

Эта часть ответа относится как к типу 1, так и к типу 2.

Те же рассуждения, которые мы использовали в (для типа 1), могут быть использованы, чтобы показать, что контекстно-зависимый язык не находится в .EPAL{www{a,b}}HAL


HAL?CSL

Это все еще открыто и для типа 1 и для типа 2.


Дальнейшие Фактоиды

HA кажется ортогональным к подмножеству языков с умеренным контекстным восприятием, принятых Embedded Pushdown Automata : хотя HA может моделировать ограниченное количество стековых стеков, они не могут симулировать произвольно много (как EPA может). Тем не менее, HA может получить доступ к верхним символам стеков, которые в настоящее время не находятся сверху (что EPA не может).

Рафаэль
источник
+1, отличный ответ. По существу эквивалентно методу Бринка, верно? Тем не менее, строгость и точность являются выдающимися. Задумывались ли вы, могут ли такие машины принимать все КЛЛ? Это кажется невозможным, так как информация о заказе теряется кучей ...
Patrick87
Это та же идея, что и у Алекса, да. Рад, что вы можете получить что-то от этого, тем не менее. Я добавил идею для другого направления, но есть (огромный?) Разрыв. Нужно подумать об этом с ясной головой завтра и, может быть, подстрелить некоторых коллег.
Рафаэль
Я чувствую, что должен был включить доказательство правильности, чтобы заработать дополнительные кредиты для строгости. ;) Думаю, это не должно быть слишком сложно по индукции по . n
Рафаэль
Схема доказательства, которую вы обозначаете как гипотезу, - это то, что я имел в виду, и я нахожу это довольно убедительным ... также, и это незначительный технический момент, я думаю, что вы используете язык палиндромов четной длины, не все палиндромы ... хотя доказательство определенно работает в любом случае (обратите внимание, что оно работает и для простых палиндромов, поэтому HAL даже не так силен, как DPDA, другой результат).
Patrick87
@ Patrick87 Проблема в том, что может быть больше возможных конфигураций, в которых данный HA может быть после чтения символов, чем есть слова, в частности, если мы разрешаем -transitions, которые помещают символы в кучу. nε
Рафаэль