Teoremas de punto fijo para la solución de ecuaciones sobre lenguajes
Cargando...
Archivos
Autores
Director
Tipo de contenido
Document language:
Español
Fecha
Título de la revista
ISSN de la revista
Título del volumen
Documentos PDF
Resumen
En este trabajo se aborda el estudio de teoremas de punto fijo sobre retículos completos con el fin de ser aplicados a una clase de funciones entre lenguajes, llamadas funciones polinomiales. Estas funciones permiten caracterizar los lenguajes regulares y los independientes de contexto como una componente del menor punto fijo de una determinada función polinomial. Además, permiten solucionar algunas ecuaciones sobre lenguajes, en particular se demuestra el lema de Arden y una generalización de éste, lo cual permitirá caracterizar algunos lenguajes lineales. / Abstract. In this work we study fixed-point theorem on complete lattices to be applied to a class of functions between languages, called polynomial functions. These functions allow characterization of regular languages and context-free languages as one component of the minor fixed point of a given polynomial function. Also, would solve some languages equations, in particular proves the Arden’s lemma and a generalization of it, which will characterize some linear languages.
Abstract
Palabras clave propuestas
Ecuaciones sobre lenguajes; Funciones polinomiales sobre lenguajes; Teoremas de punto fijo; Retículos completos; Retículos booleanos; Lema de Arden; Teorema de Ginsburg-Rice / Languages equations; Languages polynomial functions; Fixed-point theorems; Complete lattices; Boolean lattices; Arden’s lemma; Ginsburg-Rice theorem