sobre los idiomas aceptados por los autómatas finitos de Watson-Crick con retrasos
Autores: Sempere, José M.
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
sobre los idiomas aceptados por los autómatas finitos de Watson-Crick con retrasos
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Potencia computacional
Autómatas finitos Watson-Crick
Restricciones
Función de transición
Retraso
Clases de lenguaje
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 33
Citaciones: Sin citaciones
En este trabajo, analizamos el poder computacional de los autómatas finitos Watson-Crick (WKFA) si se imponen algunas restricciones sobre la función de transición en el modelo. Consideramos que las restricciones impuestas se refieren a la diferencia máxima de longitud entre las dos cadenas de entrada, lo cual se llama retraso. Demostramos que la clase de lenguaje aceptada por WKFA con tales restricciones es una subclase adecuada de los lenguajes aceptados por WKFA arbitrarios en general. Además, iniciamos el estudio de las clases de lenguaje caracterizadas por WKFA con retrasos acotados. Demostramos algunos de los resultados mediante diversas relaciones entre WKFA y sistemas de pegatinas.
Descripción
En este trabajo, analizamos el poder computacional de los autómatas finitos Watson-Crick (WKFA) si se imponen algunas restricciones sobre la función de transición en el modelo. Consideramos que las restricciones impuestas se refieren a la diferencia máxima de longitud entre las dos cadenas de entrada, lo cual se llama retraso. Demostramos que la clase de lenguaje aceptada por WKFA con tales restricciones es una subclase adecuada de los lenguajes aceptados por WKFA arbitrarios en general. Además, iniciamos el estudio de las clases de lenguaje caracterizadas por WKFA con retrasos acotados. Demostramos algunos de los resultados mediante diversas relaciones entre WKFA y sistemas de pegatinas.