2dca (autómata determinista bidireccional de un contador) (Petersen, 1994) puede reconocer el siguiente lenguaje unario: POWER={02n∣n≥0}.POWER={02n∣n≥0}.\begin{equation} \mathtt{POWER} = \lbrace 0^{2^n} \mid n \geq 0 \rbrace. \end{equation} ¿Hay algún otro lenguaje unario no trivial reconocido...
Puede una máquina estándar de dos contadores ( ) con las siguientes instrucciones:c1,c2c1,c2c_1,c_2 1) ADD 1 to c_i, GOTO label_j 2) IF c_i = 0 GOTO label_j, OTHERWISE SUB 1 to c_i and GOTO label_k 3) GOTO label_j 4) HALT and ACCEPT|REJECT decide el siguiente idioma: L={n2∣n≥1}L={n2∣n≥1}L = \{...
Los autómatas pushdown alternos unidireccionales (1APDA) pueden reconocer cualquier idioma en (Alternancia de Chandra, Kozen y Stockmeyer, 1981) . Al reemplazar un almacenamiento pushdown de un 1APDA con un contador, podemos obtener un autómata alternativo unidireccional con un contador (1ACA). Mi...
¿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...