Esta es una pregunta de seguimiento de esta .
En una pregunta anterior sobre máquinas de estado exóticas , Alex ten Brink y Raphael abordaron las capacidades computacionales de un tipo peculiar de máquina de estado: los autómatas de min-montón. Pudieron demostrar que el conjunto de idiomas aceptados por tales máquinas () no es un subconjunto ni un superconjunto del conjunto de lenguajes libres de contexto. Dada la resolución exitosa y el aparente interés en esa pregunta, procedo a hacer varias preguntas de seguimiento.
Se sabe que los idiomas regulares están cerrados bajo una variedad de operaciones (podemos limitarnos a operaciones básicas como unión, intersección, complemento, diferencia, concatenación, estrella de Kleene e inversión), mientras que los idiomas libres de contexto tienen un cierre diferente propiedades (estas están cerradas bajo unión, concatenación, estrella de Kleene e inversión).
¿HAL está cerrado bajo complementación?
fuente