Autómata de contador multidireccional determinista de dos vías o logspace TM con contador

¿Se sabe algo sobre lenguajes reconocidos por un autómata determinista bidireccional de múltiples cabezas o un logspace TM con contador (modelo equivalente)? Esta clase se llama Aux2DC en el documento de mi asesor . ¿O sobre tal clase no determinista? He obtenido que la clase de idiomas reconocidos por tales máquinas no deterministas incluye NL y parece estar incluida en LOGCFL. ¿Hay documentos sobre este tema? ¿Es ese resultado trivial?

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

Respuestas:

Se puede simular un autómata finito multi-cabeza determinista bidireccional (no determinista) mediante un espacio de registro DTM (NTM), y viceversa.

Entonces, para incluir la clase , ¡no necesitas un contador! $\mathsf{NL}$

El valor del contador que pertenece a un autómata finito multi-cabeza no determinista bidireccional con un contador puede estar limitado por un polinomio, de lo contrario, el cálculo entra en un bucle infinito. Dado que tanto tales marcador A y las cabezas de entrada pueden ser simuladas en logspace, límite superior puede ser reemplazado con . $\mathsf{LOGCFL}$ $\mathsf{NL}$

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

Hay muchos documentos sobre estos temas, por ejemplo, este documento . Puedes encontrar más después de buscar en Google. (Consulte también el Lema 1 de este documento ).

Abuzer Yakaryilmaz
fuente

Gracias, conocía la simulación L (NL) mediante un autómata bidireccional multicabezal (no determinista). Primero, pensé que obtuve la inclusión de NL para el autómata determinista con contador, pero de repente pareció que en mi reducción aumentaba el no determinismo y solucioné la publicación, pero no tan correctamente como debería. Estudiaré estos documentos, ¡muchas gracias!

Alexander Rubtsov