Какой класс языков распознается конечными автоматами с головами?

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

Определим конечный автомат с головами следующим образом:$k$

К-голова НКА является кортеж , где:$(Q, \Sigma, \Delta, q_0, F)$

• Как обычно, - это конечный набор состояний, - это конечный алфавит, - начальное состояние, а - набор принимающих состояний. Пусть \ Sigma_ \ varepsilon: = \ Sigma \ cup \ {\ varepsilon \} обозначает набор символов, включая пустую строку.$Q$$\Sigma$$q_0$$F$$\Sigma_\varepsilon := \Sigma \cup \{\varepsilon\}$

• $\Delta \subseteq Q \times (\Sigma_\varepsilon)^k \times Q$ - это отношение перехода: переход означает, что если машина находится в состоянии , он может читать в , так что является следующим символом для головы (или если эта голова не двигается), а затем переходить в состояние .$(p, (\sigma_1, \sigma_2, \ldots, \sigma_k), q)$$p$$(\sigma_1, \sigma_2, \ldots, \sigma_k)$$\sigma_i$$i$$\varepsilon$$q$

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

Язык машины есть множество строк такое , что существует действительный пробег машины , где строка , полученная по этой перспективе все равны .$w$$k$$w$

Вопрос: Какой класс языков распознается такими машинами? Было ли это изучено?

Первое наблюдение состоит в том, что такие машины производят класс больше, чем обычные языки. Например, язык признается следующим -Руководитель НКА с -х государств:

(Здесь ребро, помеченное обозначает переход вида .)$\sigma_1 / \sigma_2$$(p, (\sigma_1, \sigma_2), q)$

Однако второе наблюдение заключается в том, что не все контекстно-свободные языки распознаются; например, кажется, что язык Dyck не может быть распознан этими машинами с головой.$k$

Эта модель является одной из стандартных моделей в теории автоматов и была исследована некоторыми исследователями.

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

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

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

Некоторые общие ссылки:

• Машины Тьюринга с сублогарифмическим пространством - https://books.google.lv/books?id=vNPuNOo9BUYC

перемежаемость

• Вильям Гефферт - https://dblp.uni-trier.de/pers/hd/g/Geffert:Viliam

Вероятностный расчет

• Иоан И. Макари - https://dblp.org/pers/hd/m/Macarie:Ioan_I=

Вероятностные и квантовые вычисления

• Русинс Фрейвалдс - https://dblp.uni-trier.de/pers/hd/f/Freivalds:Rusins
• Абузер Якарылмаз - https://dblp.uni-trier.de/pers/hd/y/Yakaryilmaz:Abuzer

Родственные модели: автоматы с несколькими счетчиками и автоматы с использованием гальки.