Hay muchos resultados interesantes, pero creo que los siguientes son un buen punto de partida (tal vez en dificultad creciente).
La robustez del lenguaje regular
Los siguientes modelos son todos equi-expresivos y capturan el conjunto de los llamados lenguajes regulares.
- Autómatas finitos deterministas;
- Autómatas finitos no deterministas;
- Expresiones regulares
- Lógica monádica de segundo orden sobre secuencias
El alcance de los autómatas temporizados es decidible
Los autómatas cronometrados extienden los autómatas clásicos con relojes y protectores de valor real sobre dichos relojes para modelar el tiempo transcurrido. Es decidible comprobar si se puede acceder a un estado determinado del autómata.
- ¿Cuáles son los límites teóricos del poder computacional dictados por las leyes conocidas de la física?
- ¿Cuáles son los algoritmos de aprendizaje automático que se sabe que no son transparentes?
- ¿Cuál sería el límite de velocidad de procesamiento teórico en una computadora construida completamente con componentes discretos?
- ¿Puedes sugerir algún buen proyecto de Linux para menores de último año?
- ¿Qué se entiende por administración remota del servidor, herramientas de monitoreo?
Determinación de Safra de Buchi Autoamta
La construcción de Safra convierte un autómata de Buchi no determinista (autómata sobre cadenas infinitas) de tamaño n en un autómata determinista Rabin equivalente de tamaño 2 ^ O (n log n). Esto también muestra la existencia de un autómata complementado de tamaño 2 ^ O (n log n). Esta construcción es una de las gemas de la teoría de autómatas.
La equivalencia de los transductores de estado finito de valor finito es decidible
Este es el resultado de Helmut Seidl, que construye una buena cantidad de maquinaria que luego se ha reutilizado en muchas otras construcciones.
La equivalencia de los autómatas deterministas pushdown es decidible
Este es un resultado increíble. Fue sorprendente hasta el punto de que Géraud Sénizergues recibió el premio Godel por ello.
