Autômatos determinísticos bidirecionais de múltiplos cabeçotes ou logspace TM com contador

Isso é conhecido sobre linguagens reconhecidas pelo autômato determinístico bidirecional bidirecional ou pelo logspace TM com contador (modelo equivalente)? Esta classe chamada Aux2DC no meu conselheiro papel . Ou sobre essa classe não determinística? Eu obtive que a classe de idiomas reconhecidos por esses maschines não determinísticos inclui NL e parece estar incluída no LOGCFL. Existem documentos sobre esse assunto? Esse resultado é trivial?

cc.complexity-theory complexity-classes fl.formal-languages logspace counter-automata Alexander Rubtsov
fonte

Respostas:

Um autômato finito de múltiplas cabeças determinístico (não determinístico) bidirecional pode ser simulado por um espaço de registro DTM (NTM) e vice-versa.

Portanto, para incluir a classe , você não precisa de um contador! $\mathsf{NL}$

O valor do contador pertencente a um autômato finito de duas cabeças, não-determinístico, com um contador, pode ser limitado por um polinômio; caso contrário, o cálculo entra em um loop infinito. Uma vez que tanto essa contra um e as cabeças de entrada pode ser simulada em logspace, limite superior pode ser substituída com . $\mathsf{LOGCFL}$ $\mathsf{NL}$

$\mathsf{L}$ $\mathsf{NL}$

Existem muitos artigos sobre esses tópicos, por exemplo, este artigo . Você pode encontrar mais depois de pesquisar no Google. (Verifique também o Lema 1 deste documento .)

Abuzer Yakaryilmaz
fonte

Obrigado, eu sabia sobre a simulação L (NL) por autômato bidirecional de várias cabeças (não determinístico). Primeiro, pensei que obtivesse a inclusão de NL para autômato determinístico com contador, mas de repente pareceu que, em minha redução, o não-determinismo diminuiu e eu consertei o cargo, mas não tão adequadamente quanto deveria. Vou estudar esses trabalhos, muito obrigado!

Alexander Rubtsov