Teoremas de punto fijo para la solución de ecuaciones sobre lenguajes

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.

• Autores: Ramírez Ramírez, José Luis
• Fecha de publicación: 2011
• Institución: Universidad Nacional de Colombia
• Repositorio: Universidad Nacional de Colombia
• Idioma: spa
• OAI Identifier: oai:repositorio.unal.edu.co:unal/7709
• Acceso en línea: https://repositorio.unal.edu.co/handle/unal/7709; http://bdigital.unal.edu.co/4161/
• Palabra clave: 51 Matemáticas / Mathematics; 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
• Rights: openAccess
• License: Atribución-NoComercial 4.0 Internacional