Галечный автомат

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

История

Автоматы Pebble были представлены в 1986 году, когда было показано, что в некоторых случаях детерминированный преобразователь , дополненный камнем, может обеспечить логарифмическую экономию пространства по сравнению даже с недетерминированным преобразователем логарифмического пространства (т. е. выполнять вычисления в $\log \log n$ Функции ячеек ленты, для которых требуется недетерминированная машина $\log n$ ячейки ленты), подразумевая, что камешек увеличивает мощность машин Тьюринга, функции которых требуют пространства между $\log \log n$ и $\log n.$ ^[1] Также было показано, что конструкции преобразуют иерархию все более мощных моделей штабелированных машин в эквивалентные детерминированные конечные автоматы с числом до трех камешков, что показывает, что дополнительные камешки еще больше увеличивают мощность.

Древоходные автоматы с вложенными камешками

Древовидный автомат с вложенными камешками — это древесный автомат с дополнительным конечным множеством фиксированного размера, содержащим камешки, отождествляемый с $\{1,2,\dots ,n\}$ . Помимо обычных действий, автомат может положить камешек в текущий посещенный узел, поднять камешек из текущего посещенного узла и выполнить проверку «присутствует ли i-й камешек в текущем узле?». Существует важное ограничение стека на порядок, в котором можно класть или поднимать камешки — i+1-й камешек можно положить только в том случае, если камешки с 1-го по i-й уже находятся на дереве, а i+1- Камешек можно поднять только в том случае, если на дереве нет камешков с i+2-го по n-й. Без этого ограничения автомат обладает неразрешимой пустотой и выразительной силой, превосходящей обычные древовидные языки.

Класс языков, распознаваемых детерминированными (соответственно недетерминированными) древовидными автоматами с n камушками, обозначается $DPA_{n}$ (соответственно $PA_{n}$ ). Мы также определяем $DPA=\bigcup _{n}DPA_{n}$ и аналогично $PA=\bigcup _{n}PA_{n}$ .

Характеристики

существует язык, распознаваемый древесным автоматом с 1 камешком, но не распознаваемый обычным древесным автоматом; это означает, что либо $TWA\subsetneq DPA$ или эти классы несравнимы, что является открытой проблемой
$PA\subsetneq REG$ , т.е. древесноходящие автоматы, дополненные камешками, строго слабее ветвящихся автоматов
неизвестно, является ли $DPA=PA$ , т. е. можно ли определить гуляющие по деревьям автоматы с камушками
неизвестно, замкнуты ли древоходные автоматы-камешки при дополнении
иерархия гальки строга для древесных автоматов, для каждого n $PA_{n}\subsetneq PA_{n+1}$ и $DPA_{n}\subsetneq DPA_{n+1}$

Автоматы и логика

Древоходные камнеходные автоматы допускают интересную логическую характеристику. ^[2] Позволять $FO+TC$ обозначают набор свойств дерева, описываемых в логике транзитивного замыкания первого порядка , и $FO+{\text{pos}}\,TC$ то же самое касается положительной логики транзитивного замыкания, то есть логики, в которой оператор транзитивного замыкания не используется в области отрицания. Тогда можно доказать, что $PA\subseteq FO+TC$ и, по сути, $PA=FO+{\text{pos}}\,TC$ - Языки, распознаваемые древовидными автоматами-камешками, - это именно те языки, которые выражаются в логике положительного транзитивного замыкания.