Os autômatos limitados lineares não determinísticos de visita limitada reconhecem apenas idiomas regulares?

9

Os autômatos limitados lineares não determinísticos de visita limitada reconhecem apenas idiomas regulares?

Por autômato delimitado linear não-determinístico (nLBA), quero dizer uma máquina de Turing não-determinística de fita única, na qual a entrada é "acolchoada" com marcadores nas duas extremidades que nunca podem ser substituídos e, portanto, a cabeça nunca pode sair da região de entrada, "fora" dos marcadores finais.

O LBA é limitado por visita se houver um número k modo que todas as execuções em todas as entradas terminem e visitem todas as células da fita na maioria das vezes k .

Essa máquina reconhece apenas idiomas regulares? O resultado de Hennie parece dizer isso apenas para máquinas determinísticas, se eu estiver lendo certo. O resultado também vale para máquinas não determinísticas? Se sim, uma referência seria apreciada.

Prateek
fonte

Respostas:

7

Um pouco exagerado, mas: este artigo mostra (entre outras coisas interessantes) que os transdutores Hennie não determinísticos realizam exatamente a classe de transduções definíveis por MSO não determinísticas. Estes últimos têm domínios regulares.

Boson
fonte