¿Una referencia para un enfoque "más algebraico" de autómatas pushdown y CFL?

17

En el libro de Sakarovitch sobre teoría de autómatas, está escrito en la introducción a la sección de racionales en el grupo libre que el material presentado en él establece "la base de una teoría verdaderamente matemática de lenguajes libres de contexto". Sin embargo, esto no se hace explícito, ya que los lenguajes libres de contexto y los autómatas pushdown están más allá del alcance del libro.

Soy consciente de algunas conexiones de grupos libres (y especialmente de lo que Sakarovitch llama monoides involutivos ) con la teoría de autómatas pushdown y lenguajes libres de contexto, por ejemplo, el lenguaje Dyck, el teorema de Shamir, etc. Sin embargo, he tenido un es difícil encontrar una fuente en la que se construya realmente la "teoría matemática verdadera de los lenguajes libres de contexto", mencionada por Sakarovitch.

Lo más parecido que he encontrado es el libro de Berstel sobre transducciones y lenguajes sin contexto. Sin embargo, a primera vista me parece que los autómatas pushdown se tratan solo marginalmente en este libro, mientras que la teoría de los subconjuntos racionales de un grupo libre no se aplica en absoluto. Quizás el material que estoy buscando ha sido destinado al Volumen C de Eilenberg, pero tampoco estoy seguro de eso.

Por lo tanto, me gustaría pedir un puntero a un libro, encuesta o tal vez un conjunto de documentos, del cual podría aprender algo sobre la "teoría matemática verdaderamente de los lenguajes libres de contexto" de Sakarovitch y sus relaciones con los grupos libres y su racionalidad. subconjuntos. ¿O tal vez estoy buscando algo que en realidad no existe?

Jára Cimrman
fuente

Respuestas:

9

La tesis doctoral de Sakarovitch de 1976, titulada Monoïdes syntactiques et languages ​​algébriques (monoides sintácticos y lenguajes algebraicos), gira en torno a este tema. En ese momento, esto condujo a la definición de monoides puntiagudos (ver, por ejemplo, su artículo MFCS'75 ). Alrededor de los años 80, el objeto algebraico de elección para estudiar las CFL pasó al grupo Hotz: Sakarovitch incluso tiene un artículo sobre ese tema en Acta. Inf. Hasta donde yo sé, los monoides puntiagudos no obtuvieron la atención que merecían, aunque las mismas ideas se pueden encontrar en Behle, Krebs, et al. ; Asimismo, algunos enfoques recientes, basados ​​en herramientas más sofisticadas, especialmente la dualidad de Stone, pueden proporcionar un marco sólido para tales estudios.

Otro enfoque moderno es el de Clark sobre el entramado de concepto sintáctico , con el que no estoy familiarizado.

En cuanto a las intenciones reales del autor, una forma segura es preguntarle directamente.

Michaël Cadilhac
fuente