¿Cuáles son algunos resultados interesantes en la teoría de autómatas?

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.

  1. Autómatas finitos deterministas;
  2. Autómatas finitos no deterministas;
  3. Expresiones regulares
  4. 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.

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.

Los autómatas finitos están muy conectados a los semigrupos, lo que forma la base de la teoría de Krohn-Rhodes.

Puedes ver Álgebra de procesos.