Недетерминированные линейные ограниченные автоматы ограниченного посещения распознают только регулярные языки?

9

Недетерминированные линейные ограниченные автоматы ограниченного посещения распознают только регулярные языки?

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

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

Такая машина распознает только обычные языки? Результат Хенни, кажется, говорит это только для детерминированных машин, если я правильно понял. Действительно ли результат верен и для недетерминированных машин? Если да, ссылка будет принята.

Prateek
источник

Ответы:

7

Немного излишне, но: эта статья показывает (среди прочего), что недетерминированные преобразователи Хенни точно реализуют класс недетерминированных MSO-определяемых преобразований. Последние имеют обычные домены.

Бозон
источник